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

    Глава 4. Метод квадратичного решета                                                                                     135

    обозначает знак числа q(x) и равен 1, если q(x) < 0, и 0, в противном случае.
    Заменим коэффициенты матрицы их остатками по модулю 2. Получим:
                    x      ± 2 3 5 7                                                            
                                                                           1 1 0 0 0
                −441 1 7 0 0 2                                                      
                                                                          1 1 0 1 0 
                −360 1 3 2 1 0                                                      
                                                                          1 0 1 0 0 
                −192 1 6 1 0 0
                                                                                    
                                                                                    
                                                                          1 0 1 1 1 
                −105 1 0 1 1 1                                                      
                                                                          1 0 0 0 0 
                  −16
                                                                                    
                               1 4 0 0 0                                            
                                                                          0 0 1 0 0 
                    75         0 0 1 2 0                                            
                                                                           0 1 0 0 1 
                                                                                    
                                                                       
                    168        0 3 0 0 1
                                                                           0 1 0 1 0
                    360        0 3 2 1 0
                Припишем к полученной матрице единичную матрицу размерности
    8 × 8 и будем выполнять эквивалентные преобразования со строками
    расширенной матрицы (прибавление ведущей строки к нижележащим
    строкам, и перестановку строк) с целью приведения матрицы к треугольному
    виду:
                                                                                                                             
    1   2   3   4    5    -5    -4   -2   -1   0   1   2   4           1   2   3   4   5   -5    -4   -2   -1   0   1   2   4
                                                                                                                           

   1   1   0   0    0    1     0    0    0    0   0   0   0 
                                                              
                                                                      1   1   0   0   0   1      0    0   0    0   0   0   0 
                                                                                                                              
    1   1   0   1    0    0     1    0    0    0   0   0   0         0   1   1   0   0   1      0    1   0    0   0   0   0 
                                                                                                                           

                                                                                                                           

   1   0   1   0    0    0     0    1    0    0   0   0   0 
                                                              
                                                                      0   0   1   0   0   0      0    1   0    1   0   0   0 
                                                                                                                              
    1   0   1   1    1    0     0    0    1    0   0   0       ∼
                                                           0         0   0   0   1   1   0      0    1   1    0   0   0   0 
                                                                                                                           

                                                                                                                           

   1   0   0   0    0    0     0    0    0    1   0   0   0 
                                                              
                                                                      0   0   0   0   1   1      1    1   1    0   0   0   0 
                                                                                                                              
                                                                                                                           

   0   0   1   0    0    0     0    0    0    0   1   0   0 
                                                              
                                                                      0   0   0   0   0   0      0    1   0    1   1   0   0 
                                                                                                                              

   0   1   0   0    1    0     0    0    0    0   0   1   0 
                                                              
                                                                      0   0   0   0   0   0      1    1   1    1   0   1   0 
                                                                                                                              
    0   1   0   1    0    0     0    0    0    0   0   0   1           0   0   0   0   0   0      1    0   0    1   0   0   1


                Последние три строчки содержат различные решение системы. Для
    нахождения какого-нибудь решения возьмем одну из этих строчек, например,
    строчку 6, и выделим столбцы, в которых в этой строке содержатся единицы:
    X = {−2, 0, 1}. Вычислим
        Y                                                                                       Y
    A=    (x+m) = (45−2)·45·(45+1) = 89010,                                            B2 =           q(x) = 4802
            x∈X                                                                                 x∈X

                Вычисляя теперь с помощью алгоритма Евклида Н.О.Д. (n, A −
    B)=Н.О.Д. (2401, 88530) = 13, найдем искомый делитель числа n. Второй
    делитель q = 157 можно вычислить как Н.О.Д. (n, A + B), либо просто деля
    n на 13. То же решение можно получить, используя строку 7, а строка 8 дает