Методы факторизации натуральных чисел. Ишмухаметов Ш.Т. - 78 стр.

UptoLike

ВУЗ: 

КФУ | Казань

Составители: 

Рубрика: 

Глава 2. Простые алгоритмы факторизации 79
3. Вычислим квадратный корень из f по формулам (2.54):
g = (a
0
, b
0
, c
0
) = f
1/2
4. Выполним цикл редуцирований g = ρ(g), пока значение второго
коэффициента не стабилизируется b
0
i+1
= b
0
i
. Число итераций m этого
цикла должно быть примерно равно половине от числа итераций
первого цикла. Последнее значение a
0
даст делитель числа n (возможно
тривиальный).
Дадим теперь полное описание этого алгоритма с соответствующими
формулами. Отметим, что хотя теоретическая часть алгоритма связана
с эквивалентными преобразования квадратичных форм, практическая
часть алгоритма выполняется по формулам (2.44)–(2.46) вычисления
коэффициентов P, Q и r метода непрерывных дробей без обращения к
формам. Каждая итерация цикла соответствует одной операции применения
оператора редукции к соответствующей форме. При необходимости можно
восстановить соответствующие формы f
k
= (a
k
, b
k
, c
k
) по формулам:
(a
k
, b
k
, c
k
) =
(−1)
k−1
Q
k−1
, 2P
k
, (−1)
k
Q
k
(2.55)
Ниже мы дадим описание алгоритма SQUFOF для практической
реализации:
Алгоритм SQUFOF нахождения нетривиального делителя n
Вход: Составное число n.
Выход: Нетривиальный делитель n.
I. Инициализация алгоритма.
1. Проверим, является ли n полным квадратом. Если да, то вычислим d =
√
n, и завершим вычисление. Иначе, перейдем к следующему пункту.
2. Если n ≡ 1 (mod 4), тогда заменим n на 2n. Определим D = 4n, q
0
=
b
√
Dc.
Глава 2. Простые алгоритмы факторизации                                   79

  3. Вычислим квадратный корень из f по формулам (2.54):
     g = (a0 , b0 , c0 ) = f 1/2

  4. Выполним цикл редуцирований g = ρ(g), пока значение второго
     коэффициента не стабилизируется b0i+1 = b0i . Число итераций m этого
     цикла должно быть примерно равно половине от числа итераций
     первого цикла. Последнее значение a0 даст делитель числа n (возможно
     тривиальный).


      Дадим теперь полное описание этого алгоритма с соответствующими
формулами. Отметим, что хотя теоретическая часть алгоритма связана
с эквивалентными преобразования квадратичных форм, практическая
часть алгоритма выполняется по формулам (2.44)–(2.46) вычисления
коэффициентов P, Q и r метода непрерывных дробей без обращения к
формам. Каждая итерация цикла соответствует одной операции применения
оператора редукции к соответствующей форме. При необходимости можно
восстановить соответствующие формы fk = (ak , bk , ck ) по формулам:

      (ak , bk , ck ) = (−1)k−1 Qk−1 , 2Pk , (−1)k Qk
                                                        
                                                                       (2.55)

      Ниже мы дадим описание алгоритма SQUFOF для практической
реализации:

Алгоритм SQUFOF нахождения нетривиального делителя n

Вход: Составное число n.
Выход: Нетривиальный делитель n.
I. Инициализация алгоритма.

  1. Проверим, является ли n полным квадратом. Если да, то вычислим d =
     √
       n, и завершим вычисление. Иначе, перейдем к следующему пункту.

  2. Если n ≡ 1 (mod 4), тогда заменим n на 2n. Определим D = 4n, q0 =
      √
     b Dc.

Страницы