フェルマーの小定理計算機

フェルマーの小定理は、素数、累乗、剰余演算を結び付けます。標準形は、p が素数で a が p で割り切れないとき、a^(p - 1) を p で割った余りが 1 になるというものです。合同式では a^(p - 1) は法 p で 1 と合同です。a = 2、p = 7 なら 2^6 = 64 であり、64 を 7 で割った余りは 1 です。 同値な別形式では、p が素数なら任意の整数 a について a^p は法 p で a と合同です。この形式は p が a を割り切る場合も含み、そのとき両辺の余りはゼロになります。標準形には a と p の最大公約数が 1 という条件が必要です。計算機は素数性と互いに素の条件を確認してから、選んだ合同式を計算します。 大きな累乗を直接計算すると、途中の数が非常に巨大になります。そこで二進法による剰余累乗、別名繰り返し二乗法を使います。現在の底を繰り返し二乗し、乗算のたびに p で割った余りに置き換えます。これにより正確な余りを保ちながら巨大な累乗全体を避け、指数に対して対数的な回数の手順で計算できます。実用的な暗号ソフトウェアの基本となる方法です。 この定理で合成数であることを証明できます。互いに素な底で合同式が成立しなければ、候補の法は素数ではありません。ただしフェルマーテストを一度通過しても、素数とは証明できません。特定の底で通過する合成数があり、カーマイケル数は自身と互いに素なすべての底で標準テストを通過します。そのため信頼できる素数判定には、より強い決定的な検査や、底を慎重に選んだ Miller-Rabin などのテストを使います。 フェルマーの結果は整数論と計算のさまざまな分野に役立ちます。剰余計算で指数を小さくし、素数判定法の着想となり、公開鍵暗号の数学的基礎を支えます。RSA は関連するオイラーの定理により直接依存しますが、フェルマーの小定理はその核にある素数を法とする振る舞いを説明します。また、p が素数で a が法 p でゼロでないとき、a^(p - 2) の法 p での値から逆元を求められます。 この計算機は授業の例の確認や剰余の規則性の探索に使い、大きな暗号用素数の認証には使わないでください。信頼性のある素数判定のため入力を JavaScript の安全な整数に制限し、累乗自体は正確な整数演算で行います。成功結果は、選んだ素数と底が指定した定理の形式を満たすことを確認するものです。未検査の合成数候補が素数であることを、それだけで証明するものではありません。