считаем эту вероятность
P
и сравним ее с вероятностью
P
0
попадания в
гладкое число. Пусть
W
— множество чисел, меньших
n
, взаимно простых с
числами из факторной базы
F
.
W
=
{
1
≤
a < n
:
8
p
i
2
F,
(
a, p
i
) = 1
}
.
Тогда
P
=
2
n
2
X
d
2
W
Ψ
2
n
d
, M
2
=
=
1
n
2
X
d
2
W
n
d
2
∙
1
ln
n
d
ln
M
2 ln
n
d
ln
M
=
X
d
2
W
1
d
ln
n
d
ln
M
ln
n
d
ln
M
2
.
(12)
Формула (12) получена следующим образом. Вероятность нахождения
искомой пары чисел определяется как число пар, имеющих общий делитель
из множества
W
, отнесенное к общему числу всевозможных пар (
n
2
/
2
).
Вероятность попадания в гладкое число оценивается как
P
0
=
1
n
Ψ (
n, M
) =
1
ln
n
ln
M
ln
n
ln
M
.
(13)
В сумме (12) присутствует слагаемое с
d
= 1
, равное
(
P
0
)
2
. Тем самым
получаем нижнюю оценку для
P
:
P
0
2
< P.
Чтобы получить более точную оценку, можно воспользоваться очевидным
неравенством
ln
n
d
ln
M
ln
n
d
ln
M
<
ln
n
ln
M
ln
n
ln
M
=
1
P
0
при
1
< d < n.
Заменив в (12) знаменатель с учетом неравенства, получим
P
0
2
+
P
0
2
X
d
2
W, d
6
=1
1
d
2
< P.
Как известно, ряд Дирихле
∞
X
k
=1
1
k
2
сходится и дает в сумме число, мень-
шее единицы (а именно,
π
2
6
−
1)
. Поэтому наша выборочная сумма будет
заведомо меньше единицы. Можно в итоге записать
P > P
0
2
(1 +
C
)
, C <
π
2
6
−
1
.
Теперь оценим значение ограничения факторной базы
M
, необходимой,
чтобы вычислить логарифм с помощью обобщенного алгоритма, при усло-
вии, что используются матрицы размера dim. Порядок подгруппы, в которой
90 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2014. № 2
