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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 5. Метод решета числового поля 157
Первая координата отражает знак числа и равно 0 для положительных
a −bm, и 1, для отрицательных.
Аналогично для алгебраической факторной базы
Nr(a, b) = F
1
(8, 3) = 5696 = 2
6
·89
1
.
Полная длина вектора разложения равна 24.
Формирование системы линейных уравнений
В предыдущем разделе была описана процедура просеивания, в
результате которой было получено множество S гладких пар (a, b), а
также разложения значений F
1
(a, b) и F
2
(a, b) в произведения элементов
факторных баз F B
1
и F B
2
.
Для формирования системы линейных уравнений нам также
понадобится вычислить значение квадратичного характера для каждой
пары (a, b) ∈ S и каждой пары (p, r) из квадратичной факторной базы.
Это означает, что для всех (a, b) ∈ S , (p, r) ∈ F B
3
, мы должны вычислить
символ Лежандра
a − br
p
. (5.137)
Теперь можно сформировать матрицу системы. Она будет содержать
|S| строк по числу найденных гладких пар. Каждая строка содержит k =
s
1
+ s
2
+ s
3
+ 2 компоненты, принадлежащие множеству F
2
= {0, 1}. Здесь
s
i
–положительное число, обозначающее число элементов в факторной базе
F B
i
.
Вектор, соответствующий паре (a, b), состоит из следующих
компонент. Первая компонента соответствует знаку числа a − bm–
положительному числу отвечает 0, а отрицательному –1. Далее идет
блок из s
1
элементов, соответствующий разложению a − bm по F B
2
. Все
элементы этого вектора заменятся их остатками по модулю 2. Дальше идут
компоненты вектора разложения числа F
1
(a, b) по факторной базе F B
1
,
взятые по модулю 2. Наконец, последний блок из s
3
элементов соответствует
Глава 5. Метод решета числового поля                                              157

         Первая координата отражает знак числа и равно 0 для положительных
a − bm, и 1, для отрицательных.

         Аналогично для алгебраической факторной базы

N r(a, b) = F1 (8, 3) = 5696 = 26 · 891 .

         Полная длина вектора разложения равна 24.

Формирование системы линейных уравнений

         В предыдущем разделе была описана процедура просеивания, в
результате которой было получено множество S гладких пар (a, b), а
также разложения значений F1 (a, b) и F2 (a, b) в произведения элементов
факторных баз F B1 и F B2 .
         Для формирования системы линейных уравнений нам также
понадобится вычислить значение квадратичного характера для каждой
пары (a, b) ∈ S и каждой пары (p, r) из квадратичной факторной базы.
Это означает, что для всех (a, b) ∈ S , (p, r) ∈ F B3 , мы должны вычислить
символ Лежандра
               
         a − br
                 .                                                             (5.137)
           p
         Теперь можно сформировать матрицу системы. Она будет содержать
|S| строк по числу найденных гладких пар. Каждая строка содержит k =
s1 + s2 + s3 + 2 компоненты, принадлежащие множеству F2 = {0, 1}. Здесь
si –положительное число, обозначающее число элементов в факторной базе
F Bi .
         Вектор,   соответствующий          паре   (a, b),   состоит   из   следующих
компонент. Первая компонента соответствует знаку числа a − bm–
положительному числу отвечает 0, а отрицательному –1. Далее идет
блок из s1 элементов, соответствующий разложению a − bm по F B2 . Все
элементы этого вектора заменятся их остатками по модулю 2. Дальше идут
компоненты вектора разложения числа F1 (a, b) по факторной базе F B1 ,
взятые по модулю 2. Наконец, последний блок из s3 элементов соответствует

Страницы