Метод факторизации Эйлера - Eulers factorization method

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

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

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

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

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

Теоретические основы

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

Сначала сделайте вывод, что

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

и множить обе стороны, чтобы получить

${\displaystyle (a-c)(a+c)=(d-b)(d+b)}$ (1)

Теперь позвольте ${\displaystyle k=\operatorname {gcd} (a-c,d-b)}$ и ${\displaystyle h=\operatorname {gcd} (a+c,d+b)}$ так что существуют константы ${\displaystyle l,m,l',m'}$ удовлетворение

• ${\displaystyle (a-c)=kl}$,
• ${\displaystyle (d-b)=km}$,

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

• ${\displaystyle (a+c)=hm'}$,
• ${\displaystyle (d+b)=hl'}$,

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

Подставляя их в уравнение (1), получаем

${\displaystyle klhm'=kmhl'}$

Отмена общих факторов дает

${\displaystyle lm'=l'm}$

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

• ${\displaystyle l=l'}$
• ${\displaystyle m=m'}$

Так

• ${\displaystyle (a-c)=kl}$
• ${\displaystyle (d-b)=km}$
• ${\displaystyle (a+c)=hm}$
• ${\displaystyle (d+b)=hl}$

Теперь мы видим, что ${\displaystyle m=\operatorname {gcd} (a+c,d-b)}$ и ${\displaystyle l=\operatorname {gcd} (a-c,d+b)}$

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

${\displaystyle \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.}$

Поскольку каждый множитель представляет собой сумму двух квадратов, один из них должен содержать оба четных числа: либо ${\displaystyle (k,h)}$ или же ${\displaystyle (l,m)}$. Без ограничения общности предположим, что пара ${\displaystyle (k,h)}$ даже. Факторизация тогда становится

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

Пример работы

С: ${\displaystyle \ 1000009=1000^{2}+3^{2}=972^{2}+235^{2}}$

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

а = 1000	(А) а − c = 28	k = НОД [A, C] = 4
б = 3	(В) а + c = 1972	час = НОД [B, D] = 34
c = 972	(С) d − б = 232	л = НОД [A, D] = 14
d = 235	(D) d + б = 238	м = НОД [B, C] = 116

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

${\displaystyle 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]\,}$

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

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

${\displaystyle =293\cdot 3413\,}$

Рекомендации

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