Метод факторизации Fermats - Fermats factorization method - Wikipedia

Ферма с факторизация метод, названный в честь Пьер де Ферма, основан на представлении странный целое число как разница двух квадратов:

${\displaystyle N=a^{2}-b^{2}.}$

Эта разница алгебраически факторизованный как ${\displaystyle (a+b)(a-b)}$; если ни один из множителей не равен единице, это правильная факторизация N.

Каждое нечетное число имеет такое представление. Действительно, если ${\displaystyle N=cd}$ это факторизация N, тогда

${\displaystyle N=\left({\frac {c+d}{2}}\right)^{2}-\left({\frac {c-d}{2}}\right)^{2}}$

С N странно, то c и d также нечетные, поэтому эти половинки целые. (Число, кратное четырем, также является разностью квадратов: пусть c и d быть даже.)

В простейшей форме метод Ферма может быть даже медленнее, чем пробное деление (худший случай). Тем не менее комбинация пробного деления и ферма более эффективна, чем любая другая.

Основной метод

Пробуют разные значения а, надеясь, что ${\displaystyle a^{2}-N=b^{2}}$, площадь.

ФермаФактор (N): // N должно быть нечетным    a ← потолок (sqrt (N)) b2 ← a * a - N повторять, пока Би 2 является площадь:        a ← a + 1 b2 ← a * a - N      // эквивалентно: // b2 ← b2 + 2 * a + 1     // a ← a + 1 возвращаться а - sqrt (b2) // или a + sqrt (b2)

Например, чтобы фактор ${\displaystyle N=5959}$, первая попытка для а квадратный корень из 5959 округляется до следующего целого числа, т.е. 78. Потом, ${\displaystyle b^{2}=78^{2}-5959=125}$. Поскольку 125 не является квадратом, делается вторая попытка, увеличивая значение а на 1. Вторая попытка также не удалась, потому что 282 снова не квадрат.

Пытаться:	1	2	3
а	78	79	80
б^2	125	282	441
б	11.18	16.79	21

Третья попытка дает идеальный квадрат 441. Итак, ${\displaystyle a=80}$, ${\displaystyle b=21}$, а факторы 5959 находятся ${\displaystyle a-b=59}$ и ${\displaystyle a+b=101}$.

Предположим, что N имеет более двух простых множителей. Эта процедура сначала находит факторизацию с наименьшими значениями а и б. То есть, ${\displaystyle a+b}$ наименьший множитель ≥ квадратный корень из N, и так ${\displaystyle a-b=N/(a+b)}$ - наибольший множитель ≤ корень-N. Если процедура находит ${\displaystyle N=1\cdot N}$, что показывает, что N простое.

За ${\displaystyle N=cd}$, позволять c быть самым большим фактором subroot. ${\displaystyle a=(c+d)/2}$, поэтому количество шагов примерно ${\displaystyle (c+d)/2-{\sqrt {N}}=({\sqrt {d}}-{\sqrt {c}})^{2}/2=({\sqrt {N}}-c)^{2}/2c}$.

Если N простое (так что ${\displaystyle d=1}$), нужно ${\displaystyle O(N)}$ шаги. Это плохой способ доказать примитивность. Но если N имеет множитель, близкий к квадратному корню, метод работает быстро. Точнее, если c отличается меньше чем ${\displaystyle {\left(4N\right)}^{1/4}}$ из ${\displaystyle {\sqrt {N}}}$, метод требует всего одного шага; это не зависит от размера N.^{[нужна цитата ]}

Ферма и пробное отделение

Попробуйте разложить на множители простое число N = 2345678917, но также вычислить б и а − б на протяжении. Поднимаясь из ${\displaystyle {\sqrt {N}}}$, мы можем свести в таблицу:

а	48,433	48,434	48,435	48,436
б^2	76,572	173,439	270,308	367,179
б	276.7	416.5	519.9	605.9
а − б	48,156.3	48,017.5	47,915.1	47,830.1

На практике с этой последней строкой никто не возился, пока б целое число. Но учтите, что если N имел фактор subroot выше ${\displaystyle a-b=47830.1}$, Метод Ферма уже нашел бы это.

Пробное подразделение обычно пытается до 48 432 человек; но после всего четырех шагов Ферма нам нужно разделить только до 47830, чтобы найти множитель или доказать простоту.

Все это предполагает комбинированный метод факторинга. Выберите границу ${\displaystyle c>{\sqrt {N}}}$; использовать метод Ферма для факторов между ${\displaystyle {\sqrt {N}}}$ и ${\displaystyle c}$. Это дает предел для пробного деления, который ${\displaystyle c-{\sqrt {c^{2}-N}}}$. В приведенном выше примере с ${\displaystyle c=48436}$ граница пробного деления - 47830. Разумным выбором может быть ${\displaystyle c=55000}$ давая оценку 28937.

В этом отношении метод Ферма дает убывающую отдачу. Конечно, можно было бы остановиться до этого момента:

а	60,001	60,002
б^2	1,254,441,084	1,254,561,087
б	35,418.1	35,419.8
а − б	24,582.9	24,582.2

Улучшение сита

При рассмотрении таблицы для ${\displaystyle N=2345678917}$, можно быстро сказать, что ни одно из значений ${\displaystyle b^{2}}$ квадраты:

а	48,433	48,434	48,435	48,436
б^2	76,572	173,439	270,308	367,179
б	276.7	416.5	519.9	605.9

