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

Алгоритм Ферма похож на алгоритм Бухштаба и являетсяэффективным,еслиураскладываемогочислаnестьделитель(который

можетинебытьпростымчислом),незначительнопревосходящий n.

Пустьчислоnявляетсянечетным.Алгоритмзаключаетсявтом,чтобыпредставитьчислоnввиде

n=x²⁻y²⁼(x−y)(x+y),

гдеx,y-неотрицательныецелыечисла.Есличислаxиyнайдены,то

(x−y)и(x+y)являютсяпростымиделителямичислаn.

_{Есличислоy=0,тоделителемчислаnявляется n.}

_{Еслиизвестноyиy>0,можновычислитьчислоxкакx}

_ny²_;

полученноеxбудетбольше n.

Описаниеалгоритма.

Навходподаетсянечетноенатуральноечислоn.

Навыходеожидается:2сомножителячислаnилисообщениеоневозможностиразложитьчислоnспомощьюалгоритма.

1.Пустьx=] n[,где]…[-операциявзятияцелойчастиотаргумента.Еслиn=x²,тоxявляетсяделителемчислаn;выход.

_{2.Выполнитьx=x+1.}

3.Есливыполняетсяравенство

_{раскладываетсянамножители,выход.}

_x^(n1)_{,точислоn-простоеине}

²

_{4.Вычислитьy}

_x²_n.

5.Если]y²[=(x^2-n),тоnраскладываетсянамножители(x−y)и

(x+y),выход.

6.Иначеперейтикшагу2.

Покажемистинностьшага3алгоритмаФерма.Предположим,чточислоnможнопредставитьввидепроизведенияn=ab,гдеa≤b.Алгоритм

ищет такие целые числа x и y, которые удовлетворяют равенству

n=ab=(x²−y²)=

=(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ввыражение(x^2-y²),получим

0.25(ba)^20.25(ba)^20.25(b^22aba^2b^22aba²⁾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.

_{Таккак(x}²_-y²_)=n,тоy²_=x²_{-nили y}

_x²_{n.Покажем,чтопри}

указанных условиях нацело извлекается квадратный корень, если

_x=(n+1)/2:

_{y x}²_n

_0.25(n1)²_n0.5

_n²_{2n14n}

_0.5

_n²_{2n10.5}

_(n1)²

_{0.5(n1).}

Пример1.6.Разложимчислоn=1472861намножители.

Присвоим x=] n[=1213. При этом x^2<n, тоесть

₁₂₁₃²_{=1471369<1472861.Увеличимxнаединицу.Данныйпроцессбудет}

_{продолжендотехпор,покачисло y}

_x²_n

_{нестанетцелымилине}

выполнитсяравенство

_x^(n1)_{.Выражение}

²

(n1)

₂

равно736431.

Шагиработыалгоритмапредставимввидетрассировочнойтабл.1.6.

_{Таблица1.6.Трассировочнаятаблица}

№шага	x	x(n1) 2	y x2n	yZ?
1	1214	нет	9351/2≈30.57	нет
2	1215	нет	58	да

Навторомшагебылополученоцелоечислоy.Искомымичисламиxиy

являются 1215 и 58. Тогда множителями числа n являются числа

(x−y)=1157и(x+y)=1273.

Дополнительныепримерыдлярешения(решитьобоимиспособами):

1.Разложитечислоn=391на2сомножителя.(n₁=17иn₂=23).

3.Разложитечислоn=111на2сомножителя.(n₁=3иn₂=37).

4.Разложитечислоn=115на2сомножителя.(n₁=5иn₂=23).

5.Рассмотритепримеры1.4-1.6спомощьюалгоритмаФерма.Вопросыдлясамопроверки.

1.ВчемзаключаетсяидеяалгоритмаБухштаба?

2.ВчемзаключаетсяидеяалгоритмаФерма?

3.Какиеобщиеарифметическиеоперацииприсутствуютвобоихалгоритмах?

4.Поясните,длячегоиспользуетсяарифметическаяпрогрессиявалгоритме

_{Бухштаба?}

5.Почему,привыполненииравенствапростое?

x(n1)/2,принимается,чточислоn-

6.Длякакихчиселприменимыалгоритмы?

7.Вкакихдиапазонахищутсярезультатыразложения?