Калькулятор малой теоремы Ферма

Малая теорема Ферма связывает простые числа, степени и модульную арифметику. Стандартная форма утверждает: если p простое и a не делится на p, то a^(p - 1) при делении на p даёт остаток 1. В обозначениях сравнений a^(p - 1) сравнимо с 1 по модулю p. Для a = 2 и p = 7 получаем 2^6 = 64, а 64 при делении на 7 даёт остаток 1. Эквивалентная форма утверждает, что a^p сравнимо с a по модулю p для любого целого a, если p простое. Она охватывает и случай, когда p делит a, поскольку тогда обе стороны имеют нулевой остаток. Стандартная форма требует, чтобы наибольший общий делитель a и p был равен 1. Калькулятор проверяет простоту и взаимную простоту до вычисления выбранного сравнения. Прямое вычисление большой степени может дать огромное промежуточное число. Поэтому инструмент использует двоичное возведение в степень по модулю, также называемое методом повторного возведения в квадрат. Он многократно возводит текущее основание в квадрат и после каждого умножения берёт остаток по модулю p. Это сохраняет точный остаток, позволяет обойтись без громоздкой полной степени и требует лишь логарифмического числа шагов по отношению к показателю. Метод лежит в основе практического криптографического ПО. Теорема позволяет доказать составность числа: если взаимно простое с модулем основание не удовлетворяет сравнению, предлагаемый модуль не может быть простым. Но прохождение одного теста Ферма не доказывает простоту. Некоторые составные числа проходят его для отдельных оснований, а числа Кармайкла проходят стандартный тест для любого взаимно простого с ними основания. Поэтому надёжная проверка простоты использует более сильные детерминированные проверки или тесты вроде Miller-Rabin с тщательно выбранными основаниями. Результат Ферма применяется во многих областях теории чисел и вычислений. Он помогает уменьшать показатели степеней в модульных вычислениях, служит основой идей тестов простоты и вносит вклад в математические основы криптографии с открытым ключом. RSA непосредственно опирается скорее на родственную теорему Эйлера, но теорема Ферма объясняет поведение простых модулей в её основе. Обратный элемент по модулю можно найти как a^(p - 2) по модулю p, если p простое, а a не равно нулю по модулю p. Используйте калькулятор для проверки учебных примеров и изучения модульных закономерностей, а не для сертификации больших криптографических простых чисел. Ввод ограничен безопасными целыми числами JavaScript для надёжной проверки простоты, а само возведение в степень использует точную целочисленную арифметику. Успех подтверждает, что выбранные простое число и основание удовлетворяют указанной форме теоремы; сам по себе он не доказывает простоту непроверенного составного кандидата.