Алтернативен метод за факторизиране за големи числа

Копие от този документ може да се получи от Интернет:
http://betaexpert.narod.ru/antirsa.htm

Алтернативен метод за факторизиране
Юрий Решетов
ПРЕДВИЖЕТЕ

Първо, нека се обърнем към един от най-старите методи за факторизиране (разлагане
по прости фактори) на числата, което е открито от Пиер Ферма.

Същността на метода е, че определено съставно число N, което е
произведението на два фактора P и Q може да бъде факторизирано с помощта на диафана
уравнения:

И изчислете квадратния корен от по-малко нечетно число, или
Методът на Нютон или други методи.

Въпросът не е в това как да се организира факторизацията според уравнението на Ферма, а в това
този метод не е много подходящ за приложни цели. Ако Y е малко число,
тези. разликата между двата фактора е незначителна, тогава резултатът може да бъде получен
много бързо. Но дори факторите да са числа с една и съща битова, времето
изразходвани за намиране на Y може да се нуждаят от астрономически. Просто казано:

Има смисъл да се търси решение, използвайки уравнението на Ферма, само ако Y
е от незначително значение.

Следователно е необходим метод, с който би било възможно да се намали обемът
изчисления по уравнението на Ферма.

И този метод беше намерен за някои N.

Да предположим, че N е съставно число под формата на произведение от две прости числа
фактори P и Q. Ако сумата от фактори отговаря на условията:

(P + Q)% 12 = 9 условие (1)

След това, за да разделим числото N по уравнението на Ферма, броят на стъпките няма да надвишава
една четвърт от общия брой битове на N.

Например, ако N е 1024 бита в публичния ключ на RSA, и просто
факторите N отговарят на условие (1), тогава факторизацията на такъв брой ще отнеме
повече от 128 стъпки от метода на Ферма. За всеки съвременен личен, това е
пренебрежително незначително време.

Помислете за рекурсивна поредица от числа, започващи с N [0], отговарящи на условието (1).

N [I] = (N [I - 1] - 61) * 4 + 1 (5)

Тези. всяко следващо число се получава чрез изваждане от предишното
номер 61, умножете по 4 и добавете 1.

Ако тестваме цялата поредица от тези числа, използвайки уравнението на Ферма, тогава
оказва се, че всички те имат едно и също значение за X. Това е:

X ^ 2 = N [0] + Y [0] ^ 2 = N [1] + Y [1] ^ 2 = N [2] + Y [2] ^ 2 =. = N [M] + Y [M] ^ 2 (6)

Тъй като в уравнението на Ферма има само две неизвестни X и Y, това е достатъчно
коефициент всеки N [I] в нашата серия, за да намери X, който също се вписва
за нашата Н. И изчислявайки от нея последната неизвестна от уравнението - Y, вече
намиране на факторите N по формули (3) и (4).

Не си струва да напомняме, че ако се опитате да разберете стойностите на поредица от числа N [I]
методи, различни от метода на Ферма, резултатът може да бъде много
сложно. Факт е, че повечето от известните методи за факторизация са по-големи
подходящ за разширяване в малки фактори, докато методът на Ферма,

---