Введение. 
Основные алгоритмы проверки чисел на простоту

Выделение простых чисел является сложной задачей математики. Ученые на протяжении многих веков пытаются найти закон по которому можно определить n-ое простое число. Первый, кто занимался этой задачей, был великий математик древности Эратосфен.

Первую известную нам таблицу простых чисел составил итальянский математик Пьетро Антонио Катальди в 1603 г. Она захватывала все простые числа от 2 до 743.

В 1770 г. Немецкий математик Иоганн Генрих Ламберт опубликовал таблицу наименьших делителей всех чисел, не превосходящих 102 000 и не делящихся на 2, 3, 5. Первым значительным успехом в определении простоты целых чисел явились теорема Вильсона и теорема Ферма, которые являются центральными в данной проблеме по сей день.

В данной курсовой работе будут представлены основные алгоритмы проверки чисел на простоту. Цель данной курсовой работы познакомить читателя с основными алгоритмами проверки чисел на простоту. Почему же так важно знать простое число или нет? Поиск больших простых чисел имеет важное значение для математики и не только. Например, в криптографии большие простые числа используются в алгоритмах шифрования с открытым ключом. простой число алгоритм делимость Работа состоит из пяти глав. Первые три главы напомнят читателю основные понятия из алгебры и теории чисел. В первой главе вводится и анализируется понятие одной из основных характеристик работы алгоритмов — время исполнения алгоритма. Во второй главе определяется понятие делимости целых чисел, приводятся свойства делимости, определяется понятие НОД и НОК для двух целых чисел и приводится алгоритм Евклида. В третье главе представлены основные свойства и теоремы из теории сравнений. Здесь же доказываются теоремы основные критерии простоты целых чисел: теорема Вильсона, теорема Ферма. В четвёртой главе приведены основные алгоритмы проверки на простоту: пробное деление, решето Эратосфена, тест на основе малой теоремы ферма. Пятая глава является практической частью работы. В первом пункте этой главы решены практические задачи. Во втором пункте реализованы алгоритмы на языке С++.