Метод факторизации Ферма

 Файл:Pierre de Fermat.pngthumbrightПьерФермаалгоритм факторизации (разложения на множители) нечётного целогочисла nn, предложенный Пьером Ферма (1601—1665) в 1643 году.
 Метод основан на поиске таких целых чисел xx и yy, которыеудовлетворяют соотношению x2y2=nx2y2=n, что ведёт к разложениюn=(xy)(x+y)n=(xy)(x+y).

История


 В начале XVII века во Франции математические идеи начали активнораспространяться между учёными посредством переписки. В 1638 году ккругу переписывающихся учёных присоединился Пьер Ферма. Переписка былаудобным способом общения, так как Ферма жил в Тулузе, а многие егознакомые учёные жили в Париже. Одним из таких учёных был Марен Мерсенн,занимавшийся распространением писем, пересылкой и связью многих учёныхмежду собой. 26 декабря 1638 года в письме Мерсенну Ферма упомянул, чтонашёл метод, с помощью которого можно находить делители положительныхчисел, но какие-либо подробности и описание метода он опустил. На тотмомент Мерсенн также вёл переписку с французским математиком БернаромФреникль де Бесси, занимавшимся, как и Ферма, теорией чисел, вчастности, делителями натуральных чисел и совершенными числами. В начале1640 года, узнав о том, что Ферма получил метод нахождения делителей,Френикль пишет Мерсенну, и тот пересылает письмо Ферма. Мерсенн долгоевремя был связующим звеном между двумя математиками в их переписке.Именно в письмах Френиклю Ферма смог доказать корректность методафакторизации, а также впервые сформулировать и обосновать основныеположения теоремы, которая позже была названа Малой теоремой Ферма
 .

Обоснование


 Метод Ферма основан на теореме о представлении числа в видеразности двух квадратов:
 Если n>1n>1 нечетно, то существует взаимно однозначное соответствие междуразложением на множители n=abn=ab и представлением в виде разностиквадратов n=x2y2n=x2y2 с x>y>0x>y>0, задаваемое формуламиx=a+b2,x=a+b2, y=ab2,y=ab2, a=x+y,a=x+y, b=xy.b=xy.

Описаниеалгоритма


 Для разложения на множители нечётного числа nn ищется пара чисел(x,y)(x,y) таких, что x2y2=nx2y2=n, или (xy)(x+y)=n(xy)(x+y)=n. При этомчисла (x+y)(x+y) и (xy)(xy) являются множителями nn, возможно, тривиальными(то есть одно из них равно 1, а другое — nn.)
 В нетривиальном случае, равенство x2y2=nx2y2=n равносильно x2n=y2x2n=y2,то есть тому, что x2nx2n является квадратом.
 Поиск квадрата такого вида начинается сx=nx=n — наименьшего числа, при которомразность x2nx2n неотрицательна.
 Для каждого значения kN,kN, начиная с k=1k=1, вычисляют(n+k)2n(n+k)2n и проверяют, не является лиэто число точным квадратом. Если не является, то kk увеличивают наединицу и переходят на следующую итерацию.
 Если (n+k)2n(n+k)2n является точнымквадратом, то есть x2n=(n+k)2n=y2,x2n=(n+k)2n=y2,то получено разложение:

n=x2y2=(x+y)(xy)=ab,n=x2y2=(x+y)(xy)=ab, в которомx=(n+k)x=(n+k)
 Если оно является тривиальным и единственным, то nn — простое.
 На практике значение выражения на (k+1)(k+1)-ом шаге вычисляется с учётомзначения на kk-ом шаге:

(s+1)2n=s2+2s+1n,(s+1)2n=s2+2s+1n, гдеs=n+k.s=n+k.

Примеры


Пример с малым числомитераций


 Возьмём число n=10873n=10873. Вычислимs=n=105.s=n=105. Для k=1,2,...k=1,2,... будемвычислять значения функции s+ks+k. Для дальнейшей простоты построимтаблицу, которая будет содержать значения y=(s+k)2ny=(s+k)2n и yy накаждом шаге итерации. Получим:
По модулю 16:Квадраты равны0, 1, 4 или 9
n mod 16 равно5
следовательно, a2a2 равно9
и равно3, 5, 11 или 13 по модулю 16
По модулю 9:Квадраты равны0, 1, 4, или 7
n mod 9 равно7
следовательно, a2a2 равно7
и равно4 или 5 по модулю 9

Оптимизациямножителем


 Метод Ферма хорошо работает в случае, когда у числа nn есть множитель,приблизительно равный квадратному корню из nn.
 Если известно примерное соотношение d/cd/c между множителями числа nn,то можно выбрать рациональное число u/vu/v, приблизительно равное этомусоотношению. Тогда можно записать следующее равенство:nuv=cvdunuv=cvdu, где множители cvcv и dudu близки в силу сделанныхпредположений. Поэтому применив метод Ферма для разложения числа nuvnuv,их можно быстро найти. Далее для нахождения cc и dd можно использоватьравенства gcd(n,cv)=cgcd(n,cv)=c и gcd(n,du)=dgcd(n,du)=d (в случае, если uu не делитсяна cc и vv не делится на dd).
 В общем случае, когда соотношение между множителями nn не известно,можно попытаться использовать разные соотношения u/vu/v, и пробоватьразложить получившееся в результате число nuvnuv. Алгоритм, основанный наданном методе, был впервые предложен американским математиком ШерманомЛеманом в 1974 году и называется метод Лемана. Алгоритм детерминированораскладывает данное натуральное число nn на множители за O(n1/3)O(n1/3)арифметических операций, однако в настоящее время представляет толькоисторический интерес и на практике почти не используется.

