ИСПОЛЬЗОВАНИЕ И СРАВНИТЕЛЬНЫЙ АНАЛИЗ МЕТОДОВ ГЕНЕРАЦИИ ПРОСТЫХ ЧИСЕЛ

История и описание простых чисел

Простым числом мы называем каждое натуральное число, большее единицы, которое не является произведением двух натуральных чисел, больших единицы. [5, стр. 11]

Все остальные числа кроме единицы называются составными. Есть люди, которые думают, что простые числа не нуждаются в глубоком изучении, однако такие числа имеют колоссальную важность для математики. Любое число может быть представлено единственным образом, как произведение простых чисел. (Так число 84=2*2*7*3) Таким образом простые числа — это маленькие частички, из которых может быть собрано что-то большое.

Так как простые числа — это составляющие целых чисел, получаемые произведением, мы можем решить проблемы целых чисел, сведя их к проблемам простых. Поэтому, если бы количество простых чисел было конечным, возможно было бы проверить каждое, но простых чисел бесконечно много. 

Это было доказано Евклидом. Утверждалось, что, имея некоторое количество простых чисел (p1,…, pn) и рассмотрев число, на единицу большее произведения этих чисел (p1×…×pn + 1). Таким образом мы получим число, не являющееся кратным исходным числам, но в тоже время оно больше единицы. Поэтому все простые множители полученного числа не могут быть простыми числами из списка (p1,…, pn), вставляя полученные простые числа в наш список мы найдем как минимум одно новое простое число. Таким образом доказано существование бесконечного множества простых чисел. 

История изучений

Доподлинно неизвестно, когда начали изучать простые числа. Их рассматривают очень давно, и первые записи не сохранились. Существует гипотеза, что ранние цивилизации начали изучать простые числа, однако первым документальным подтвержением стали египетские папирусы, сделанные примерно 3500 лет назад. 

Вероятно, древние греки перыми начали изучать простые числа, так как думали, что простые числа нужны для абстрактной математики. В курсе школьной программы до сих пор рассматривают Теорему Евклида, хотя она старше 2000 лет. 

Практические применения

Простые числа имеют широкий спектр применений как в математике, так и вне её. В наше время они используются каждый день, вне зависимости от того, знаем мы об этом или нет. Простые числа важны для ученых, так как они являются составляющими любого числа. Многие трудности, касающиеся произведения, возможно избежать, если бы знания людей о простых числах были бы обширнее. Если бы наши знания о простых числах были больше, то нам было бы проще решать математические проблемы, разделив их на более мелкие. В реальной жизни мы сталкиваемся с важностью простых чисел в компьютерах, так как хранение данных является бинарным кодом, который мы можем преобразовать в число. В банковских переводах, в передаче секретной информации, скрытой средствами криптографии в ключах к шифрам чаще всего используются простые числа порядка 10^100 и более. Так как простые числа не имеют особых характеристик, а перебрать их все в пределах от 10^100 до 10^101 займет даже у суперкомпьютера десятки лет, шифры с использованием больших простых чисел в ключе являются стойкими.

Тайны простых чисел.

Сегодня о простых числах знают не очень много, хотя их изучают уже более трех тысячелетий и описать их достаточно просто. К примеру, математикам известно, что единственная пара простых чисел, которая отличается на единицу, это числа 2 и 3. Но при этом не известно, есть ли бесконечное число пар простых чисел, различающихся на 2.

Множество вопросов о простых числах связаны с тем, сколько простых чисел имеют определенное свойство. Современная математика предлагает достаточно точные методы получить правильный ответ на большинство из таких вопросов. Гипотезы математиков доказываются численными экспериментами, поэтому являются достаточно надежными. Однако для работы компьютерных алгоритмов чрезвычайную значимость имеет абсолютная точность этих предположений.

Серьезной практическую проблему представляет сложность нахождения всех простых множителей числа. Для числа 21, быстро определяется, что 21=7х3, но если число 1000-значное, на поиск всех его простых множителей уйдет более миллиарда лет у самого мощного компьютера. Безопасность в интернете серьезно зависит от сложности этих вычислений, поэтому для уверенности в безопасности коммуникации в сети важно знать, что невозможно просто взять и придумать легкий путь к подбору простых множителей.

Поиск новых простых чисел

Простых чисел невероятно много, потому что, взяв большое число и прибавив к нему единицу, можно получить простое число. Сейчас большинство компьютерных программ полагаются на то, что простые числа легко найти. Это означает, что, наугад выбрав число из 100 знаков, компьютер получит большое простое достаточно быстро. Так как 100-значных простых чисел гораздо больше, чем атомов во вселенной, то вероятнее всего, никто не будет знать точно, простое ли это число.

Есть две важные проблемы: бесконечно ли количество простых чисел, которые на один больше, чем квадрат, и существует ли бесконечное количество пар простых чисел, различающихся друг от друга на 2.

В нашей работе мы рассмотрим два алгоритма генерации простых чисел:

1) Решето Аткина

2) Решето Эратосфена.

Решето Аткина

Опишем этапы алгоритма:

1. Перечисляются натуральные числа от 1 до n. 

2. Просматриваются все существующие пары чисел x, y, где x<=sqrt(n) и y<=sqrt(n). Т.е. (1,1), (1,2), …, (1,sqrt(n)), (2,1), (2,2),…,(sqrt(n),sqrt(n)).

3. Для всех пар чисел находятся решения трех уравнений:

a) 4*x^2+y^2;

b) 3*x^2+y^2;

