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

Метод разложения Эйлера — это техника факторизации числа путём записи его в виде суммы двух квадратов двумя разными путями. Например, число $1000009$ можно записать как $1000^{2}+3^{2}$ или как $972^{2}+235^{2}$ и метод Эйлера даёт разложение $1000009=293\cdot 3413$.

История

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

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

Недостатки

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

Это ограничение сделало метод разложения Эйлера нежелательным для алгоритмов разложения на компьютере , поскольку любой пользователь, пытающийся применить метод к случайному числу, вряд ли знает, будет ли метод Эйлера применим к этому числу. Только относительно недавно были попытки разработать метод Эйлера в компьютерных алгоритмах для специальных чисел, для которых метод Эйлера заведомо применим.

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

Тождество Брахмагупты — Фибоначчи утверждает, что произведение двух сумм двух квадратов является суммой двух квадратов. Метод Эйлера опирается на эту теорему, но может рассматриваться как обратный теореме подход, если дано $n=a^{2}+b^{2}=c^{2}+d^{2}$, мы ищем разложение $n$ на произведение двух квадратов.

Сначала мы выводим, что

$a^{2}-c^{2}=d^{2}-b^{2}$

и разлагаем обе части на множители

$(a-c)(a+c)=(d-b)(d+b)$ (1)

Теперь пусть k = НОД( a-c, d-b), а h = НОД(a+c, d+b), так что существуют некоторые числа $l,m,l',m'$, для которых

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

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

$klhm'=kmhl'$

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

$lm'=l'm$

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

• $l=l'$
• $m=m'$

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

• $(a-c)=kl$
• $(d-b)=km$
• $(a+c)=hm$
• $(d+b)=hl$

Теперь мы видим, что m = НОД(a+c, d-b) и l = НОД(a-c, d+b)

После применения тождества Брахмагупты — Фибоначчи мы получим

$\left(k^{2}+h^{2}\right)\left(l^{2}+m^{2}\right)=\left(kl-hm\right)^{2}+(km+hl)^{2}={\bigl (}(a-c)-(a+c){\bigr )}^{2}+{\bigl (}(d-b)+(d+b){\bigr )}^{2}=(2c)^{2}+(2d)^{2}=4n,$

$\left(k^{2}+h^{2}\right)\left(l^{2}+m^{2}\right)=(kl+hm)^{2}+(km-hl)^{2}={\bigl (}(a-c)+(a+c){\bigr )}^{2}+{\bigl (}(d-b)-(d+b){\bigr )}^{2}=(2a)^{2}+(2b)^{2}=4n.$

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

$n=\left(\left({\tfrac {k}{2}}\right)^{2}+\left({\tfrac {h}{2}}\right)^{2}\right)\left(l^{2}+m^{2}\right).\,$.

Пример

Дано: $\ 1000009=1000^{2}+3^{2}=972^{2}+235^{2}$

Из формул выше мы имеем:

a = 1000	(A) a − c = 28	НОД[A,C] k = 4
b = 3	(B) a + c = 1972	НОД[B,D] h = 34
c = 972	(C) d − b = 232	l = 7
d = 235	(D) d + b = 238	m = 58

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

$1000009=\left[\left({\frac {4}{2}}\right)^{2}+\left({\frac {34}{2}}\right)^{2}\right]\cdot \left(7^{2}+58^{2}\right)\,$

$=\left(2^{2}+17^{2}\right)\cdot \left(7^{2}+58^{2}\right)\,$

$=(4+289)\cdot (49+3364)\,$

$=293\cdot 3413\,$