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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 5. Метод решета числового поля 152
Теорема 5.1. Множество простых идеалов кольца Z
K
находится во
взаимно–однозначном соответствии с множеством пар положительных
целых чисел (p, r) таких, что p–простое число, 0 ≤ r < p, и f
1
(r) ≡
0 ( mod p).
Благодаря этому результату, можно не выписывать явно простые
идеалы кольца Z
K
, а просто установить границу B
1
и искать все пары (p, r),
где p ≤ B
1
–простое число, а r ∈ [0, p − 1], и f
1
(r) mod p = 1.
В нашем примере установим границу B
1
= 103. Элементы F B
1
можно
найти простым перебором (табл.1).
Таблица 1
Алгебраическая факторная база
(p, r) (p, r) (p, r) (p, r)
(2, 0) (41,19) (67,44) (89,62)
(7, 6) (43,13) (73,50) (89,73)
(17,13) (53,1) (79,23) (97,28)
(23,11) (61,46) (79,47) (101,87)
(29,26) (67,2) (79,73) (103,47)
(31,18) (67,6) (89,28)
Простой перебор всех допустимых пар работает неэффективно для
больших чисел p. Опишем здесь один алгоритм, позволяющий улучшить
поиск корней многочлена f
1
(x) mod p. Этот алгоритм основывается на
следующей теореме:
Теорема 5.2. В конечном поле GF
q
= GF
p
k
многочлен x
q
− x полностью
раскладывается на линейные множители
x
q
− x =
q−1
Y
i=0
(x − i). (5.134)
Алгоритм вычисления корней по модулю простого числа p работает
следующим образом:
Глава 5. Метод решета числового поля                                     152

Теорема 5.1. Множество простых идеалов кольца ZK находится во
взаимно–однозначном соответствии с множеством пар положительных
целых чисел (p, r) таких, что p–простое число, 0 ≤ r < p, и f1 (r) ≡
0 ( mod p).

      Благодаря этому результату, можно не выписывать явно простые
идеалы кольца Z K , а просто установить границу B1 и искать все пары (p, r),
где p ≤ B1 –простое число, а r ∈ [0, p − 1], и f1 (r) mod p = 1.
      В нашем примере установим границу B1 = 103. Элементы F B1 можно
найти простым перебором (табл.1).

                                                                   Таблица 1
                         Алгебраическая факторная база
                         (p, r)   (p, r)   (p, r)    (p, r)
                         (2, 0)   (41,19) (67,44)    (89,62)
                         (7, 6)   (43,13) (73,50)    (89,73)
                     (17,13)      (53,1)   (79,23)   (97,28)
                     (23,11) (61,46) (79,47) (101,87)
                     (29,26)      (67,2)   (79,73) (103,47)
                     (31,18)      (67,6)   (89,28)

      Простой перебор всех допустимых пар работает неэффективно для
больших чисел p. Опишем здесь один алгоритм, позволяющий улучшить
поиск корней многочлена f1 (x) mod p. Этот алгоритм основывается на
следующей теореме:

Теорема 5.2. В конечном поле GFq = GFpk многочлен xq − x полностью
раскладывается на линейные множители
                q−1
                Y
              q
          x −x=     (x − i).                                          (5.134)
                   i=0


      Алгоритм вычисления корней по модулю простого числа p работает
следующим образом:

Страницы