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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 4. Метод квадратичного решета 133
x q(x) Вектор разложения
-224 -12196095 −3 × 5 × 23
2
× 29 × 53
-166 -9040779 −3
2
× 11 × 29 × 47 × 67
-155 -5769579 −3 × 17 × 29 × 47 × 83
-99 -5387470 −2 × 5 × 11 × 17 × 43 × 67
-77 -4185918 −2 × 3
8
× 11 × 29
-40 -2162943 −3
7
× 23 × 43
-23 -1232550 −2 × 3
3
× 5
2
× 11 × 83
-21 -1123054 −2 × 17
2
× 29 × 67
-13 -684990 −2 × 3
3
× 5 × 43 × 59
-12 -630223 −11 × 23 × 47 × 53
11 629970 2 × 3 × 5 × 11 × 23 × 83
22 1233045 3
2
× 5 × 11 × 47 × 53
32 1781505 3
2
× 5 × 11 × 59 × 61
41 2275290 2 × 3
4
× 5 × 53
2
46 2549685 3 × 5 × 43 × 59 × 67
268 14783217 3 × 17
4
× 59
5. Для каждого p ∈ FB подсчитаем количество гладких чисел, в
разложение которых этот p входит в нечетной степени:
p 2 3 5 11 17 23 29 43 47 53 59 61 67 83
#p 6 9 8 7 2 4 4 4 4 3 4 1 4 3
Из таблицы 1 видно, что множитель p = 61 вошло только в одно
гладкое число q(32). Удалим 61 из факторной базы, а число q(32) из
множества Smooth. Остальные числа представим в виде векторов, состоящих
из показателей степеней (первая координата представляет знак числа равный
1, если число - отрицательное, и 0, если число - положительное).
6. Сформируем матрицу системы A размерности 14 × 15, полагая
A(i + 1, j) =
(
1, если p
i
входит в разложениеq(x
j
) в нечетной степени,
0, в противном случае.
Первая строка матрицы определяет знаки соответствующих q(x
j
).
Глава 4. Метод квадратичного решета                                         133

        x        q(x)             Вектор разложения
       -224 -12196095          −3 × 5 × 232 × 29 × 53
       -166    -9040779       −32 × 11 × 29 × 47 × 67
       -155    -5769579       −3 × 17 × 29 × 47 × 83
       -99     -5387470      −2 × 5 × 11 × 17 × 43 × 67
       -77     -4185918            −2 × 38 × 11 × 29
       -40     -2162943                 −37 × 23 × 43
       -23     -1232550        −2 × 33 × 52 × 11 × 83
       -21     -1123054           −2 × 172 × 29 × 67
       -13    -684990        −2 × 33 × 5 × 43 × 59
       -12     -630223            −11 × 23 × 47 × 53
        11      629970        2 × 3 × 5 × 11 × 23 × 83
        22     1233045            32 × 5 × 11 × 47 × 53
        32     1781505            32 × 5 × 11 × 59 × 61
        41     2275290              2 × 34 × 5 × 532
        46     2549685            3 × 5 × 43 × 59 × 67
       268     14783217                 3 × 174 × 59
      5. Для каждого p ∈ FB подсчитаем количество гладких чисел, в
разложение которых этот p входит в нечетной степени:
        p     2 3 5 11 17 23 29 43 47 53 59 61 67 83
       #p 6 9 8          7    2     4     4   4   4     3   4   1   4   3
      Из таблицы 1 видно, что множитель p = 61 вошло только в одно
гладкое число q(32). Удалим 61 из факторной базы, а число q(32) из
множества Smooth. Остальные числа представим в виде векторов, состоящих
из показателей степеней (первая координата представляет знак числа равный
1, если число - отрицательное, и 0, если число - положительное).

      6. Сформируем матрицу системы A размерности 14 × 15, полагая
               (
                 1, если pi входит в разложениеq(xj ) в нечетной степени,
 A(i + 1, j) =
                 0, в противном случае.

      Первая строка матрицы определяет знаки соответствующих q(xj ).

Страницы