homechevron_rightУчебаchevron_rightМатематика

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

Выполняет тест простоты числа, основанный на малой теореме Ферма по заданным основаниям.

При помощи данного калькулятора можно узнать является ли число псевдопростым по заданному основанию. Калькулятор использует тест простоты Ферма, основанный на малой теореме Ферма. Если n простое число, и a не делится на n, то справедливо сравнение: a^{n-1} \equiv 1 \pmod n .

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

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

Может быть простым?
 



Однако, при помощи теста нельзя достоверно утверждать, что число простое, если результат равен 1. То есть обратное утверждение неверно: если a^{n-1} \equiv 1 \pmod n и числа a и n взаимно простые не означает что n - простое число.
Например, число 29341 - дает положительный результат по основаниям 3; 5; 7; 11, согласно результатам работы теста. Однако это число не является простым, это одно из составных чисел Кармайкла: 13 x 37 x 61= 29341.

Ссылка скопирована в буфер обмена
Creative Commons Attribution/Share-Alike License 3.0 (Unported) PLANETCALC, Тест простоты Ферма

Комментарии