c) 3*x^2-y^2, значение вычисляется при x>y. 

4. Для каждого найденного решения уравнений находится остаток от деления на 12, при этом:

a) если остаток 1 или 5 для решения первого уравнения;

b) если остаток 7 для решения второго уравнения;

с) если остаток 11 для решения третьего уравнения, 

то в первоначальном ряду от 1 до n число отмечается как простое.

Замечание: при условии, что число Z присутствует в значениях нескольких уравнений, и остаток от деления его на 12 удовлетворяет условиям обоих групп, то оно помечается дважды: в начале как простое, а затем как составное.

5. На заключительном этапе проверяется кратность отмеченных чисел квадратам простых чисел от 5 до sqrt(n). Если число кратно квадрату, то оно отмечается как составное.

Пример работы алгоритма для n = 50. 

1. Выписываем все натуральные числа из диапазона от 1 до 50. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50. 

2. Перебираются все возможные пары чисел от (1,1) до (6,6) (т.к. sqrt(50)~7).

3. Вычисляем значения уравнений для каждой пары чисел x и y.

 Таблица 1.

Пример решения уравнений

4. Вычисляем остаток от деления на 12 и помечаем простые числа. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50. 

5. Проверяем кратность помеченных чисел квадратам простых из диапазона от 5 до 7.

5,7 — простое число, 6 — составное, значит проверяем на кратность 5^2=25, 7^2=49 помеченные числа. В результате 25 — нужно вычеркнуть. В итоге остаются только простые числа от 1 до 50.

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50.

Решето Эратосфена

Автором алгоритма поиска простых чисел до целого числа N является древнегреческий математик Эратосфен Киренский. Из названия алгоритма понятен принцип его работы – под решетом понимается фильтрация всех чисел кроме простых. В процессе прохода по массиву чисел простые остаются, а составные исключаются.

Чтобы найти все простые числа не больше данного числа n, по методу Эратосфена, выполняются такие действия:

1. Выписать все целые числа от двух до n.
2. Примем, что p равна 2 – первому простому числу.
3. Вычеркнуть из ряда числа от 2p до n с шагом p (2p, 3p, 4p, …).
4. Найти первое незачеркнутое число в ряду, большее чем p, и сделать p равной этому числу.
5. Пока возможно, повторять шаги 3 и 4.

В итоге не зачеркнутые числа в ряду – все простые числа от 2 до n.

Пример.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50.

На первом шаге выбираем число 2 и вычеркиваем все числа, кратные 2,

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50.

Берем первое незачеркнутое число (3) и зачеркиваем все числа, кратные ему.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50.

Далее берем следующее незачеркнутое число (5)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50.

Берем (7)

1 2 3 (4) 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 (44) 45 46 47 48 49 50.

Так как, рассматривая число 2, мы зачеркивали и 2*11, то нет смысла смотреть произведение 11*2, таким образом, имеет смысл рассматривать числа равные квадрату рассматриваемого числа и больше.

Для 7 рассмотрим 7*7, 7*8, 7*9 и т.д., но т.к. 7*7=49, а мы ищем простые числа в первых 50 натуральных числах, то поиск можно считать завершенным.

Для нахождения первых 800 000 000 простых чисел мы реализовали алгоритмы асинхронного решета Эратосфена и решета Аткина.

Рисунок 1. Процесс работы алгоритма решета Эратосфена

Решето Эратосфена справилось с поставленной задачей за 9.4 секунды, затратив 53 Mb оперативной памяти.

Для решета Аткина в нашей реализации потребовался 841 Mb оперативной памяти и 115 секунд.

Обсуждение результатов и выводы

В представленной работе мы изучили и представили методы генерации больших простых чисел, провели их сравнительный анализ, в котором выяснилось, что решето Эратосфена позволяет гораздо быстрее получить простые числа в диапазоне от 0 до 8*10^8. При этом он также задействует гораздо больше оперативной памяти на хранение вычеркнутых чисел и биткарт. Скорее всего это вызвано тем, что, хоть теоретически решето Аткина имеет меньшую сложность равную , чем решето Эратосфена, имеющее -  , на практике приходится делить весь диапазон чисел на блоки. Так чтобы выделенный блок смог поместиться в L2 кэш процессора, иначе генерации происходить гораздо медленнее в обоих методах.

Представленные методы, хотя и являются самыми быстрыми на данный момент, на наш взгляд не могут быть достаточно эффективными на больших числах, так как плотность нахождения простых чисел падает с ростом величины исследуемого диапазона. Чем больше число, тем больше вычеркиваний надо произвести и соответственно хранить в оперативной памяти, в эффективность, которой и упирается генерация.

Методы генерации были реализованы нами на языке программирования С++, в частности мы улучшили их, добавив биткарту, хранящую промежуточные вычеркивания.

Список литературы:

1.  Айерлэнд К., Роузен М. Классическое введение в современную теорию чисел. – М.: Мир, 1987. – 418 с.
2.  Бухштаб А.А. Теория чисел. – М.: Просвещение, 1966. – 384 с.
3.  Дэвенпорт Г. Высшая арифметика. Введение в теорию чисел. – М.: Наука, 1965. – 176 с.
4.  Оре О. Приглашение в теорию чисел: Пер с англ. Изд. 2-е, стереотипное. – М.: Едиториал УРСС, 2003. – 128 с.
5.  Серпинский В. Что мы знаем и чего не знаем о простых числах. – М., Л.: Физматгиз, 1963. – 92 с.
6.  Трост Э. Простые числа. – М.: Физматлит, 1959. – 137 с.