Псевдопростое число Эйлера
- Нечетное составное целое число n называется псевдопростым числом Эйлера с основанием a, если a и n взаимно просты.
- Определение основано на малой теореме Ферма, утверждающей, что если p является простым и взаимно простым с a, то ap−1 ≡ 1 (по модулю p).
- Псевдопростые числа Эйлера также являются псевдопростыми числами Ферма.
- Невозможно провести определенный тест на простоту, основанный на том, является ли число псевдопростым числом Эйлера.
- Существует более сильное определение псевдопростого числа Эйлера, где наибольший общий делитель a и n равен 1, а (a / n) — символ Якоби.
- Строгий вероятностный простой тест еще более эффективен, чем тест Эйлера-Якоби, но требует тех же вычислительных усилий.
Полный текст статьи: