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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 4. Метод квадратичного решета 128
max q(x) ≈ 2n
1/2+ε
. Оценим вероятность того, что случайно выбранное
значение q(x), x ∈ [−L, L], является B –гладким, где B – верхняя граница
факторной базы. Обозначим через ψ(X, B) число B -гладких чисел в
интервале [1, X].
Вычислим сначала значение ψ(X, B) при B = x
1/2
:
ψ(X, X
1/2
) = X −
X
X
1/2
<p≤X
[X/p], (4.105)
где p пробегает все простые числа из интервала [1, X]. Действительно, все
числа, меньшие X
1/2
по определению X
1/2
– гладкие. Число из второй
половины интервала [1, X] не будет гладким, если оно кратно какому-нибудь
простому числу p, X
1/2
< p < X . Число таких кратных для каждого p
равно bX/pc (т.е. целой части от частного X/p). По теореме Чебышева, число
простых чисел в интервале [1, X], обозначаемое через π(x), примерно равно
X/ ln X . Отсюда
ψ(X, X
1/2
) = X
1 −
X
X
1/2
<p≤X
1/p
+ 0(X/ ln X). (4.106)
По теореме Мертенса,
X
p≤t
1/p = ln ln t + C + 0(1/ ln t), (4.107)
для некоторой константы C. Используя эту теорему, получим
X
X
1/2
<p≤X
1/p =
X
p≤X
1/p −
X
p≤X
1/2
1/p = ln ln X −ln ln(X
1/2
) + 0(1/ ln X
1/2
) =
= ln 2 + 0(1/ ln X).
Подставляя последнее равенство в (4.106), получим
ψ(X, X
1/2
) = (1 − ln 2)X + 0(1/ ln X
1/2
), (4.108)
откуда
ψ(X, X
1/2
)
X
∼ 1 − ln 2 при x → ∞ (4.109)
Глава 4. Метод квадратичного решета                                        128

max q(x) ≈ 2n1/2+ε . Оценим вероятность того, что случайно выбранное
значение q(x), x ∈ [−L, L], является B –гладким, где B – верхняя граница
факторной базы. Обозначим через ψ(X, B) число B -гладких чисел в
интервале [1, X].
       Вычислим сначала значение ψ(X, B) при B = x1/2 :
                                 X
                     1/2
              ψ(X, X ) = X −          [X/p],                            (4.105)
                                      X 1/2

Страницы