Алгоритм Ферма

 

Алгоритм Ферма похож на алгоритм Бухштаба и является эффективным, если у раскладываемого числа 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) =

 

= (xy)(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. В каких диапазонах ищутся результаты разложения?