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

  • 07 нояб. 2012 г.
  • 1623 Слова
Чувашский государственный университет им. И. Н. Ульянова
Кафедра вычислительной техники












Курсовая работа по дискретной математике
Тема: «Генерация простых чисел»







Выполнил:
Студент ИВТ 41-10
Галкин Павел

Руководитель:
Стеценко В. Г.










Чебоксары, 2011

Содержание


Индивидуальное задание 3
Введение 3
Глава 1. Простыечисла 3
1.1.Формальное описание 3
1.2.Основные теоремы 3
1.3.Проверка числа на простоту 5
1.4.Генерация простых чисел 6
1.5.Проблемы 6
1.6.Вывод 6
Глава 2.Разработка программной модели генерации простых чисел 6
2.1. Семантическое описание программной модели. 6
2.2. Выбор типов и структуры данных. 6
2.3. Используемые алгоритмы. 6
2.4. Разработкаграфического интерфейса. 7
2.5. Вывод. 7
Глава 3. Анализ результатов моделирования 8
3.1. Результаты тестирования алгоритмов на быстродействие. 8
3.2. Число ошибок допущенных тестом Ферма. 8
3.1. Вывод 8
Глава 4. Вывод по курсовой работе. 8
Список литературы. 9
Приложение. 9





























Индивидуальное задание

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


Введение

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





Глава 1. Простые числа


1 Формальное описание


Пусть а— целое число. Числа 1, -1, а, -а называются тривиальными делителями числа а.
Целое число р[pic]Z\{0} называется простым, если оно не является делителем единицы и не имеет других делителей, кроме тривиальных. В противном случае число р[pic]Z\{-1,0,1} называется составным.

2 Основные теоремы

Свойства простых чисел:

1. Если числа р и q простые и р делится на q, то р ~ q.Доказательство. Из определения простого числа и того, что р делится на q, следует, что q [pic]{±1, ±р}. Если q = ±1, то q не простое; если q = ±р, то р ~ q.


2. Если число р простое и число а целое, то либо а делится на р, либо НОД(a,р) = 1.
Доказательство. Пусть НОД(a, р) = d > 1. Тогда а делится на d и р делится на d, но так как число р простое, то либо d = ± 1 (что противоречитпредположению), либо d = ±р.

3. Если число р простое и произведение ab делится на р, то либо а делится на р, либо b делится на р.
Доказательство. Пусть а не делится на р. Тогда по предыдущему свойству НОД(а, р) = 1. Следовательно, по свойству 2 наибольшего общего делителя, b делится на р.

4. Если число р простое и произведение а1а2...ак делится на р, то хотя бы одно из чисел а1,а2,... ,ак делится на р.

5.Если числа р1,р2,...,рк,q1,q2,...,ql простые и выполняется равенство для произведений р1р2...рк=q1q2...ql, то l = к и числа q1,q2,...,ql можно перенумеровать так, что р1~q1, р2~q2, ..., рk~qk..


Теорема 1. (основная теорема арифметики). Всякое число n[pic]Z\{-1,0,1} можно представить в виде п = εр1р2...рr, где ε=±1 и р1,р2,…,pr — простые числа (не обязательно различные), г>=1. Этопредставление единственно с точностью до порядка сомножителей.
Доказательство. Сначала докажем, что разложение существует. Пусть n[pic]Z\{-1,0,1}. Доказывать будем индукцией по |n|. Если |n|=2, то п=ε*2, где ε=±1, — база индукции. Пусть для всех чисел а[pic]Z\{-1,0,1}, |a| 1, то есть существует нетривиальный делитель а (а ≠ ± 1, а ≠ ±п) числа п. Тогда существует такое целое число b, что п = ab, где b ≠ ±1, b ≠±п. Поскольку |п| > 1, справедливо равенство для абсолютных величин: |n| = |ab| = |а|*|b| > |а|.
Аналогично |n| > |b|, поэтому к числам а и b применимо предположение индукции:

a = ε1р1р2...рk , b = ε2q1q2...ql
где числа рi ,qj простые; ε1, ε2= ±1.
Произведение ab дает требуемое представление. Существование представления...