Тест Ферма

Тест простоты Ферма в теории чисел — это тест простоты натурального числа n, основанный на малой теореме Ферма.

Содержание

Если n — простое число, то оно удовлетворяет сравнению $a^{n-1}\equiv 1{\pmod {n}}$ для любого a, которое не делится на n.

Выполнение сравнения $a^{n-1}\equiv 1{\pmod {n}}$ является необходимым, но не достаточным признаком простоты числа. То есть, если найдётся хотя бы одно a, для которого $a^{n-1}\not \equiv 1{\pmod {n}}$ , то число n — составное; в противном случае ничего сказать нельзя, хотя шансы на то, что число является простым, увеличиваются. Если для составного числа n выполняется сравнение $a^{n-1}\equiv 1{\pmod {n}}$ , то число n называют псевдопростым по основанию a . При проверке числа на простоту тестом Ферма выбирают несколько чисел a. Чем больше количество a, для которых $a^{n-1}\equiv 1{\pmod {n}}$ , тем больше шансы, что число n простое. Однако существуют составные числа, для которых сравнение $a^{n-1}\equiv 1{\pmod {n}}$ выполняется для всех a, взаимно простых с n — это числа Кармайкла. Чисел Кармайкла — бесконечное множество, наименьшее число Кармайкла — 561. Тем не менее, тест Ферма довольно эффективен для обнаружения составных чисел.

Скорость

При использовании алгоритмов быстрого возведения в степень по модулю время работы теста Ферма для одного a оценивается как O(log²n × log log n × log log log n), где n — проверяемое число. Обычно проводится несколько проверок с различными a.

Литература

Василенко О. Н. Теоретико-числовые алгоритмы в криптографии, МЦНМО, 2003
Трост Э. — Primzahlen / Простые числа — М.: ГИФМЛ, 1959, 135 страниц
Томас Кормен, Чарльз Лейзерстон, Рональд Ривест, Клиффорд Штайн. Section 31.8: Primality testing // Introduction to Algorithms (рус.). — Second Edition. — MIT Press; McGraw-Hill, 2001. — С. 889—890. — ISBN 0-262-03293-7.

Ссылки

Is this number prime? // Berkeley Math Circle 2002—2003
Fermat’s test // Algorithms used in asymmetric cryptosystems. cryptowiki.net

Теоретико-числовые алгоритмы
Тесты простоты	Миллера Миллера — Рабина Люка — Лемера Пепина Агравала — Каяла — Саксены Соловея — Штрассена
Поиск простых чисел	Перебор делителей Решето Эратосфена Решето Аткина Решето Сундарама
Факторизация	Перебор делителей Метод Ферма p−1-метод Полларда ρ-алгоритм Полларда Метод Лемана Метод эллиптических кривых (алгоритм Ленстры) Алгоритм Диксона Квадратичное решето
Дискретное логарифмирование	Алгоритм Гельфонда — Шенкса Алгоритм Полига — Хеллмана ρ-метод Полларда Алгоритм «кенгуру» Полларда Алгоритм Адлемана Алгоритм COS
Нахождение НОД	Алгоритм Евклида Расширенный алгоритм Бинарный алгоритм
Арифметика по модулю	Алгоритм Монтгомери Китайская теорема об остатках
Умножение и деление чисел	Алгоритм Карацубы Алгоритм Тоома — Кука Алгоритм Шёнхаге — Штрассена Алгоритм Фюрера Алгоритм Харви — ван дер Хувена Алгоритм Бурникеля — Циглера
Вычисление квадратного корня	Алгоритм Тонелли — Шенкса Алгоритм Берлекэмпа — Рабина

Похожие исследовательские статьи

Тест Миллера — Рабина — вероятностный полиномиальный тест простоты. Тест Миллера — Рабина, наряду с тестом Ферма и тестом Соловея — Штрассена, позволяет эффективно определить, является ли данное число составным. Однако, с его помощью нельзя строго доказать простоту числа. Тем не менее тест Миллера — Рабина часто используется в криптографии для получения больших случайных простых чисел.

Ма́лая теоре́ма Ферма́ — теорема теории чисел, которая утверждает, что:

Если $\text{[math]}$ — простое число и $\text{[math]}$ — целое число, не делящееся на $\text{[math]}$ то $\text{[math]}$ делится на $\text{[math]}$

Сравне́ние двух целых чисел по мо́дулю натурального числа $\text{[math]}$ — математическая операция, позволяющая ответить на вопрос о том, дают ли два выбранных целых числа при делении на $\text{[math]}$ один и тот же остаток. Любое целое число при делении на $\text{[math]}$ даёт один из $\text{[math]}$ возможных остатков: число от 0 до $\text{[math]}$ ; это значит, что все целые числа можно разделить на $\text{[math]}$ групп, каждая из которых отвечает определённому остатку от деления на $\text{[math]}$ . Эти группы называются классами вычетов по модулю $\text{[math]}$ , а содержащиеся в них целые числа — вычетами по модулю $\text{[math]}$ .

