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

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

Эта страница существует благодаря следующим персонам

Anton

Создан: 2020-11-10 12:40:33, Последнее изменение: 2020-11-10 14:07:42

При помощи данного калькулятора можно узнать является ли число псевдопростым по заданному основанию. Калькулятор использует тест простоты Ферма, основанный на малой теореме Ферма. Если 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.

Ссылка скопирована в буфер обмена
PLANETCALC, Тест простоты Ферма

Комментарии