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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 5. Метод решета числового поля 167
Применяя эту теорему, найдем значение корня x
∗
= g(m) mod n =
694683807559 mod 45113 = 43992.
Недостатком этого метода вычисления квадратного корня из полинома
является его ограничения, заключающиеся в том, что он применим только в
случае полинома f
1
(x) нечетной степени и выбор соответствующей системы
простых чисел, по которым f
1
(x) mod p является неприводимым, не всегда
возможен.
В работе Бухлера, Ленстры и Померанса ([13]) дается оценка
сложности алгоритма вычисления квадратного корня. Она зависит от
выбранного алгоритма и техники реализации операций с длинными
числами. Если операции умножения полиномов и вычисления остатков по
модулю f(x) выполнены с помощью дискретного преобразования Фурье, то
время вычисления квадратного корня определяется с помощью следующей
оценки:
T (n) = y
1+o(1)
, (5.145)
где y –верхняя граница для параметров a, b области просеивания, зависящая
от числа n и степени d многочлена f
1
(x). Ее оптимальное значение равно
log y =
1
2
+ o(1)
d log s +
q
(d log d)
2
+ 4 log(n
1/d
) log log(n
1/d
).
(5.146)
В указанной работе дается описание еще одного алгоритма
вычисления квадратного корня, который позволяет вычислять корень
путем последовательного вычисления системы вспомогательных полиномов
(µ
i
(s), ν
i
(s)). Пусть S = {(a
i
, b
i
)}
k
i=1
–решение системы, тогда определим
систему многочленов (µ
i
, ν
i
) следующим образом:
(µ
0
(s), ν
0
(s) = (1, 1)).
µ
i
=
(
µ
i−1
/(a −bθ), если (a − bθ) |µ
i−1
,
µ
i−1
· (a − bθ), иначе.
(5.147)
ν
i
=
(
ν
i−1
· (a − bθ), если (a − bθ) |µ
i−1
,
ν
i−1
, иначе.
(5.148)
Глава 5. Метод решета числового поля                                           167

       Применяя эту теорему, найдем значение корня x∗ = g(m) mod n =
694683807559 mod 45113 = 43992.

       Недостатком этого метода вычисления квадратного корня из полинома
является его ограничения, заключающиеся в том, что он применим только в
случае полинома f1 (x) нечетной степени и выбор соответствующей системы
простых чисел, по которым f1 (x) mod p является неприводимым, не всегда
возможен.
       В работе Бухлера, Ленстры и Померанса ([13]) дается оценка
сложности алгоритма вычисления квадратного корня. Она зависит от
выбранного алгоритма и техники реализации операций с длинными
числами. Если операции умножения полиномов и вычисления остатков по
модулю f (x) выполнены с помощью дискретного преобразования Фурье, то
время вычисления квадратного корня определяется с помощью следующей
оценки:

          T (n) = y 1+o(1) ,                                               (5.145)

где y –верхняя граница для параметров a, b области просеивания, зависящая
от числа n и степени d многочлена f1 (x). Ее оптимальное значение равно
                                                                       
            1
                                q
  log y =     + o(1)   d log s + (d log d)2 + 4 log(n1/d ) log log(n1/d ).
            2
                                                                            (5.146)
       В указанной работе дается описание еще одного алгоритма
вычисления квадратного корня, который позволяет вычислять корень
путем последовательного вычисления системы вспомогательных полиномов
(µi (s), νi (s)). Пусть S = {(ai , bi )}ki=1 –решение системы, тогда определим
систему многочленов (µi , νi ) следующим образом:

   (µ0 (s), ν0 (s) = (1, 1)).
        (
           µi−1 /(a − bθ), если (a − bθ) | µi−1 ,
  µi =                                                                     (5.147)
           µi−1 · (a − bθ), иначе.
         (
             νi−1 · (a − bθ), если (a − bθ) | µi−1 ,
  νi =                                                                     (5.148)
             νi−1 , иначе.

Страницы