МетодКрайчика-Ферма


 Обобщение метода Ферма было предложено в 1926 году. Он предложилрассматривать вместо пар чисел (x,y),(x,y), которые удовлетворяютсоотношению x2y2=n,x2y2=n, искать пары чисел, удовлетворяющих более общемусравнению x2y2(modn).x2y2(modn). Такое сравнение можно найти,перемножив несколько сравнений вида u2iviu2ivi, где vivi —небольшие числа, произведения которых будет квадратом. Для этого можнорассмотреть пары чисел (ui,vi)(ui,vi), где uiui — целый числа чутьбольше nn, а vi=u2invi=u2in. Крайчик заметил, что многие изполученных таким образом чисел vivi раскладываются на небольшие простыемножители, то есть числа vivi являются гладкими.

Пример


 С помощью метода Крайчика-Ферма разложим число n=2041.n=2041. Число 4646является первым чей квадрат больше числа nn: 462=2116.462=2116.
 Вычислим значение функции v(u)=u2nv(u)=u2n для всех u=46,47, Мыполучим 75,168,263,360,459,560,
 По методу Ферма, нужно было бы продолжать вычисления пока не был бынайден квадрат какого-либо числа. По методу Крайчика-Ферма далее нужнопоследовательно искать такие uk, для которых v(u1)v(u2)...v(uk)=y2,u1u2uk=x. Тогда

x2=u21u22...u2k(u21n)(u22n)(u2kn)=v(u1)v(u2)v(uk)=y2(modn).
 Из алгоритма Крайчика-Ферма следует, что все полученные числа(u2kn) можно легко факторизовать.
 Действительно:75=352, 168=2337, 360=23325, 560=2457.
 Очевидно, что произведение полученных четырёх чисел будет квадратом:210345472. Тогда теперь можно вычислитьx,y:
x=46474951311(mod2041), y=25325271416(mod2041).
 Далее с помощью алгоритма Евклида находим gcd(1416311,2041)=13.
 Таким образом, 2041=13157.

АлгоритмДиксона


 В 1981 году математик Карлтонского университета Джон Диксон опубликовалразработанный им метод факторизации на основе идей Крайчика.
 Алгоритм Диксона основан на понятии о факторных базах и являетсяобобщением алгоритма факторизации Ферма. В алгоритме вместо пар чисел,удовлетворяющих уравнению x2y2=n ищутся пары чисел,удовлетворяющих более общему уравнению x2y2(modn), длярешения которого Крайчиком было замечено несколько полезных фактов.Вычислительная сложность алгоритма

T=O(L(n)2),
 гдеL(n)=exp(lnnlnlnn).

Другиеулучшения


 Идея метода факторизации Ферма лежит в основе одних из самых быстрыхалгоритмов для факторизации больших полупростых чисел — методеквадратичного решета и общем методе решета числового поля. Основноеотличие метода квадратичного решета от метода Ферма заключается в том,что вместо поиска квадрата в последовательности a2n находятся парытаких чисел, чьи квадраты равны по модулю n (каждая из этих пар можетявляться разложением числа n). Затем уже среди найденных пар чиселищется та пара, которая и является разложением числа n.
 Развитием метода факторизации Ферма является метод квадратичных формШенкса (также известен как SQUFOF), основанный на примененииквадратичных форм. Интересно то, что для 32-разрядных компьютеровалгоритмы, основанные на данном методе, являются безусловными лидерамисреди алгоритмов факторизации для чисел от 1010 до 1018.

Применение


 Алгоритм факторизации Ферма может быть применён для криптоанализа RSA.Если случайные числа p,q, произведение которых равно n, близки другдругу, то они могут быть найдены методом факторизации Ферма. После чегоможно найти секретную экспоненту d, взломав таким образом RSA. Намомент опубликования алгоритма RSA было известно лишь небольшоеколичество алгоритмов факторизации, самым известным из которых являлсяметод Ферма.

Интересныефакты


 Известный английский экономист и логист У. С. Джевонс сделал в своейкниге «Принципы науки» («The Principles of Science», 1874 год) следующеепредположение: По данным двум числам можно найти их произведение простыми надёжным способом, но совсем другое дело, когда для большого числанеобходимо найти его множители. Можно ли сказать, какие два числаперемножены, чтобы получилось число 8 616 460 799? Я думаю, что вряд ликто-либо кроме меня знает это.
 Интересно то, что указанное Джевонсом число может быть разложено вручнуюметодом Ферма с применением метода решета примерно за 10 минут.Действительно, n=92825. Используяметод решета, можно быстро прийти к соотношению:
928802n=10233601=31992.
 Таким образом разложение на простые множители имеет вид8616460799=8968196079.
 Основная же мысль Джевонса о сложности разложения чисел на простыемножители по сравнению с их перемножением справедлива, но только в томслучае, когда речь идёт о произведении чисел, не настолько близких другк другу.