Те́ст Люка́ — Ле́мера — полиномиальный, детерминированный и безусловный тест простоты для чисел Мерсенна. Сформулирован Эдуардом Люка в 1878 году и доказан Лемером в 1930 году.

Вопрос определения того, является ли натуральное число $\text{[math]}$ простым, известен как проблема простоты.

Тест Пепина — тест простоты для чисел Ферма. Тест назван в честь французского математика Феофила Пепина.

Псевдопростое число — натуральное число, обладающее некоторыми свойствами простых чисел, являясь тем не менее составным. В зависимости от рассматриваемых свойств существует несколько различных типов псевдопростых чисел.

Си́мвол Я́коби — теоретико-числовая функция двух аргументов, введённая К. Якоби в 1837 году. Является квадратичным характером в кольце вычетов.

Вероятно простое число — это число, которое проходит тест простоты. Сильное вероятно простое число — это число, которое проходит сильную версию теста простоты. Сильное псевдопростое число — это составное число, которое проходит сильную версию теста простоты.

Тест Аграва́ла — Кая́ла — Саксе́ны — единственный известный на данный момент универсальный полиномиальный, детерминированный и безусловный тест простоты чисел, основанный на обобщении малой теоремы Ферма на многочлены.

Число Кармайкла — составное число $\text{[math]}$ , которое удовлетворяет сравнению $\text{[math]}$ для всех целых $\text{[math]}$ , взаимно простых с $\text{[math]}$ , другими словами — псевдопростое число по каждому основанию $\text{[math]}$ , взаимно простому с $\text{[math]}$ . Такие числа относительно редки, но их бесконечное число, наименьшее из них — 561; существование таких чисел делает недостаточным условие простоты малой теоремы Ферма, и не позволяет применять тест Ферма как универсальное средство проверки простоты.

Тест Соловея — Штрассена — вероятностный тест простоты, открытый в 1970-х годах Робертом Мартином Соловеем совместно с Фолькером Штрассеном. Тест всегда корректно определяет, что простое число является простым, но для составных чисел с некоторой вероятностью он может дать неверный ответ. Основное преимущество теста заключается в том, что он, в отличие от теста Ферма, распознает числа Кармайкла как составные.

Метод квадратичного решета — метод факторизации больших чисел, разработанный Померанцем в 1981 году. Долгое время превосходил другие методы факторизации целых чисел общего вида, не имеющих простых делителей, порядок которых значительно меньше $\text{[math]}$ . Метод квадратичного решета представляет собой разновидность метода факторных баз . Этот метод считается вторым по быстроте. И до сих пор является самым быстрым для целых чисел до 100 десятичных цифр и устроен значительно проще чем общий метод решета числового поля. Это универсальный алгоритм факторизации, так как время его выполнения исключительно зависит от размера факторизуемого числа, а не от его особой структуры и свойств.

В теории чисел теорема Прота является тестом простоты для чисел Прота.

В теории чисел тест простоты Люка — это тест простоты натурального числа n; для его работы необходимо знать разложение $\text{[math]}$ на множители. Для простого числа n простые множители числа $\text{[math]}$ вместе с некоторым основанием a составляют сертификат Пратта, который позволяет подтвердить за полиномиальное время, что число n является простым.

В теории чисел, вероятно простым числом называется целое число, которое удовлетворяет некоторым условиям, которым удовлетворяют все простые числа. Различные типы вероятно простых имеют различные условия. Поскольку вероятно простое может быть составным, условие выбирается так, чтобы сделать эти исключения редкими.

В теории чисел факторизация методом непрерывных дробей (CFRAC) — это алгоритм разложения целых чисел на простые множители. Это алгоритм общего вида, пригодный для факторизации произвольного целого $\text{[math]}$ .

Псевдопросты́е чи́сла Ферма́ — составные числа, проходящие тест Ферма. Названы в честь французского математика Пьера Ферма. В теории чисел псевдопростые числа Ферма составляют важнейший класс псевдопростых чисел.

В математике методы проверки на простоту с помощью эллиптических кривых являются одними из самых быстрых и наиболее широко используемых методов проверки на простоту . Эту идею выдвинули Шафи Гольдвассер и Джо Килиан в 1986 году; она была превращена в алгоритм А.О.Л. Аткином в том же году. Впоследствии алгоритм был несколько раз изменён и улучшен, в особенности Аткином и François Morain в 1993. Концепция использования факторизации с помощью эллиптических кривых была разработана Хендриком Ленстрой в 1985 году, и в скором времени последовало её использование для проверки и доказательства чисел на простоту.

В математике и информатике сертификат простоты — это строгое доказательство того, что число является простым. Наличие сертификата простоты позволяет проверить, что число простое, не прибегая к тестам простоты.

Эта страница основана на статье Википедии.
Текст доступен на условиях лицензии CC BY-SA 4.0; могут применяться дополнительные условия.
Изображения, видео и звуки доступны по их собственным лицензиям.