Метод факторизации Ферма

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

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

Эта разница алгебраически факторизуется как $(a+b)(a-b)$; если ни один из факторов не равен единице, это правильная факторизация N .

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

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

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

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

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

Кто-то пробует различные значения a , надеясь, что $a^{2}-N=b^{2}$, квадрат.

FermatFactor(N): // N should be odd
    a ← ceiling(sqrt(N))
    b2 ← a*a - N
    repeat until b2 is a square:
        a ← a + 1
        b2 ← a*a - N 
     // equivalently: 
     // b2 ← b2 + 2*a + 1 
     // a ← a + 1
    return a - sqrt(b2) // or a + sqrt(b2)

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

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

Третья попытка дает идеальный квадрат 441. Таким образом, $a=80$, $b=21$, а факторы числа 5959 равны $a-b=59$ и $a+b=101$.

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

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

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

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

Попробуйте разложить простое число N = 2 345 678 917 на факторы , а также вычислить b и a − b повсюду. Поднимаясь от ${\sqrt {N}}$ округлив до следующего целого числа, равного 48 433, мы можем свести в таблицу:

Пытаться	1-й	2-й	3-й	4-й
а	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

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

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

Все это предполагает комбинированный метод факторинга. Выберите какую-нибудь границу $a_{\mathrm {max} }>{\sqrt {N}}$; используйте метод Ферма для факторов между ${\sqrt {N}}$ и $a_{\mathrm {max} }$. Это дает границу для пробного деления, которая равна $a_{\mathrm {max} }-{\sqrt {a_{\mathrm {max} }^{2}-N}}$. В приведенном выше примере с $a_{\mathrm {max} }=48436$ граница пробного деления равна 47830. Разумным выбором может быть $a_{\mathrm {max} }=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

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

При рассмотрении таблицы для $N=2345678917$, можно быстро сказать, что ни одно из значений $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

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

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

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

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

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

FermatSieve(N, astart, aend, astep, modulus)
    a ← astart
    do modulus times:
        b2 ← a*a - N
        if b2 is a square, modulo modulus:
            FermatSieve(N, a, aend, astep * modulus, NextModulus)
        endif
        a ← a + astep
    enddo

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

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

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

Если приблизительное соотношение двух факторов ( $d/c$) известно, то рациональное число $v/u$ можно выбрать около этого значения. $Nuv=cv\cdot du$, а метод Ферма, примененный к Nuv , найдет факторы $cv$ и $du$ быстро. Затем $\gcd(N,cv)=c$ и $\gcd(N,du)=d$. (Если только c не делит u или d не делит v .)

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

Другие улучшения

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

См. также

• Завершение площади
• Факторизация полиномов
• Факторная теорема
• Правило ФОЛЬГИ
• Моноидная факторизация
• Треугольник Паскаля
• Главный фактор
• Факторизация
• Метод факторизации Эйлера
• Целочисленная факторизация
• Синтез программы
• Таблица гауссовских целочисленных факторизаций
• Уникальная факторизация

Ссылки

• Ферма (1894), Сочинения Ферма , т. 2, с. 256
• Макки, Дж (1999). «Ускорение метода факторинга Ферма» . Математика вычислений . 68 (228): 1729–1737. дои : 10.1090/S0025-5718-99-01133-3 .

Внешние ссылки

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