Операция выполнена!
Закрыть
info@vsetut.pro
Стать автором
Вернуться

Факторизация.Тайна Ферма.Факторизуем вручную число 100895598169

11.09.2026 09:27:52 | Хабр
Хабы: Криптография, Алгоритмы

Пролог.

Пусть например N = 253 с точки зрения факторизации это прямоугольник p*q. Построим прямоугольник близкий к p*q.Посмотрим изнутри N =11*23 берем 2 слоя короткой стороны и присоединяем их к длинной стороне получаем получаем прямоугольник N1 = 12*21 =252 очень близкий к N . Смотря извне предполагаем что N1 = N -1 очень близкий к N , N1 = N -1 = 253-1 = 2*2*3*3*7 т.е. возникло множество вариантов N1. И комбинаторика не проблема т.к. скорость роста вариантов гораздо медленнее роста N. Перебором получаем один из вариантов (2*2*3)*(3*7) = 12*21 т.е. N = 11*23 = 253 похож на 12*21+1=12*22 ,как вариант. Пока числа маленькие в этом методе нет смысла.

Обратимся к историческому факту.

Аббат Мерсенн, как то в ходе переписки, предложил Ферма выяснить является ли простым число 100895598169. Ферма быстро дал ответ, данное число является произведением простых чисел 898423 на 112303. И опять на предложение поделиться методикой… Ну, вы поняли. Речь о Марене Мерсенн (Marin Mersenne, 1588–1648). Координатор научной жизни. В ту эпоху не было научных журналов, и Мерсенн был организатором обмена знаниями в Европе. Он вёл обширную переписку. Среди его корреспондентов были Декарт, Галилей, Паскаль, Ферма, Гюйгенс, Торричелли и другие.

Факторизовать число N=100895598169 вручную не простая задача.

Ферма давно покинул лучший из миров и тайну забрал с собой.Не знаю как действовал Ферма.Я факторизую так - N - 1 , N - 3 и на пятом шаге N - 9. Далее N1 = 100895598169 - 9 = 100895598160 , N1 = 100895598160 = 2*2*2*2*5*7*7*19*193*7019 , N = 2*2*2*2*5*7*7*19*193*7019 + 9 с помощью не сложной ручной комбинаторики получаем N = (5*7*7*19*193+9)*(2*2*2*2*7019) Voila! получилось ! N = 898424*112304 а хотелось получить N = 898423*112303 И ДА. В этой бочке мёда ложка дёгтя в этом случае q нацело делится на p потому и всё просто.Факторизовать RSA-155 похоже сложнее ,пока у меня не получается.

Читать далее
Подробнее
Читайте также
НОВОСТИ

ВСЕ НОВОСТИ
ПИШИТЕ

Техническая поддержка проекта ВсеТут

info@vsetut.pro

Copyright © 2026 - vsetut.pro