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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 5. Метод решета числового поля 159
полным квадратом, то его Nr(g(x)) будет полным квадратом в кольце целых
чисел Z. Однако обратное соотношение верно не всегда.
Пример. Рассмотрим числовое поле Q[
√
3], получаемое при
рассмотрении неприводимого полинома f(x) = x
2
− 3. Элемент v = 2 +
√
3
принадлежит Q[
√
3] и имеет координаты (2, 1) в базисе B = (1;
√
3). Его
норма, определяемая по формуле (А.169), равна Nr(v) = v
2
1
−3v
2
2
= 1. Таким
образом, норма элемента является полным квадратом в Z , а сам полином
v не является квадратом в Q[
√
3], т.к. v = w
2
для w = (
√
6 +
√
2)/2, и
w 6∈ Q[
√
3]. Рассмотрим причины, по которым это может произойти:
1. Первая причина состоит в том, что теорема об однозначном
разложении (теор. А.7) выполняется в кольце целых алгебраических чисел
Z
K
поля Q[θ], а мы работает в меньшем кольце полиномов с целыми
коэффициентами Z[θ] от переменной θ , являющемся в общем случае
собственным подмножеством кольца Z
K
.
Пример. В поле K = Q[
√
5] элемент g = (−1 +
√
5)/2 является
целым, т.к. он является корнем минимального многочлена f(x) = x
2
+ x −1,
однако не принадлежит кольцу Z[
√
5].
К счастью, эту причину можно устранить, воспользовавшись
следующей теоремой:
Теорема 5.3. Пусть K = Q[θ] – алгебраическое числовое поле, полученное
присоединением к Q корня неприводимого в Q многочлена f(x). Тогда для
любого полинома α(x), принадлежащего кольцу Z
K
, многочлен h(x) =
α(x) · f
0
(x) принадлежит кольцу Z[α], где f
0
(x)–производная многочлена
f(x).
Значит, чтобы устранить неполноту кольца Z[θ] в GNFS, достаточно
домножить многочлен γ(x) =
Q
x∈S
(a −bα) на квадрат производной f
1
(x):
g(x) = (f
0
1
(x))
2
· γ(x). (5.139)
Вычислим значение многочлена g(x) для нашего базового примера
n = 45113:
g(x) = (f
0
1
(x))
2
·γ(x) = (3x
2
+30x+29)
2
·
Y
x∈S
(a−bx) ≡
Глава 5. Метод решета числового поля                                   159

полным квадратом, то его N r(g(x)) будет полным квадратом в кольце целых
чисел Z. Однако обратное соотношение верно не всегда.
                                                  √
       Пример. Рассмотрим числовое поле Q[ 3], получаемое при
                                                                   √
рассмотрении неприводимого полинома f (x) = x2 − 3. Элемент v = 2 + 3
               √                                              √
принадлежит Q[ 3] и имеет координаты (2, 1) в базисе B = (1; 3). Его
норма, определяемая по формуле (А.169), равна N r(v) = v12 −3v22 = 1. Таким
образом, норма элемента является полным квадратом в Z , а сам полином
                             √                          √    √
v не является квадратом в Q[ 3], т.к. v = w2 для w = ( 6 + 2)/2, и
       √
w 6∈ Q[ 3]. Рассмотрим причины, по которым это может произойти:
         1. Первая причина состоит в том, что теорема об однозначном
разложении (теор. А.7) выполняется в кольце целых алгебраических чисел
Z K поля Q[θ], а мы работает в меньшем кольце полиномов с целыми
коэффициентами Z[θ] от переменной θ , являющемся в общем случае
собственным подмножеством кольца Z K .
                               √                  √
        Пример. В поле K = Q[ 5] элемент g = (−1 + 5)/2 является
целым, т.к. он является корнем минимального многочлена f (x) = x2 + x − 1,
                                 √
однако не принадлежит кольцу Z[ 5].
         К счастью, эту причину можно устранить, воспользовавшись
следующей теоремой:
Теорема 5.3. Пусть K = Q[θ] – алгебраическое числовое поле, полученное
присоединением к Q корня неприводимого в Q многочлена f (x). Тогда для
любого полинома α(x), принадлежащего кольцу Z K , многочлен h(x) =
α(x) · f 0 (x) принадлежит кольцу Z[α], где f 0 (x)–производная многочлена
f (x).
     Значит, чтобы устранить неполноту кольца Z[θ] в GNFS, достаточно
                           Q
домножить многочлен γ(x) = x∈S (a − bα) на квадрат производной f1 (x):

                 g(x) = (f10 (x))2 · γ(x).                          (5.139)

         Вычислим значение многочлена g(x) для нашего базового примера
n = 45113:
                                                 Y
g(x) =   (f10 (x))2 ·γ(x)       2
                            = (3x +30x+29) · 2
                                                       (a−bx) ≡
                                                 x∈S

Страницы