Факторизация.Тайна Ферма.Факторизуем вручную число 100895598169
Habr ·
Пролог. Пусть например 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 похоже сложнее ,пока у меня не получается. Читать далее
Пролог. Пусть например 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 похоже сложнее ,пока у меня не получается. Читать далее