Алгоритм Бухштаба

 

Данный алгоритм приведен из книги Бухштаба А.А. "Теория чисел" [4]. Пусть задано натуральное нечетное число n, n ≥ 9, которое необходимо разложить на 2 простых сомножителя. Зададим ряд чисел Ns (s - нуль и натуральное число), где на каждом шаге к Ns прибавляются числа в порядке

возрастания: для вычисления Ns к Ns−1 прибавляется число (2s-1).

 

Тогда итеративно вычислим элементы Ns по формуле Ns=Ns-1+2s-1:

 

N0=n

 

N1=N0+1

 

N2=N1+3

 

N3=N2+5

 

……

 

Ns=Ns-1+2s-1

 

……

 

Прибавляемые к Ns числа являются членами арифметической прогрессии:

- начальный элемент равен a0=1,

 

- последний - as=2s-1,

 

- число членов - m=s

 

- шаг прогрессии равен 2.


 

Тогда сумма чисел прибавленных к n равна (по формуле суммы арифметической прогрессии) Sпрогрес= (a1 +as )m/2=(1+2s-1)s/2=2s2/2= s2.

В результате элемент Ns равен Ns = N0 + Sпрогрес = n + Sпрогрес= n + s2.

 

Предположим, что из Ns извлекается нацело квадратный корень, то есть Ns = t2, где t - некоторое натуральное число, тогда Ns = t2= n + s2 Þ n = Ns − s2 = t2 − s2.

Таким образом, если при некотором s будет возможно извлечение нацело квадратного корня из Ns = t2, то исходное число n раскладывается как

n=(t2−s2)=(ts)(t+s).

 

ù=n -9 é 2 2


Если в диапазоне для s: 1≤s≤ úû 6


ëêне будет найдено t , где из t


 

нацело извлекается квадратный корень, то процесс поиска двух сомножителей числа n завершается - число n является простым или алгоритм не применим для него.

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

 

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

 

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

1. Ввод числа n. Если n<9, то задача данным алгоритмом не решается. Выход.

2. N=n.

 

ùn -9 é


3. Для "s =1, úû


6 êë


выполнить:


 

3.а. N=N+2s-1.

 

3.б. t =] N [ .

 

3.в. Если t2=N, то

 

вывод чисел (t-s) и (t+s); Выход из алгоритма.

 

4. Разложить число n не удалось. Выход из алгоритма.


 


Пример 1.4. Пусть n = 69.


 

Таблица 1.4. Трассировочная таблица


 

  Шаг, s ù=n -9 é Условие:s £úû 6 êë?   N = N+2s-1   t =] N [   Условие: t =N?
да: 1≤10 нет: 64≠70
да: 2≤10 нет: 64≠73
да: 3≤10 нет: 64≠78
да: 4≤10 нет: 81≠85
да: 5≤10 нет: 81≠94
да: 6≤10 нет: 100≠105
да: 7≤10 нет: 100≠118
да: 8≤10 нет: 121≠133
да: 9≤10 нет: 144≠150
да: 10≤10 да: 169=169

ù=n -9 é


N0=n=69; максимальное число шагов:


s £úû 6


êë=10 . Шаги работы


 

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

 

Из числа N10= 169 можно извлечь квадратный корень: t2=13. Тогда

 

n = (t2 − s2) =(t s)? (t + s)=(13-10)? (13+10) = 3? 23.

 

Т.е. число 69 раскладывается на два числа: 3 и 23.

 

 


Пример 1.5. Пусть n = 23.


 

ù=n -9 é


N0 = n = 23; максимальное число шагов: s ≤ úû 6


ëê= 2.


 

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

 

Таблица 1.5. Трассировочная таблица

 

  Шаг, s n -9 Условие: s £ ?   N = N+2s-1   t =] N [   Условие: t 2 =N?
да: 1≤2 Нет: 16≠24
да: 2≤2 Нет: 25≠27
нет: 3>2 - - -

Таким образом, число 23 не раскладывается алгоритмом Бухштаба на 2

 

простых сомножителя.