ВВЕДЕНИЕ 3
1 Постановка задачи 5
2 Технологический и алгоритмический прогресс 6
3 Числа Ферма 13
4 Вероятностные тесты на простоту 16
5 Случайных поиск чисел в заданном диапазоне 17
6 Тест Ферма на простоту 19
7 Тест Миллера-Рабина на простоту 20
8 Тест Поклингтона 23
9 Результаты Вычислений 25
ЗАКЛЮЧЕНИЕ 44
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 45
ПРИЛОЖЕНИЯ 46
Простые числа принадлежат недосягаемому миру мыслимых сущностей. Эти чудесные объекты допускают простое, изящное описание, и в то же время приводят к невероятным - можно даже сказать невообразимым - трудностям в изучении их свойств. Само понятие простоты можно объяснить и ребенку, но тем не менее, ни один человеческий мозг не в состоянии охватить целиком всю картину. В наши дни, когда теоретики продолжают схватку со всей лавиной простых чисел, громадные силы и средства направлены на исследование вычислительных аспектов данной проблемы: на задачи отыскания, классификации и применения простых чисел в других областях знаний. Именно этим вычислительным аспектам мы и посвятим дальнейшие главы. Однако же, нам придется время от времени обращаться к теории для того, чтобы осветить, подчеркнуть и обосновать практическую значимость вычислительных алгоритмов.
Итак, натуральное число р называется простым, если оно имеет лишь два делителя, а именно 1 и р. Натуральное число называется составным, если оно превосходит единицу и не является простым. (Считается, что число 1 - не простое и не составное.) Таким образом, число п является составным тогда и только тог да, когда оно допускает так называемое нетривиальное разложение п = аЬ, где целые числа а, Ь лежат строго между 1 и п. Несмотря на изысканную ясность определения простоты, получающаяся последовательность простых чисел 2, 3, 5, 7, . . . будет далеко не тривиальным постоянным объектом нашего внимания. Изумительные свойства простых чисел, а также связанные с ними известные результаты и открытые проблемы многочисленны и разнообразны. Мы затронем в этой главе те моменты, которые нам видятся наиболее красивыми и интересными с теоретической точки зрения, а также проясним и некоторые практические аспекты. В то же время мы коснемся важной проблемы разложения на множители - темы, тесным образом связанной с изучением самих простых чисел. В оставшейся части настоящей главы мы предложим способ вычисления характеров и распознавания простых чисел, а также приведем сопутствующие практические сведения.
Каждое натуральное Число n можно единственным образом представить в виде где все показатели а, - натуральные 'Числа, а 'Числа Р1 < Р2 < . . . < Pk - простые. (Если число п является простым, то его представление по этой теореме совпадает с ним самим, при этом k = 1 и а1 = п. В случае п = 1 теорема имеет место в смысле пустого произведения, т. е. k = О.) Доказательство теоремы 1.1.1 естественным образом распадается на две части: существование разложения числа п на простые множители и его единственность. Существование доказывается очень легко (достаточно рассмотреть наименьшее число, не имеющее искомого разложения, представить его в виде произведения двух множителей и получить противоречие). Единственность - несколько более тонкая задача. Ее можно вывести из более простого результата, а именно, из «первой теоремы» Евклида. Основная теорема арифметики дает начало тому, что можно назвать «Основной задачей арифметики»: найти разложение данного целого числа п > 1 на простые множители. Обратимся теперь к текущему положению дел в вычислительной области.
В данной работе были протестированы следующие тесты на простоту - Тест Миллера-Рабина , тест Ферма и тест Поклингтона. В работе были представлены результаты работы этих алгоритмов по времени. Наилучшие показали были выявлены у теста Ферма - он быстрее всех справился с определением - просто число или составное , вплоть до чисел ориентировочно 2Л300. Так же в работе были представлены таблицы вероятности ошибок в определении простоты числа. Здесь наилучшие результаты были представлены у теста Миллера- Рабина. Тест Ферма , который работает быстрее всех показал наихудший результат. Но Тест Миллера-Рабина является самым медленным из всех представленных. Это обуславливается большим числом проверок на простоту и наибольшим количеством операций. Тест Поклингтона показал средние результаты в случае ошибок и скорости работы. Тест Ферма в свою очередь показал наиболее быструю работу , но имеет довольно большую вероятность ошибки. Таким образом , если необходимо сгенерировать простое число большого размера , то можно воспользоваться тестом Миллера рабина с количеством итераций примерно log2 п , где n - само число. Это поможет существенно сократить процент ошибок при генерации простых чисел большого размера , например при шифровании.
Помощь студентам и аспирантам в выполнении работ от наших партнеров
