В арифметике нечетное составное целое число n называется псевдопростым числом Эйлера по основанию a , если a и n взаимно просты , и
(где mod относится к операции по модулю ).
Мотивацией для этого определения является тот факт, что все простые числа p удовлетворяют приведенному выше уравнению, которое можно вывести из малой теоремы Ферма . Теорема Ферма утверждает, что если p является простым числом и взаимно простым с a , то a p −1 ≡ 1 (mod p ). Предположим, что p > 2 является простым числом, тогда p можно выразить как 2 q + 1, где q — целое число. Таким образом, a (2 q +1) − 1 ≡ 1 (mod p ), что означает, что a 2 q − 1 ≡ 0 (mod p ). Это можно разложить на множители как ( a q − 1)( a q + 1) ≡ 0 (mod p ), что эквивалентно a ( p −1)/2 ≡ ±1 (mod p ).
Уравнение можно проверить довольно быстро, что может быть использовано для вероятностного тестирования простоты . Эти тесты в два раза сильнее тестов, основанных на малой теореме Ферма.
Каждое псевдопростое число Эйлера является также псевдопростым числом Ферма . Невозможно создать определенный тест простоты, основанный на том, является ли число псевдопростым числом Эйлера, поскольку существуют абсолютные псевдопростые числа Эйлера , числа, которые являются псевдопростыми числами Эйлера по каждому основанию, взаимно простому с собой. Абсолютные псевдопростые числа Эйлера являются подмножеством абсолютных псевдопростых чисел Ферма, или чисел Кармайкла , и наименьшее абсолютное псевдопростое число Эйлера равно 1729 = 7×13×19 (последовательность A033181 в OEIS ).
Немного более сильное условие, что
где n — нечетное составное число, наибольший общий делитель a и n равен 1, а ( a / n ) — символ Якоби , — более общее определение псевдопростого числа Эйлера. См., например, страницу 115 книги Коблица, указанную ниже, страницу 90 книги Ризеля или страницу 1003. [1] Обсуждение чисел этой формы можно найти в Euler–Jacobi pseudoprime . Абсолютных псевдопростых чисел Эйлера–Якоби не существует. [1] : стр. 1004
Сильный вероятный простой тест даже сильнее, чем тест Эйлера-Якоби, но требует тех же вычислительных усилий. Из-за этого преимущества над тестом Эйлера-Якоби программное обеспечение для проверки простых чисел часто основывается на сильном тесте.
функция EulerTest(k) а = 2 если k == 1 , то верните false, иначе если k == 2 , то верните true, иначе m = modPow(a,(k-1)/2,k), если (m == 1) или (m == k-1), то верните true, иначе верните false, конец, конец , конец
