Метод факторизации Эйлера

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

Идея о том, что два различных представления нечетного положительного целого числа могут привести к факторизации, по-видимому, была впервые предложена Марином Мерсенном . Однако широкое применение он получил только сто лет спустя Эйлера. Его самым знаменитым применением метода, который теперь носит его имя, было факторизация числа $1000009$, которое, по-видимому, ранее считалось простым, хотя по каким-либо основным критериям простоты оно не является псевдопростым .

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

Недостаток и ограничение

Большим недостатком метода факторизации Эйлера является то, что его нельзя применять для факторизации целого числа, при этом любой простой множитель формы 4 k + 3 встречается в нечетной степени при его простой факторизации, поскольку такое число никогда не может быть суммой двух квадратов. . Четные нечетные составные числа вида 4 k + 1 часто являются произведением двух простых чисел вида 4 k + 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=\operatorname {gcd} (a-c,d-b)$ и $h=\operatorname {gcd} (a+c,d+b)$ так что существуют некоторые константы $l,m,l',m'$ удовлетворяющий

• $(a-c)=kl$,
• $(d-b)=km$,

$\operatorname {gcd} (l,m)=1$

• $(a+c)=hm'$,
• $(d+b)=hl'$,

$\operatorname {gcd} (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=\operatorname {gcd} (a+c,d-b)$ и $l=\operatorname {gcd} (a-c,d+b)$

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

$\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}$

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

а = 1000	(А) а - с = 28	k = НОД[A,C] = 4
б = 3	(Б) а + с = 1972 г.	ч = НОД[B,D] = 34
с = 972	(В) d − b = 232	l = НОД[A,D] = 14
д = 235	(Д) д + б = 238	м = НОД[B,C] = 116

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

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

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

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

$=293\cdot 3413\,$

Псевдокод

function Euler_factorize(int n) -> list[int]
   if is_prime(n) then
       print("Number is not factorable")
       exit function
   for-loop from a=1 to a=ceiling(sqrt(n))
       b2 = n - a*a
       b = floor(sqrt(b2))
       if b*b==b2
           break loop preserving a,b
   if a*a+b*b!=n then
       print("Failed to find any expression for n as sum of squares")
       exit function
   for-loop from c=a+1 to c=ceiling(sqrt(n))
       d2 = n - c*c
       d = floor(sqrt(d2))
       if d*d==d2 then
           break loop preserving c,d
   if c*c+d*d!=n then
       print("Failed to find a second expression for n as sum of squares")
       exit function
   A = c-a, B = c+a
   C = b-d, D = b+d 
   k = GCD(A,C)//2, h = GCD(B,D)//2
   l = GCD(A,D)//2, m = GCD(B,C)//2
   factor1 = k*k + h*h
   factor2 = l*l + m*m
   return list[ factor1, factor2 ]

Ссылки

• Оре, Эйстейн (1988). «Метод факторизации Эйлера» . Теория чисел и ее история . Курьерская корпорация. стр. 59–64 . ISBN  978-0-486-65620-5 .
• Макки, Джеймс (1996). «Превращение метода факторинга Эйлера в алгоритм факторинга». Бюллетень Лондонского математического общества . 4 (28): 351–355. дои : 10.1112/blms/28.4.351 .