情報セキュリティにおけるフェルマーの小定理とは何ですか？

フェルマーの小定理は、素数を法とする整数の計算能力を提供する、基本数論の基本的な定理です。これはオイラーの定理の特定のケースであり、素数判定や公開鍵暗号などの初等数論のアプリケーションに不可欠です。これはフェルマーの小定理と呼ばれます。

フェルマーの小定理はフェルマーの小定理とも呼ばれ、Pは素数であり、「a」はPで割り切れない正の整数であると定義されています-

a ^P-1 ≡1modP

2番目の条件は、Pが素数で、aが整数の場合、a ^P ≡1modP。

証明 − z _p は整数{0、1…P-1}のセットであり、モジュロPを掛けると、結果にはZ _pのすべての要素が含まれます。 あるシーケンスでは、さらにax0≡0mod Pです。したがって、（P-1）の数{a mod P、2a mod P、…（（P-1）a mod P）}は数{1、2 、…（P-1）}ある順序で。

両方のステップで数値を乗算し、結果modPを取得すると

a x2ax…。 x（（P-1）a）=[（a mod P）x（2a mod P）x…。 x（（P-1）a mod P）] mod P

=[1 x 2x…x（P-1）] mod P

=（P-1）！ mod P

しかし

a x 2ax…x（（P-1）a）=（P-1）！a ^P-1

（P-1）！ a ^P-1 ≡（𝑃− 1）！ mod P

a ^P-1 ≡1modP

p：{1、2 ... p1}未満の正の整数のセットを検討し、各要素にpを法とするaを掛けて、セットX ={a mod p、2amodpを受け取ります。 。 。 （p1）modp}。 pはaを除算しないため、Xの要素はどれもゼロに似ていません。

さらに、Xの整数の2つは同じではありません。これを確認するには、（ja≡p）ここで1≤p1であると考えてください。 pであるため、方程式の両側からaを削除すると、−j≡pになります。

jとkはどちらもp未満の正の整数であるため、この最終的な類似性にはアクセスできません。したがって、Xの（p1）要素はすべて正の整数であり、2つの要素が同じではないことが理解されます。

数値-フェルマーの定理は、pが素数であり、aがPで割り切れない正の整数である場合、a ^P-1 ≡1（mod p）。

したがって、3 ¹⁰ ≡1（mod 11）。

したがって、3 ²⁰¹ =（3 ¹⁰ ） ²⁰ x3≡3（mod 11）。

フェルマーの小定理は、いくつかのべき乗の解をすばやく見つけるのに役立つ場合があります。次の例はその概念を示しています。

例1 − 6 ¹⁰ の結果を見つけます mod11。

解決策

ここでは、6 ¹⁰ があります mod 11 =1。これは、フェルマーの小定理の最初のバージョンであり、p=11です。

例2 − 3 ¹² の結果を見つける mod11。

解決策

したがって、指数（12）と係数（11）は等しくありません。置換により、これはフェルマーの小定理を利用して定義できます。

3 ¹² mod11 =（3 ¹¹ x3）mod11 =（3 ¹¹ mod11）（3 mod 11）=（3x3）mod11 =9