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

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

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

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

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

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

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

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

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

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

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

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

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

• ${\ displaystyle (ac) = kl}$,
• ${\ displaystyle (db) = км}$,

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

• ${\ Displaystyle (а + с) = хм '}$,
• ${\ displaystyle (d + b) = hl '}$,

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

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

${\ displaystyle klhm '= kmhl'}$

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

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

Теперь, используя тот факт, что и - пары относительно простых чисел, мы находим, что ${\ Displaystyle (л, м)}$${\ Displaystyle \ влево (л ', м' \ вправо)}$

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

Так

• ${\ displaystyle (ac) = kl}$
• ${\ displaystyle (db) = км}$
• ${\ Displaystyle (а + с) = hm}$
• ${\ displaystyle (d + b) = hl}$

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

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

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

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

${\ Displaystyle п = \ left (\ left ({\ tfrac {k} {2}} \ right) ^ {2} + \ left ({\ tfrac {h} {2}} \ right) ^ {2} \ вправо) \ влево (l ^ {2} + m ^ {2} \ right). \,}$

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

Поскольку: ${\ displaystyle \ 1000009 = 1000 ^ {2} + 3 ^ {2} = 972 ^ {2} + 235 ^ {2}}$

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

а = 1000	(А) а - с = 28	k = gcd [A, C] = 4
b = 3	(В) а + с = 1972	h = gcd [B, D] = 34
с = 972	(В) г - б = 232	l = gcd [A, D] = 14
d = 235	(D) d + b = 238	m = gcd [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. DOI : 10.1112 / БЛМ / 28.4.351 .