Нет необходимости вычислять все квадратные корни из ${\displaystyle a^{2}-N}$, и даже не исследовать все значения для а. Квадраты всегда равны 0, 1, 4, 5, 9, 16 по модулю 20. Значения повторяются с каждым увеличением а на 10. В этом примере N равно 17 по модулю 20, поэтому вычитая 17 по модулю 20 (или прибавляя 3), ${\displaystyle a^{2}-N}$ производит 3, 4, 7, 8, 12 и 19 по модулю 20 для этих значений. Очевидно, что только 4 из этого списка могут быть квадратом. Таким образом, ${\displaystyle a^{2}}$ должно быть 1 mod 20, что означает, что а равно 1, 9, 11 или 19 по модулю 20; это произведет ${\displaystyle b^{2}}$ который заканчивается на 4 mod 20 и, если квадрат, б закончится 2 или 8 мод 10.

Это можно сделать с любым модулем. Используя тот же ${\displaystyle N=2345678917}$,

по модулю 16:	Квадраты	0, 1, 4 или 9
	N mod 16 есть	5
	так ${\displaystyle a^{2}}$ может быть только	9
	и а должно быть	3 или 5 или 11 или 13 по модулю 16
по модулю 9:	Квадраты	0, 1, 4 или 7
	N mod 9 есть	7
	так ${\displaystyle a^{2}}$ может быть только	7
	и а должно быть	4 или 5 по модулю 9

Обычно для каждого модуля выбирают степень различных простых чисел.

Учитывая последовательность а-значения (начало, конец и шаг) и модуля, можно действовать следующим образом:

FermatSieve (N, astart, aend, astep, модуль) a ← astart делать модуль раз: b2 ← a * a - N если b2 - квадрат по модулю модуля: FermatSieve (N, a, aend, astep * modulus, NextModulus) endif        а ← а + ступень Enddo

Но рекурсия останавливается, когда мало а-значения остаются; то есть, когда (aend-astart) / astep мало. Также потому, что а 's размер шага постоянен, можно вычислить последовательные b2 с добавлением.

Дальнейшее модульное усовершенствование можно сделать, применив алгоритм деления как аффинное преобразование, то есть ${\displaystyle X=\beta x+a}$, ${\displaystyle Y=\beta y+b}$, ${\displaystyle N=\beta z+r}$, по любому целочисленному кольцу ${\displaystyle \mathbb {Z} _{\beta }}$ куда ${\displaystyle \beta <X}$. После небольшого количества алгебры можно заключить, что ${\displaystyle \lfloor N/\beta ^{2}\rfloor -s=xy}$ и ${\displaystyle \lfloor ab/\beta \rfloor =t}$ где s и t идентичны определению переносов, которое делается при умножении делителей на основание ${\displaystyle \beta }$.^{[нужна цитата ]}

Улучшение множителя

Метод Ферма работает лучше всего, когда есть множитель, близкий к квадратному корню из N.

Если примерное соотношение двух факторов (${\displaystyle d/c}$) известно, то Рациональное число ${\displaystyle v/u}$ можно выбрать рядом с этим значением. Например, если ${\displaystyle Y/X\approx q}$, тогда ${\displaystyle X\approx {\sqrt {N/q}}}$ является хорошей оценкой меньшего из пары делителей. ${\displaystyle Nuv=cv\cdot du}$, а множители примерно равны: коэффициент Ферма, примененный к Nuv, быстро их найдет. потом ${\displaystyle \gcd(N,cv)=c}$ и ${\displaystyle \gcd(N,du)=d}$. (Пока не c разделяет ты или же d разделяет v.) Дальнейшее обобщение этого подхода предполагает, что ${\displaystyle Y^{n}/X^{m}\approx q}$, означающий, что ${\displaystyle X\approx N^{m/(m+n)}/q^{1/(m+n)}}$.

Как правило, если соотношение неизвестно, различные ${\displaystyle u/v}$ значения могут быть опробованы, и попытайтесь учесть каждый результат Nuv. Р. Леман разработал систематический способ сделать это, так что плюсовое пробное деление Ферма может учитывать N в ${\displaystyle O(N^{1/3})}$ время.^[1]

Прочие улучшения

Фундаментальные идеи метода факторизации Ферма лежат в основе квадратное сито и общее числовое поле сито, самые известные алгоритмы факторинга больших полупростые, которые являются «худшим случаем». Основное улучшение квадратного сита по сравнению с методом факторизации Ферма состоит в том, что вместо простого нахождения квадрата в последовательности ${\displaystyle a^{2}-n}$, он находит подмножество элементов этой последовательности, у которых товар квадрат, и он делает это очень эффективно. Конечный результат тот же: разница квадратного мода п что, если нетривиально, может быть использовано для факторизации п.

Смотрите также

• Завершение квадрата
• Факторизация многочленов
• Факторная теорема
• Правило FOIL
• Факторизация моноида
• Треугольник Паскаля
• главный фактор
• Факторизация
• Метод факторизации Эйлера
• Целочисленная факторизация
• Программный синтез
• Таблица гауссовских целочисленных факторизаций
• Уникальная факторизация

Примечания

1. Леман, Р. Шерман (1974). «Факторинг больших целых чисел» (PDF). Математика вычислений. 28 (126): 637–646. Дои:10.2307/2005940.

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

• Ферма (1894 г.), Oeuvres de Fermat, 2, п. 256
• Макки, Дж (1999). «Ускорение метода факторинга Ферма». Математика вычислений (68): 1729–1737.

внешняя ссылка

• Время выполнения факторизации Ферма, на blogspot.in
• Онлайн-калькулятор факторизации Ферма, на windowspros.ru