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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 4. Метод квадратичного решета 124
Учитывая равенство q(x) ≡ 0 (mod p
k
), поделим последнее уравнение
на p
k
. Получим:
f + 2(x + m)r ≡ 0 (mod p),
где f – остаток от деления q(x)/p
k
на p.
Если f = 0, тогда r = 0 и y = x. В противном случае, с помощью
расширенного алгоритма Евклида следует вычислить элемент u, обратный
к элементу 2(x + m) в поле F
p
, тогда решение y находится по формуле:
y = x − ufp
k+1
. (4.103)
II. Процедура просеивания
В ходе инициализации процедуры просеивания выбирается радиус
просеивания L. Далее формируется массив W действительных чисел
размерности 2L. Вместо значений многочлена q(x) в массив W будем
помещать логарифмы значений q(x): W [x] = logq(x) ≈ log(2m) + logx при
x ∈ [−L; L], взятые с небольшой точностью. Позднее мы оценим допустимую
погрешность вычисления логарифма. Для нашего примера, когда n имеет 34
десятичных разряда, в значении логарифма достаточно брать два знака после
десятичной точки.
Сама организация просеивания не имеет каких-то особых трудностей,
а представляет собой двойной цикл в ходе которого перебираются все простые
числа из факторной базы, для каждого из которых потом выполняется цикл
по элементам массива W . Например, если тройка < 19, 3, 10 > принадлежит
факторной базе FB, это означает, что на 19 делятся q(3), q(10), а также все
q(y), y ∈ [−L, L], y ≡ 3 mod 19 или y ≡ 10 mod 19. Можно организовать
вычисление, найдя наименьшее x ≡ 3 mod 19, большее −L, вычесть из W [x]
log19, затем, присвоив x новое значение x+19, опять вычесть из W [x] log19
и т.д. пока не дойдем до правого конца интервала [−L, L].
После окончания просеивания по первым степеням элементов
факторной базы, следует перейти к их степеням. Пусть, например, кортеж
< 19, 22, 105, 2 > принадлежит таблице степеней факторной базы. Тогда все
числа q(x) такие, что x ≡ 22 mod 361 или x ≡ 105 mod 361 делятся на
Глава 4. Метод квадратичного решета                                     124

      Учитывая равенство q(x) ≡ 0 (mod pk ), поделим последнее уравнение
на pk . Получим:
                        f + 2(x + m)r ≡ 0 (mod p),

где f – остаток от деления q(x)/pk на p.
      Если f = 0, тогда r = 0 и y = x. В противном случае, с помощью
расширенного алгоритма Евклида следует вычислить элемент u, обратный
к элементу 2(x + m) в поле Fp , тогда решение y находится по формуле:

                       y = x − uf pk+1 .                            (4.103)


     II. Процедура просеивания
      В ходе инициализации процедуры просеивания выбирается радиус
просеивания L. Далее формируется массив W действительных чисел
размерности 2L. Вместо значений многочлена q(x) в массив W будем
помещать логарифмы значений q(x): W [x] = logq(x) ≈ log(2m) + logx при
x ∈ [−L; L], взятые с небольшой точностью. Позднее мы оценим допустимую
погрешность вычисления логарифма. Для нашего примера, когда n имеет 34
десятичных разряда, в значении логарифма достаточно брать два знака после
десятичной точки.
      Сама организация просеивания не имеет каких-то особых трудностей,
а представляет собой двойной цикл в ходе которого перебираются все простые
числа из факторной базы, для каждого из которых потом выполняется цикл
по элементам массива W . Например, если тройка < 19, 3, 10 > принадлежит
факторной базе FB, это означает, что на 19 делятся q(3), q(10), а также все
q(y), y ∈ [−L, L], y ≡ 3 mod 19 или y ≡ 10 mod 19. Можно организовать
вычисление, найдя наименьшее x ≡ 3 mod 19, большее −L, вычесть из W [x]
log19, затем, присвоив x новое значение x+19, опять вычесть из W [x] log19
и т.д. пока не дойдем до правого конца интервала [−L, L].
      После окончания просеивания по первым степеням элементов
факторной базы, следует перейти к их степеням. Пусть, например, кортеж
< 19, 22, 105, 2 > принадлежит таблице степеней факторной базы. Тогда все
числа q(x) такие, что x ≡ 22 mod 361 или x ≡ 105 mod 361 делятся на

Страницы