情報セキュリティにおけるオイラーの定理とは何ですか？

オイラーの定理は、正の整数を法とする整数の累乗を使用したフェルマーの小定理処理の一般化です。 RSA暗号システムの理論的サポート構造など、基本数論のアプリケーションで増加します。

この定理は、互いに素であるすべてのaとnについて-

$$ \ mathrm {a ^ {\ phi \ left（n \ right）} \、\ equiv \、1 \ left（mod \、n \ right）} $$

ここで、ф（n）はオイラーのトーティエント関数であり、nに対して互いに素であるn未満の正の整数の数をカウントします。

そのような整数のセットを考えてください-

R ={x ₁ 、x ₂ 、…x _ф（n） }、つまり、Rの各要素xiは、ged（xi、n）=1のnよりも小さい一意の正の整数です。次に、各要素にaとモジュロn-

S ={（ax ₁ mod n）、（ax ₂ mod n）、…（ax _ф（n） mod n）}

aはnとx_iに対して互いに素であるため nに対して互いに素であり、ax _i また、nに対して互いに素でなければなりません。したがって、Sのすべてのメンバーは、n未満であり、互いに素である整数です。

Sには重複はありません。

ax _iの場合 modnおよびn=ax _j mod n、x _i =x _j

$$ \ mathrm {したがって、\、\ Pi _ {i =1} ^ {\ phi \ left（n \ right）} \ left（ax_ {i} \、mod \、n \ right）=\ Pi _ { i =1} ^ {\ phi \ left（n \ right）} \、x_ {i}} $$

$$ \ mathrm {\ Pi _ {i =1} ^ {\ phi \ left（n \ right）} \、ax_ {i} \ equiv \ Pi _ {i =1} ^ {\ phi \ left（n \ right）} \、x_ {i} \ left（mod \、n \ right）} $$

$$ \ mathrm {a ^ {\ phi \ left（n \ right）} \、x \ left [\ Pi _ {i =1} ^ {\ phi \ left（n \ right）} \、x_ {i} \ right] =\ Pi _ {i =1} ^ {\ phi \ left（n \ right）} \、x_ {i} \ left（mod \、n \ right）} $$

$$ \ mathrm {a ^ {\ phi \ left（n \ right）} \ equiv 1 \ left（mod \、n \ right）} $$

オイラーのトーティエント関数

オイラーのトーティエント関数は、「n」の素数である「n」として一般に知られている与えられた整数までの正の整数を数える数学的な乗法関数であり、この関数を使用して、ex_{iの素数の数を理解できます。} 指定された整数「n」まで。

オイラーのトーティエント関数は、オイラーのファイ関数とも呼ばれます。これは、暗号化において重要な役割を果たします。 nより小さく、互いに素である整数の数を検出できます。 $ \ mathrm {Z_ {n} ^ {*}} $（nより小さく、nに互いに素な数）によって定義されるこれらの数のセット。

オイラーのトーティエント関数は、いくつかの点で有益です。これは、セキュリティ目標に使用できるRSA暗号化システムで使用できます。この関数は素数定理を扱い、大規模な計算の計算にも役立ちます。この関数は、代数計算や単純な数値に利用できます。

関数を示すために使用される記号はϕであり、ファイ関数とも呼ばれます。この関数には、実際の使用ではなく、より理論的な使用が含まれています。関数の賢明な要件は限られています。

この関数は、理論的な説明だけでなく、いくつかの実際的な例を通してよりよく理解できます。オイラーのトーティエント関数を計算するためのいくつかの規則があり、異なる数に対しては、異なる規則が使用されます。

オイラーのトーティエント関数ф（n）は、次のルールを使用して$ \ mathrm {Z_ {n} ^{*}}$の要素数を計算します-

• ф（1）=0。

• Pが素数の場合、ф（P）=P −1。

• mとnが互いに素の場合、ф（m x n）=ф（m）xф（n）。

• ф（P ^e ）=P ^e − p ^e−1 （Pが素数の場合。）

次の4つのルールを組み合わせて、ф（n）の値を取得し、nを因数分解することができます

$$ \ mathrm {n =P_ {1} ^ {e1} \、x \、P_ {2} ^ {e2} x \ cdot \ cdot \ cdot P_ {k} ^ {ek}} $$

$$ \ mathrm {\ phi \ left（n \ right）=\ left（P_ {1} ^ {e1} -P_ {1} ^ {e1-1} \ right）\ left（P_ {2} ^ {e2 }-P_ {2} ^ {e2-1} \ right）x \ cdot \ cdot \ cdot x \ left（P_ {k} ^ {ek}-P_ {k} ^ {ek-1} \ right）} $ $

ф（n）を見つけることの難しさは、nの因数分解を見つけることの難しさに依存します。