Тесты простоты

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 21:17, 17 мая 2016.

Основные задачи

  • Разложить числа на простые множители;
  • Поиск чисел.

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

Примеры решений

TemplateExampleIcon.svg Пример Пример в общем случае
- малая теорема Ферма
- простое
берем разные

Если - составное.

Числа Кармайкла и псевдопростые числа

TemplateDifinitionIcon.svg Определение « Псевдопростое число »
Если для некоторого составного для всех целых , взаимнопростых с , выполняется следующее равенство: , то называется псевдопростым по основанию
TemplateDifinitionIcon.svg Определение « Число Кармайкла »
Если существуют такие числа, что - составное, то для всех целых взаимнопростых с , то называется числом Кармайкла.


(минимальное число Кармайкла)
TemplateTheoremIcon.svg Теорема Теорема
Если - псевдопростое по оси и , то псевдопростое по оси и
Доказательство