Метод разложения Эйлера

Метод разложения Эйлера — это техника факторизации числа путём записи его в виде суммы двух квадратов двумя разными путями. Например, число 1000009 можно записать как 10002+32 или как 9722+2352 и метод Эйлера даёт разложение 1000009=2933413.

История


 Идею, что два различных представления нечётного положительного числа могут привести к разложению, впервые высказал Марен Мерсенн. Однако он не применялся интенсивно, пока сто лет позже метод не стал применять Эйлер. Торжеством метода, который теперь носит имя Эйлера, стало разложение на множители числа 1000009, которое считалось до этого простым, даже хотя оно не являлось псевдопростым по всем главным тестам простоты.
 Метод факторизации Эйлера более эффективен, чем метод Ферма для чисел, делители которых не близки и, потенциально, существенно эффективнее, чем пробное деление, если можно найти представление чисел в виде суммы двух квадратов достаточно быстро. Разработка Эйлера позволила находить разложение чисел много быстрее и разрабатывать большие таблицы разложения чисел. Методы, используемые для поиска чисел в виде суммы двух квадратов, по сути, те же, что и для нахождения разности квадратов в методе факторизации Ферма.

Недостатки


 Большим недостатком метода разложения Эйлера является факт, что его нельзя применить для разложения целых чисел с простым делителем вида 4k + 3, входящем в разложение на простые множители с нечётной степенью, поскольку такие числа не могут быть представлены в виде суммы двух квадратов. Даже нечётные составные числа вида 4k + 1 часто являются произведением двух простых вида 4k + 3 (например, 3053 = 43 × 71) и не могут быть разложены методом Эйлера.
 Это ограничение сделало метод разложения Эйлера нежелательным для алгоритмов разложения на компьютере , поскольку любой пользователь, пытающийся применить метод к случайному числу, вряд ли знает, будет ли метод Эйлера применим к этому числу. Только относительно недавно были попытки разработать метод Эйлера в компьютерных алгоритмах для специальных чисел, для которых метод Эйлера заведомо применим.

Теоретический базис


 утверждает, что произведение двух сумм двух квадратов является суммой двух квадратов. Метод Эйлера опирается на эту теорему, но может рассматриваться как обратный теореме подход, если дано n=a2+b2=c2+d2, мы ищем разложение n на произведение двух квадратов.
 Сначала мы выводим, что
a2c2=d2b2

 и разлагаем обе части на множители
(ac)(a+c)=(db)(d+b)
(1)
 Теперь пусть k = НОД( a-c, d-b), а h = НОД(a+c, d+b), так что существуют некоторые числа l,m,l,m, для которых

  • (ac)=kl,
  • (db)=km, НОД(l, m) = 1
  • (a+c)=hm,
  • (d+b)=hl, НОД(l', m') = 1

 После подстановки в (1) получаем
klhm=kmhl

 После сокращения общих множителей получим
lm=lm

 Теперь используем факт, что (l,m) и (l,m) взаимно просты, так что получаем

  • l=l
  • m=m

 Таким образом,

  • (ac)=kl
  • (db)=km
  • (a+c)=hm
  • (d+b)=hl

 Теперь мы видим, что m = НОД(a+c, d-b) и l = НОД(a-c, d+b)
 После применения мы получим
(k2+h2)(l2+m2)=(klhm)2+(km+hl)2=((ac)(a+c))2+((db)+(d+b))2=(2c)2+(2d)2=4n,

(k2+h2)(l2+m2)=(kl+hm)2+(kmhl)2=((ac)+(a+c))2+((db)(d+b))2=(2a)2+(2b)2=4n.

 Так как каждый множитель является суммой двух квадратов, один из них должен содержать оба чётных числа — либо (k,h), либо (l,m). Без потери общности будем считать, что числа в паре (k,h) чётны. Разложение превращается в
n=((k2)2+(h2)2)(l2+m2).
.

Пример


 Дано:  1000009=10002+32=9722+2352
 Из формул выше мы имеем:
a = 1000(A) ac = 28НОД[A,C] k = 4
b = 3(B) a + c = 1972НОД[B,D] h = 34
c = 972(C) db = 232l = 7
d = 235(D) d + b = 238m = 58

 Таким образом,

1000009=[(42)2+(342)2](72+582)

=(22+172)(72+582)
=(4+289)(49+3364)
=2933413