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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 5. Метод решета числового поля 149
множества M , состоящего из гладких пар (a, b). Пара (a, b)
называется гладкой, если Н.О.Д.(a, b) = 1, и полином a − bθ и
число a − bm раскладываются полностью по соответствующим
факторным базам F B
1
и F B
2
. Число гладких пар в множестве
M должно превышать суммарную мощность трех факторных баз,
по-крайней мере, на две единицы.
11. На следующем шаге ищется подмножество S ⊆ M такое, что
произведение всех пар
Y
(a,b)∈S
Nr(a − bθ) = H
2
, для H ∈ Z, и
Y
(a,b)∈S
(a − bm) = B
2
, B ∈ Z.
Для нахождения множества S составляется, как и в методе
квадратичного решета, система линейных алгебраических уравнений с
коэффициентами из множества F
2
= {0, 1}, решением которой и будут
номера множества S .
12. Далее формируем многочлен
g(θ) = (f
0
1
(θ))
2
·
Y
(a,b)∈S
(a − bθ), (5.132)
где f
0
1
(x)–производная многочлена f
1
(x).
13. Если вся процедура была выполнена корректно, то многочлен g(θ)
является полным квадратом в кольце полиномов Z[θ]. Извлекаем
квадратные корни из многочлена g(θ) и целого числа B
2
, находя
некоторый многочлен α(θ) и число B .
14. Заменяем многочлен α(θ) числом α(m). Отображение φ : θ → m
является кольцевым гомоморфизмом кольца алгебраических целых
чисел Z
K
в кольцо Z, откуда получим соотношение:
A
2
= g(m)
2
≡ (φ(g(α)
2
) ≡ φ
(f
0
1
(θ))
2
·
Y
(a,b)∈S
(a − bθ)
≡
≡ (f
0
1
(m))
2
·
Y
(a,b)∈S
(a−bm) ≡ (f
0
1
(m))
2
·C
2
( mod n ) (5.133)
Глава 5. Метод решета числового поля                                                    149

     множества M , состоящего из гладких пар                           (a, b). Пара (a, b)
     называется гладкой, если Н.О.Д.(a, b) = 1, и полином a − bθ и
     число a − bm раскладываются полностью по соответствующим
     факторным базам F B1 и F B2 . Число гладких пар в множестве
     M должно превышать суммарную мощность трех факторных баз,
     по-крайней мере, на две единицы.

 11. На следующем шаге ищется подмножество S                            ⊆ M такое, что
     произведение всех пар
        Y                                                 Y
            N r(a − bθ) = H 2 , для H ∈ Z, и                       (a − bm) = B 2 , B ∈ Z.
       (a,b)∈S                                           (a,b)∈S

     Для нахождения множества                    S   составляется, как и в методе
     квадратичного решета, система линейных алгебраических уравнений с
     коэффициентами из множества F2 = {0, 1}, решением которой и будут
     номера множества S .

 12. Далее формируем многочлен
                          Y
                 0     2
        g(θ) = (f1 (θ)) ·   (a − bθ),                                                (5.132)
                                   (a,b)∈S

     где f10 (x)–производная многочлена f1 (x).

 13. Если вся процедура была выполнена корректно, то многочлен g(θ)
     является полным квадратом в кольце полиномов Z[θ]. Извлекаем
     квадратные корни из многочлена g(θ) и целого числа B 2 , находя
     некоторый многочлен α(θ) и число B .

 14. Заменяем многочлен α(θ) числом α(m). Отображение φ : θ → m
     является кольцевым гомоморфизмом кольца алгебраических целых
     чисел ZK в кольцо Z, откуда получим соотношение:
                                                        
                                               Y
     A2 = g(m)2 ≡ (φ(g(α)2 ) ≡ φ (f10 (θ))2 ·   (a − bθ) ≡
                                                       (a,b)∈S
                        Y
      ≡ (f10 (m))2 ·             (a−bm) ≡ (f10 (m))2 ·C 2 ( mod n )                  (5.133)
                       (a,b)∈S

Страницы