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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 5. Метод решета числового поля 175
2. Стадии просеивания, формирования системы линейных уравнений
и построения множества S гладких пар (a, b) не изменятся.
3. Изменится формула (5.132) для определения g
2
(x), как полинома с
целыми коэффициентами степени d − 1:
g
2
(θ) = (f
0
1
(θ)/c
d
)
2
·
Y
(a,b)∈S
(c
d
a − bθ) (5.161)
4. Извлечение квадратного корня g(x) по модулю многочлена f
1
(x)
остается прежним. Вычисляем коэффициенты g(x) и число v :
g(x) =
d−1
Y
i=0
b
i
x
i
, v =
d−1
Y
i=0
b
i
m
i
1
m
d−1−i
2
mod n. (5.162)
5. Вычисляем число D
2
и C :
D
2
=
Y
(a,b)∈S
(am
1
− bm
2
θ), C = D mod n. (5.163)
6. Вычисляем числа A = m
#S/2
2
·v mod n и B = c
d−2+#S/2
d
·C mod n.
7. Находим делители n, вычисляя Н.О.Д.(n, A ± B).
5.8. Заключение
Мы завершили описание основных алгоритмов вычислительной теории
чисел, связанных с факторизацией. Нельзя считать эту тему закрытой,
поскольку многие крупные открытия и новые достижения в этой области
появляются снова и снова. Эти достижения обусловлены не только развитием
вычислительной мощности компьютеров и сетей, но и развитием тех
областей теоретической математики, которые до недавнего времени служили
областью интересов лишь профессиональных математиков– специалистов в
абстрактной алгебре и теории чисел.
Задачи элементарной теории чисел, вычислительные задачи
криптографии подстегивает интерес большого круга лиц к математике
и теории чисел, превращая их из дилетантов в профессионалы. Я надеюсь,
что эта книга послужит решению этой важной задачи.
Глава 5. Метод решета числового поля                                                     175

      2. Стадии просеивания, формирования системы линейных уравнений
и построения множества S гладких пар (a, b) не изменятся.
      3. Изменится формула (5.132) для определения g 2 (x), как полинома с
целыми коэффициентами степени d − 1:
                                 Y
   g 2 (θ) = (f10 (θ)/cd )2 ·             (cd a − bθ)                                 (5.161)
                                (a,b)∈S

      4. Извлечение квадратного корня g(x) по модулю многочлена f1 (x)
остается прежним. Вычисляем коэффициенты g(x) и число v :
          d−1
          Y                     d−1
                                Y
                    i
 g(x) =         bi x ,    v=          bi mi1 md−1−i
                                              2     mod n.                            (5.162)
          i=0                   i=0

      5. Вычисляем число D2 и C :
          Y
  D2 =             (am1 − bm2 θ),          C = D mod n.                               (5.163)
         (a,b)∈S

                                               #S/2                    d−2+#S/2
      6. Вычисляем числа A = m2                       · v mod n и B = cd          · C mod n.
      7. Находим делители n, вычисляя Н.О.Д.(n, A ± B).


5.8. Заключение
Мы завершили описание основных алгоритмов вычислительной теории
чисел, связанных с факторизацией. Нельзя считать эту тему закрытой,
поскольку многие крупные открытия и новые достижения в этой области
появляются снова и снова. Эти достижения обусловлены не только развитием
вычислительной мощности компьютеров и сетей, но и развитием тех
областей теоретической математики, которые до недавнего времени служили
областью интересов лишь профессиональных математиков– специалистов в
абстрактной алгебре и теории чисел.
      Задачи            элементарной         теории      чисел,   вычислительные      задачи
криптографии подстегивает интерес большого круга лиц к математике
и теории чисел, превращая их из дилетантов в профессионалы. Я надеюсь,
что эта книга послужит решению этой важной задачи.

Страницы