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

Метод разложения Эйлера — это техника факторизации числапутём записи его в виде суммы двух квадратов двумя разными путями.Например, число 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