Элементы теории чисел и криптозащита. Воронков Б.Н - 33 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

33
7. Аппроксимация функции
π
(x)
Число
π
(x), которое определено для всех действительных чисел x, яв-
ляется числом простых чисел ≤ x. История теории чисел сопровождалась
попытками найти хорошую аппроксимацию функции
π
(x). В настоящее
время известно несколько аппроксимаций
π
(x), характеризующихся различ-
ной точностью.
7.1.
π
(x) приближённо равна x/ln x. Точное утверждение гласит, что
π
(x) ln x/x → 1 при x→ ∞. Это было предположением Гаусса (оно несколько
отличается от формулы Лежандра), оно было доказано независимо
Ж. Адамаром и Ш.Ж. Валле-Пуссэном в 1896 г. Для понимания формулы
важным является представление, что для больших х отношение
π
(x)lnx/x
близко к 1. Простые числа редеют в соответствии с логарифмическим зако-
ном, но это в среднем: всегда можно найти бесконечно много пар простых
чисел, различающихся между собой на две единицы!
Используя эту формулу, найдём, что количество простых чисел, за-
ключённое между x и y приблизительно равно
ln ln
yx
yx
−
. Полагая
y = 10
4
+ 100 и x = 10
4
, получим 9,67; в действительности в этом интервале
содержится 11 простых чисел. Эта аппроксимация не такая плохая, как мо-
жет показаться: 1229 простых чисел, меньших x, и 1240 – меньших y.
7.2. Компьютерное упражнение. Составьте таблицу оценок количе-
ства простых чисел в интервалах вида: от 10
n
до 10
n
+ 10
k
, где k = 2, 3 или 4,
и сравните полученные значения с действительными.
Вспомним две другие аппроксимации
π
(x): логарифмический инте-
грал и функцию Римана [15].
7.3. Компьютерное упражнение: логарифмический интеграл. Он
определяется как
2
()
ln
x
dt
Li x
t
=
∫
.
Напишите программу для вычисления этого интеграла по формуле
Симпсона. Вторая версия теоремы о простых числах утверждает, что
π
(x)/Li(x) → 1 при х → ∞. Примените эту формулу к аналогичным примерам
п. 7.2 и сравните полученные результаты. [В случае, если Вы забыли фор-
мулу Симпсона [3], то напомним, как с ее помощью аппроксимировать ин-
теграл
Ifxdx
a
b
=
∫
()
. Для этого разделим интервал интегрирования на 2n рав-
ных частей точками
x
0
= a, x
1
= a+h, x
2
= a + 2h, . . . , x
2n
= a + 2nh = b, где h = (b– a)/2n.

Страницы