Пролог.
Пусть например 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=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 похоже сложнее ,пока у меня не получается.
ссылка на оригинал статьи https://habr.com/ru/articles/1081208/