Метод квадратичного решета и его вариации

В начале 70-х годов прошлого столетия[1], Майкл Моррисон и Джон Бриллхарт (Michael A. Morrison & John Brillhart) предложили процедуру алгоритмического построения сравнения х2 = у2 (mod та) по заданному множеству сравнений вида и2 = v (mod та). Для реализации этой процедуры потребовалось введение понятия «факторная база».

Определение 13.2. Зафиксируем натуральное число В > 2. Мы будем называть множество В и факторной базой, если оно содержит целые числа —1, 2, а также нечетные простые числа р, удовлетворяющие следующим условиям.

  • 1. Для величины р выполнено неравенство р < В.
  • 2. Выполнено равенство — 1, то есть число т является квадратичным вычетом по модулю р.

Отметим, что второе условие позволяет нам связать с факторной базой множество Тт многочленов второй степени

для каждого из которых разрешимо сравнение

Опишем способ, который предложили Моррисон и Бриллхарт для построения сравнения х2 = у2 (mod т) по множеству сравнений вида и2 = v (mod т). Каждому найденному сравнению, в котором

и величина s определяет количество элементов в факторной базе, сопоставим векторы

Вектор ё содержит нули и единицы, то есть степени простых, входящих в разложение v, взятые по модулю 2. Нулям соответствуют простые в четной степени, то есть квадраты, единицам - простые, которые не образуют квадрат.

Предположим, что мы нашли г сравнений

правые части которых удовлетворяют равенству (13.19). Каждому сравнению будут соответствовать свои векторы уг и ег вида (13.21).

Образуем из векторов ё; прямоугольную матрицу Е размера (г х s), где г - количество строк матрицы, as- количество столбцов. Элементами матрицы являются нули и единицы - каждая строка матрицы соответствует одному из найденных сравнений (13.22). Аналогично из векторов уг образуем матрицу Г.

Применим алгоритм исключения Гаусса над полем F2 и приведем матрицу Е к треугольному виду. Если г > s, то количество строк больше, чем количество столбцов, и ранг матрицы не превосходит s. Следовательно, найдется как минимум одна линейно зависимая строка, состоящая из одних нулевых элементов. Именно эта строка будет соответствовать сравнению, в котором правая часть будет полным квадратом.

Одновременно с изменением матрицы Е мы будем модифицировать матрицу Г и найденные нами сравнения таким образом, чтобы при получении пулевой строки соответствующее ей сравнение имело искомый вид х2 = у2 (mod ш).

Алгоритм гауссового исключения хорошо известен, его трудоемкость оценивается величиной 0(s3) операций побитового сложения и умножения вычетов по модулю т. При больших значениях В для приведения матрицы Е к треугольному виду можно использовать алгоритмы Ланцоша или Видсмана-Конерсмитта, см. [3].

  • [1] См. Morrison МЛ. and Brillhart J. A Method of Factoring and the Factorizationof Fr // Mathematics Of Computation. -№. 129. - Vol. 29. - 1975. -pp. 183-205.
 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >