ВВЕДЕНИЕ 3
История возникновения 3
Понятия и термины 4
Цель изучения простых чисел 5
Первая Часть 6
Тесты на простоту 6
Типы алгоритмов 8
Генерация большого простого числа 11
Бесконечность простых чисел 13
Разложение числа на простые множители 14
Распределения простых чисел 15
Вторая Часть 16
Цель работы 17
Демонстрация алгоритма 21
Трудоемкость алгоритма n-1 25
Третья часть 27
Исследования 27
Проверка и сравнение с теорией 30
ЗАКЛЮЧЕНИЕ 33
СПИСОК ЛИТЕРАТУРЫ 34
ПРИЛОЖЕНИЕ
Изучение простых чисел началось из древне от египтян, после греками до наших дней. Интерес древних математиков к простым числам связан с тем, что любое число либо простое, либо может быть представлено в виде произведения простых чисел.
Простые числа известны с древних времен, но их использование обрела стоимость только в конце 20- ого века. Действительно их роль в современном мире очень велика они имеют важную роль не только в математике, но и в криптографии.
В современной криптографии - науке, занимающейся шифрованием и расшифровкой тайных сообщений, в основном используют свойства простых чисел, а именно: разложение на множители. Мы не способны быстро проверить и распознать большие числа на факт простоты, в частности факторизовать- разложить на простые множители, по крайней мере мы ограничены технологиями своего времени. пользуясь этим фактом, построена ряд криптографических алгоритмов, один из наиболее популярных это “RSA”
Сегодня, без этих криптографических алгоритмов не утроена ни одна ЭВМ сеть АС. Те же банки, мессенджеры, социальные сети, зашифрованные каналы связи для хранении и передачи информации используют в своих транзакциях криптографические алгоритмы основанных на сложно решаемой задаче факторизации числа.
Понятия и термины
Профессиональными математиками установлено, что 1 это не простое число. На самом деле 1 не простое число и этому есть объяснения.
Что такое простое число?
Простое число это - число, которое делится на 1 и на самого себя. Простые числа это - 2,3,5,7,11,13 и так далее. Хорошо, определение звучит так, что 1 тоже простое число, оно вроде подходит под определение, она делится на 1 и на саму себя на 1. Исторический так сложилось, что 1 считали простым числом, математики раньше тоже так считали. Но в итоге им пришлось исключит 1 из ряда простых чисел, отделив его от простых и от составных. Была причина сделать это. В математике есть очень важная теорема- Основная теорема арифметики. Она гласит, что каждое натуральное число можно представить в виде уникального произведения простых чисел. Суть в том, что простые числа, как атоме в химии. Их можно использовать для создание других чисел перемножаю их друг на друга. На пример 15 это 3 умноженное на 5 15=3*5, где 3 и 5 - простое числа. Возвращаясь к определению теоремы замечаем, что там есть слово уникально, что означает произведение должно быть уникальным. Ну что выходит, если число 1 простое?
15=5х3
=1х3х5
=1х1х3х5
=1х1х1х3х5
Это означало бы, что произведение простых чисел для получения 15 уже не является уникальным. Так что когда все считали 1 простым числом, ее приходилось исключать то тут то там, то есть использовать все простые число кроме 1. Поэтому 1 исключили из определения простых чисел, так что 1 не простое число, но и не составное число, которое получается как произведение простых множителей. Поэтому с тех пор 1 относится к отдельной категории.
Таким образом, число n является составным тогда и только тогда, когда его можно разложить на n = axb, где целые числа a, b лежат строго между 1 и n .
Цель изучения простых чисел
Для чего же нужны простые числа и зачем проверять числа на простоту? Задача проверки простоты натурального числа и задача построения больших простых чисел имеют важные приложения в криптографии. Генерации простых чисел, используемые в криптографических алгоритмах с открытым ключом, необходимы для аутентификации (определения подлинности) сообщений (файлов) в сетях ЭВМ и АС.
В 21-ом веке вся безопасность инфраструктуры лежит на основе сложно-решаемой задаче разложения большого числа на простые множители. Если тот факт, что задача разложения числа на простые множители разрушить, придумав новый быстрый алгоритм, либо отыскав в ряде натуральных чисел закономерность, то с 21-ого века мы очень быстро скатимся до уровня 18-ого века, либо даже будет всемирный хаос.
Да существует множество криптографических алгоритмов не имеющих ничего общего с простыми числами, но либо они сложны в реализации, либо на против их безопасность очень низкая для стремительно развивающей отрасли науки.
Поэтому чем больше мы познаем тайны простых чисел и в конце концов изучим их мы можем построить новые алгоритмы с очень прочной защитой. А не основываться на догадках.
Мы можем сказать, к примеру числа 2, 3, 5, 7, 17, 37, 61 ... - простые. А как определить число n имеющая более 5, 10, 20 знаков? На этот вопрос отвечает тесты(алгоритмы) проверки числа на простоту
n-1 тест оказался не плохим алгоритмом в проверка числа на простоту и можно сказать, что время работы программа приблизительно растет близко к закону степени, но так и все другие алгоритмы основанные на мало теореме Ферма имеет лишь один не достаток - они пропускают некоторые составные числа, к примеру число 341 для входного параметра а, равного, к примеру, 2, но в алгоритме есть найденное решение, если при проверки окажется, что параметр определяющий НОД равен 1, то тест будет пройден заново, но только в этот раз уже с другим значением числа а. Только данное решение проблемы для всех чисел, хотя и убирают числа, прошедшие тест со лживыми свидетелями простоты, но в свою очередь так же как и у всех других тестов основанных на малой теореме Ферма тест проходит со всеми значениями числа а для чисел Кармайкла, которые и являются псевдопростыми.
Что касается полученных результатов из анализа, был сделан вывод, что количество простых чисел приблизительно равно асимптотическому приближению с погрешностью не более 4 %.
Более точно определяет приближения Лежандра и Гаусса, соответственно.
Так же вероятность появления простого числа до определенного числа приблизительно равно . Но так как появления простых чисел не имеет
закономерности, то не будет никакое приближение описывать точное появление простых чисел.
Таким образом, задача проверки числа на простоту является, если не самой главной, то одним из самых главных задач на сегодняшний день.
Ведь криптографический алгоритм будет надежнее тогда, когда генерируемое простое число большое. А генератор как раз проверяет выбранное им число на простоту, следовательно, чем выше скорость, заложенного в него алгоритма то есть быстродействие, тем выше безопасность будущей криптосистемы.
Создания нового алгоритма, либо модернизация и ускорение уже имеющихся алгоритмов проверки числа на простоту, является актуальными развивающимся направлением по сей день
Помощь студентам и аспирантам в выполнении работ от наших партнеров
