原始根の計算方法

コンテンツ

• 説明書

原始根の計算は、暗号学や数論において有用なスキルです。 g mod pがオーダーモジュラスp-1を持つ場合、数値 "g"は与えられた素数 "p"の原始根です。これは、 "g1 mod p"、 "g2 mod p"から "g（p-1）mod p"のリストに、1から（p-1）までのすべての整数が含まれることを意味します。原始根を効率的に計算するための既知のアルゴリズムはありません。最も簡単な方法は、2から（p-1）までの各可能な数を試すことです。

説明書

モジュラ算術の一般的な用途は、算術係数12を使用するポインタクロックです。 （Hemera Technologies / PhotoObjects.net / Getty Images）

1. 5のような素数「p」を選択してください。素数にはそれ自体と1を超える約数はありません。たとえば、4は素数ではありません "4/2 = 2"、それはその約数の1つとして2があります。

2. 1から（p-1）までの各整数 "n"に対して "2 ^ n mod p"を計算します。例を使用すると、 "p"は5で、1から4までの "n"に対して "2 ^ n mod 5"を計算します。これによりリストが生成されます。

   2 ^ 1 = 2 mod 5 = 2 2 ^ 2 = 4 mod 5 = 4 2 ^ 3 = 8 mod 5 = 3 2 ^ 4 = 16 mod 5 = 1

3. 数字のリストに5つの痕跡がすべて含まれていることを確認してください。リスト2、4、3、および1が適格であるため、2は剰余5を含む原始根です。代わりに、リストが4のリストである2,1,4および1であれば、4はそうではありません。数3がリストにないため、原始根。

4. 5未満のすべての整数に対して前の手順を繰り返します。 3番は残り5番の原始根でもありますが、4番はそうではありません。その場合、2と5が5の原始根です。