ferma

Тест простоты Ферма

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

Тест основан на утверждении:

Если n — простое число, то оно удовлетворяет сравнению a**(n − 1) ≡ 1(mod n) для любого a, которое не делится на n.

Это утверждение не является достаточным условием простоты, поэтому тест выявляет потенциально простые числа (псевдопростые) и составные.

Зачастую выбирают разные числа a и проводят тест несколько раз.

Требования к реализации

Реализовать функцию теста Ферма со следующей сигнатурой:

ferma(number: int, k: int = 100) -> bool

Описание параметров:

• number: проверяемое число;
• k: количество тестов.

Результатом работы функции должно True если число псевдопростое, в противном случае False.

Входные и выходные данные

в следующей таблице приведены примеры входных данных для параметра number:

№	Ввод	Вывод
1	2	True
2	3	True
3	4	False
4	199	True
5	200	False

Ссылки

• Wiki