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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 2. Простые алгоритмы факторизации 82
Оценка сходимости метода Шенкса
Согласно расчетам, выполненным самим Шенксом, число итераций
первого и второго циклов определяется числом w сомножителей числа n
и равно примерно
C
2
w
− 2
· n
1/4
,
где C –константа, равная примерно 2, 4 для первого цикла итераций.
Таким образом, метод квадратичных форм Шенкса имеет асимптотическую
сложность O(n
1/4
) и является, как уже упоминалось раньше, наиболее
быстрым методом в классе алгоритмов для разложения чисел длиной до 18
десятичных знаков.
Глава 2. Простые алгоритмы факторизации                            82

Оценка сходимости метода Шенкса

      Согласно расчетам, выполненным самим Шенксом, число итераций
первого и второго циклов определяется числом w сомножителей числа n
и равно примерно
             C
           w
               · n1/4 ,
          2 −2
где C –константа, равная примерно 2, 4 для первого цикла итераций.
Таким образом, метод квадратичных форм Шенкса имеет асимптотическую
сложность O(n1/4 ) и является, как уже упоминалось раньше, наиболее
быстрым методом в классе алгоритмов для разложения чисел длиной до 18
десятичных знаков.

Страницы