Алгоритм Ферма похож на алгоритм Бухштаба и является эффективным, если у раскладываемого числа n есть делитель (который
может и не быть простым числом), незначительно превосходящий n .
Пусть число n является нечетным. Алгоритм заключается в том, чтобы представить число n в виде
n = x2 − y2 = (x − y)(x + y),
где x, y - неотрицательные целые числа. Если числа x и y найдены, то
(x − y) и (x + y) являются простыми делителями числа n.
Если число y = 0, то делителем числа n является n .
Если известно y и y > 0, можно вычислить число x как x =
n +y2 ;
полученное x будет больше n .
Описание алгоритма.
На вход подается нечетное натуральное число n.
На выходе ожидается: 2 сомножителя числа n или сообщение о невозможности разложить число n с помощью алгоритма.
1. Пусть x = ] n [, где ]…[ - операция взятия целой части от аргумента. Если n = x2, то x является делителем числа n; выход.
2. Выполнить x = x + 1.
3. Если выполняется равенство
раскладывается на множители, выход.
x =(n +1) , то число n - простое и не
2
4. Вычислить y =
x 2 -n .
5. Если ] y2[ = (x2 - n), то n раскладывается на множители (x − y) и
(x + y), выход.
6. Иначе перейти к шагу 2.
Покажем истинность шага 3 алгоритма Ферма. Предположим, что число n можно представить в виде произведения n = ab, где a ≤ b. Алгоритм
ищет такие целые числа x и y, которые удовлетворяют равенству
n = ab = (x2−y2) =
= (x−y)(x+y).
Так как a = (x-y), b = (x+y) и a ≤ b, то (x-y) ≤ (x+y). Выразим неизвестные
x и y из системы
ìa =x -y
í
îb =x +y
ìx =(b +a) / 2
=> í
îy =(b -a) / 2
. Действительно, подставляя
значения x и y в выражение (x2 - y2), получим
0.25(b + a)2 + 0.25(b - a)2 = 0.25(b 2+ 2ab + a 2- b 2+ 2ab - a 2) = ab , что равно
n.
Если число n - нечетное (так как предположительно n - простое), то его
2 сомножителя a и b также являются нечетными числами. Так как сумма и разность двух нечетных чисел являются четными, то числа (a + b) и (a − b) - четные.
Если n является простым числом, то единственными его сомножителями являются числа a = 1 и b = n. Тогда x = (a + b)/2 = (n + 1)/2 и
y = (n − 1)/2.
Так как (x2-y2) = n, то y2 = x2 - n или y =
x 2 -n . Покажем, что при
указанных условиях нацело извлекается квадратный корень, если
x = (n + 1)/2:
y = x 2 -n =
0.25(n +1)2 -n =0.5
n2 +2n +1 -4n =
=0.5
n2 -2n +1 =0.5
(n -1)2
=0.5(n -1) .
Пример 1.6. Разложим число n = 1472861 на множители.
Присвоим x = ] n [ = 1213. При этом x2 < n, то есть
12132 = 1471369 < 1472861. Увеличим x на единицу. Данный процесс будет
продолжен до тех пор, пока число y =
x 2 -n
не станет целым или не
выполнится равенство
x =(n +1) . Выражение
2
(n + 1)
2
равно 736431.
Шаги работы алгоритма представим в виде трассировочной табл. 1.6.
Таблица 1.6. Трассировочная таблица
№ шага | x | x =(n +1) | y = x 2 - n | y ÎZ? |
нет | 9351/2 ≈ 30.57 | нет | ||
нет | да |
На втором шаге было получено целое число y. Искомыми числами x и y
являются 1215 и 58. Тогда множителями числа n являются числа
(x − y) = 1157 и (x + y) = 1273.
Дополнительные примеры для решения (решить обоими способами):
1. Разложите число n = 391 на 2 сомножителя. (n1=17 и n2=23).
3. Разложите число n = 111 на 2 сомножителя. (n1=3 и n2=37).
4. Разложите число n = 115 на 2 сомножителя. (n1=5 и n2=23).
5. Рассмотрите примеры 1.4-1.6 с помощью алгоритма Ферма. Вопросы для самопроверки.
1. В чем заключается идея алгоритма Бухштаба?
2. В чем заключается идея алгоритма Ферма?
3. Какие общие арифметические операции присутствуют в обоих алгоритмах?
4. Поясните, для чего используется арифметическая прогрессия в алгоритме
Бухштаба?
5. Почему, при выполнении равенства простое?
x = (n + 1) / 2 , принимается, что число n -
6. Для каких чисел применимы алгоритмы?
7. В каких диапазонах ищутся результаты разложения?