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

Глава 4. Метод квадратичного решета                                             129
                                                          √
Отсюда, около 30 % чисел, меньших X , является                X –гладкими.
        Для произвольной границы B               =   X 1/u выполняется формула
К.Дикмана (K. Dickman [1930]):

                    ψ(X, X 1/u )
                                 ∼ ρ(u),                                     (4.110)
                       X
где ρ(u) для u > 0 функция Дикмана–де Брюина. Эта функция является
непрерывным решением дифференциального уравнения

uρ0 (u)+ρ(u−1) = 0 при u > 1 c начальным условием ρ(u) ≡ 1 на интервале [0, 1].

        Ее значение приблизительно равно ρ(u) ≈ u−u . Дадим здесь таблицу
начальных значений этой функции
  u       2        3             4           5            6          7          8
ρ(u) 0.25 3, 7 · 10−2 3, 9 · 10−4 3, 2 · 10−4 2, 1 · 10−5 1, 2 · 10−6 5, 96 · 10−8

        Заметим, что величина X/ψ(X, X 1/u ) равна среднему числу попыток
для нахождения одного гладкого числа. Каждая попытка может быть
оценена в ln ln B элементарных операций. Нам требуется найти столько
гладких чисел, сколько элементов в факторной базе, т.е. около π(B) (в
действительности, факторная база содержит примерно половину от этого
числа, т.к. только половина p является квадратичными вычетами по модулю
n). Отсюда можно подсчитать, что общее число операций T (u) примерно
равно

      T (u) = π(B) ln ln BX/ψ(X, X 1/u ) ≈ X 1/X u1/u .
                                                                             (4.111)
Мы должны минимизировать эту величину. Вычислим ее логарифм:
                              1
                 ln T (u) =     ln X + u ln u.
                              u
        Производная этой функции равна 0, если u2 (ln u + 1) = ln X , откуда
                                     √
        u ∼ (2 ln X/ ln ln X) и B ≈ e 2 ln X ln ln X) .
                             1/2
                                                                       (4.112)

        При выборе B равным выражению (4.112) при X = n, число
элементарных операций метода квадратичного решета разложения числа n