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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 5. Метод решета числового поля 161
элементов M , и f
0
(s) 6≡ 0 ( mod q), тогда
Y
x∈S
a − bs
q
= 1. (5.142)
Если произведение
Q
x∈S
(a − bx) не является полным квадратом, то
найдется пара чисел (q, s), удовлетворяющая условию теоремы, для которой
символ Лежандра (a − bs/q) окажется равным 0. Квадратичная факторная
база, состоящая из подобных пар (q, s), как раз и предназначена для того,
чтобы предотвратить такую возможность. Поскольку мы не можем проверить
условие (5.142) на бесконечном множестве пар, то существует вероятность,
что найденное в ходе просеивания множество S , не дает полный квадрат, но с
ростом размера квадратичной факторной базы, такая вероятность стремится
к нулю.
Таким образом, при достаточном большом размере факторной базы
квадратичных характеров, единицы поля K[θ] будут входить в многочлен
g(x) только в четной степени.
3. Третьей причиной, по которой g(x) может не быть полным
квадратом, заключается в том, что теорема об однозначном разложении
целых алгебраических чисел выполняется в кольце идеалов кольца Z
K
,
а идеалы Z
K
не всегда являются главными, т.е. не могут порождаться
элементом вида a − bθ , a, b ∈ Z.
5.4. Вычисление квадратного корня
Как только множество M пар целых чисел (a, b), образующих решение,
найдено, необходимо вычислить многочлен α(x), квадрат которого равен
g(x) = (f
0
(x))
2
·
Y
x∈S
(a − bx) (5.143)
Заметим, что подобной задачи не было ни в одном из предыдущих
методов факторизации, включая метод квадратичного решета, и она
появляется только в методе решета числового поля. При небольших
значений коэффициентов вычисление квадратного корня в кольце
Глава 5. Метод решета числового поля                                           161

элементов M , и f 0 (s) 6≡ 0 ( mod q), тогда
                Y a − bs
                                 = 1.                                       (5.142)
                           q
                  x∈S
                            Q
      Если произведение         x∈S (a   − bx) не является полным квадратом, то
найдется пара чисел (q, s), удовлетворяющая условию теоремы, для которой
символ Лежандра (a − bs/q) окажется равным 0. Квадратичная факторная
база, состоящая из подобных пар (q, s), как раз и предназначена для того,
чтобы предотвратить такую возможность. Поскольку мы не можем проверить
условие (5.142) на бесконечном множестве пар, то существует вероятность,
что найденное в ходе просеивания множество S , не дает полный квадрат, но с
ростом размера квадратичной факторной базы, такая вероятность стремится
к нулю.
      Таким образом, при достаточном большом размере факторной базы
квадратичных характеров, единицы поля K[θ] будут входить в многочлен
g(x) только в четной степени.

      3. Третьей причиной, по которой g(x) может не быть полным
квадратом, заключается в том, что теорема об однозначном разложении
целых алгебраических чисел выполняется в кольце идеалов кольца ZK ,
а идеалы ZK не всегда являются главными, т.е. не могут порождаться
элементом вида a − bθ , a, b ∈ Z.


5.4. Вычисление квадратного корня
Как только множество M пар целых чисел (a, b), образующих решение,
найдено, необходимо вычислить многочлен α(x), квадрат которого равен
                                 Y
                        0   2
             g(x) = (f (x)) ·          (a − bx)                             (5.143)
                                 x∈S

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

Страницы