Факторизация.Тайна Ферма.Факторизуем вручную число 100895598169
<p>Пролог.</p><p>Пусть например N = 253 с точки зрения факторизации это прямоугольник p*<em>q. Построим прямоугольник близкий к p*</em>q.Посмотрим изнутри N =11*<em>23 берем 2 слоя короткой стороны и присоединяем их к длинной стороне получаем получаем прямоугольник N1 = 12*</em>21 =252 очень близкий к N . Смотря извне предполагаем что N1 = N -1 очень близкий к N , N1 = N -1 = 253-1 = 2*<em>2*</em>3*<em>3*</em>7 т.е. возникло множество вариантов N1. И комбинаторика не проблема т.к. скорость роста вариантов гораздо медленнее роста N. Перебором получаем один из вариантов (2*<em>2*</em>3)*<em>(3*</em>7) = 12*<em>21 т.е. N = 11*</em>23 = 253 похож на 12*21+1=12*22 ,как вариант. Пока числа маленькие в этом методе нет смысла.</p><p><code> Обратимся к историческому факту. </code></p><p>Аббат Мерсенн, как то в ходе переписки, предложил Ферма выяснить является ли простым число 100895598169. Ферма быстро дал ответ, данное число является произведением простых чисел 898423 на 112303. И опять на предложение поделиться методикой… Ну, вы поняли. Речь о Марене Мерсенн (Marin Mersenne, 1588–1648). Координатор научной жизни. В ту эпоху не было научных журналов, и Мерсенн был организатором обмена знаниями в Европе. Он вёл обширную переписку. Среди его корреспондентов были Декарт, Галилей, Паскаль, Ферма, Гюйгенс, Торричелли и другие.</p><p>Факторизовать число N=100895598169 вручную не простая задача.</p><p>Ферма давно покинул лучший из миров и тайну забрал с собой.Не знаю как действовал Ферма.Я факторизую так - N - 1 , N - 3 и на пятом шаге N - 9. Далее N1 = 100895598169 - 9 = 100895598160 , N1 = 100895598160 = 2*<em>2*</em>2*<em>2*</em>5*<em>7*</em>7*<em>19*</em>193*<em>7019 , N = 2*</em>2*<em>2*</em>2*<em>5*</em>7*<em>7*</em>19*<em>193*</em>7019 + 9 с помощью не сложной ручной комбинаторики получаем N = (5*<em>7*</em>7*<em>19*</em>193+9)*<em>(2*</em>2*<em>2*</em>2*<em>7019) Voila! получилось ! N = 898424*</em>112304 а хотелось получить N = 898423*112303 И ДА. В этой бочке мёда ложка дёгтя в этом случае q нацело делится на p потому и всё просто.Факторизовать RSA-155 похоже сложнее ,пока у меня не получается.</p> <a href="https://habr.com/ru/articles/1081208/?utm_source=habrahabr&utm_medium=rss&utm_campaign=1081208#habracut">Читать далее</a>