はじめに
通常、この資料には豊富な数式が用意されており、数学者向けに設計されています。 ハードウェアレベルでマイクロエレクトロニクスにこの方法を適用するという観点から、単純な数値例を使用して最もアクセスしやすいものにしようとします。 数値の例では、明確にするためにp = 11が使用されます。
問題の声明
次の形式の乗算を実行する必要があるとします：
res = (a*b) mod p 、ここで
0 <= a < p0 <= b < ppは素数です。
mod p剰余をモジュロで求める演算。
そして、乗算操作や除算の残りをそのままとる操作がない低レベルで実行する必要があります。そうでない場合は、非常に困難です（たとえば、電子デバイスで）。
最も簡単な解決方法
- 最初に頭に浮かぶのは、乗算してから除算して残りを取得することです。 このアプローチには存在する権利がありますが、操作の数の点で非常にコストがかかり、実装が非常に困難です。
- 2番目に考えられることは、サイズ
p 2次元乗算テーブルを使用してこの演算を実装することです。 p小さい場合は理にかなっていますが、pが増加すると、テーブルを格納するコストが2次的に増加します（図1）。
図1. p = 11のpを法とする乗算表インデックスメソッドの乗数
ただし、次元
p 1つの（または2つの便宜のために）テーブルを必要とするメソッドがあります。 この方法は、乗算を加算で置き換えることに基づいています。 また、次の図（図2）で概略的に説明できます。
図2.インデックスの乗算。これが可能な理由を説明しましょう。 数値のインデックス表現は、
p法とする逆微分根の概念に基づいています[1]。 原始根wは整数であり、その累乗
0, 1, 2, …, (p-2)は
p法とする非反復剰余を与えます。 素数根は常に任意の素数
p存在します（1801年にガウスによって証明されました）。 この場合、区間
(0; p)各整数
qは、
q = (w i ) mod pような数値
i関連付けることができます。 したがって、次の通信を取得します。
(a*b) mod p <-> w^((ia+ib) mod (p-1)) [2]。
モジュール
p = 11例を考えてみましょう。 このモジュラス値のプリミティブルート
wは2です
wを0、1、... 9の累乗にすると、一意の結果が得られることを簡単に確認できます。
- （2 0 ）
mod 11 = 1 mod 11 = 1 - （2 1 ）
mod 11 = 2 mod 11 = 2 - （2 2 ）
mod 11 = 4 mod 11 = 4 - （2 3 ）
mod 11 = 8 mod 11 = 8 - （2 4 ）
mod 11 = 16 mod 11 = 5 - （2 5 ）
mod 11 = 32 mod 11 = 10 - （2 6 ）
mod 11 = 64 mod 11 = 9 - （2 7 ）
mod 11 = 128 mod 11 = 7 - （2 8 ）
mod 11 = 256 mod 11 = 3 - （2 9 ）
mod 11 = 512 mod 11 = 6
通常の
{q} {i}表現とインデックス
{i}表現間の変換テーブルを取得するには、結果の値のペアを昇順で並べ替える必要があります。 したがって、モジュール
p = 11の直接変換テーブルは次のようになります。
また、
p = 11モジュールの逆変換テーブルは次のようになります。
式（3 * 5）
mod 11の値を見つけます。数字3と5には、対応するインデックス8と4があります（表1を参照）。 これらのインデックスをモジュロ（11-1）= 10で合計すると、結果（8 + 4）
mod 10 = 12
mod 10 = 2が得られます。表2から、インデックス2の逆変換により4に等しい最終結果が得られます。
考慮された例のm = 11を法とするインデックス乗数の構造図を次の図に示します（図3）。
図3. p = 11のインデックス乗数のスキーム入力のゼロ値
テーブルをよく見ると、入力データにゼロ値がないことがわかります。 これは、
iの値がない場合に
w i ！= 0であるという事実によるものです。 このケースは個別に処理されます（または、処理の特別なルールを持つ特異点の概念が導入されます）。 乗数の入力の1つに0が表示される場合、出力にも0があります。これは、乗算の規則から直接に従います。
乗算器の並列化
乗算をさらに高速に実行できることがわかりました。 数
(p-1)を相互に単純な因子
p-1 = m1*m2*…*mrに分割できる場合、加算演算はより小さな次元の
r加算演算に分割できます。 この場合、インデックスは次の式に従って長さ
rベクトルに変換されます：（
i mod m1, i mod m2, …, i mod mr ）。 そして、加算はベクトルの各要素に対して独立して実行されます。
これを例として考えてください。
p = 11の場合、
p -1 = 10の値であり、相互に単純な要因に一意に分割できます：10 = 2 * 5（
m1 = 2、
m2 = 5）。 この場合、表1は次のように記述できます。
| q | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 私は | 0 | 1 | 8 | 2 | 4 | 9 | 7 | 3 | 6 | 5 |
（i mod 2、i mod 5） | （0、0） | （1、1） | （0、3） | （0、2） | （0、4） | （1、4） | （1、2） | （1、3） | （0、1） | （1、0） |
それぞれ次のような逆変換の表：
（i mod 2、i mod 5） | （0、0） | （0、1） | （0、2） | （0、3） | （0、4） | （1、0） | （1、1） | （1、2） | （1、3） | （1、4） |
| q | 1 | 9 | 4 | 3 | 5 | 10 | 2 | 7 | 8 | 6 |
前の例のように、値（3 * 5）
mod 11を見つけます。まず、テーブルで対応するベクトルを探します：3->（0、3）、5->（0、4）。 次に、要素ごとに要素を追加します（（0 + 0）
mod 2、（3 + 4）
mod 5）=（0、2）。 逆変換の表から答えを見つけます：（0、2）-> 4.並列乗算スキームを以下に示します（図4）：
図4. p = 11の並列インデックス乗数のスキームプリミティブルートを探す方法は？
正直に言うと、私はこの質問をしませんでした。 2からpまでの徹底的な検索を使用します。 または、既製のシーケンス
oeis.org/A046145を使用できます。 より効率的な方法がある場合は、コメントを書いてください。
加算器モジュロ（p-1）を設計する方法は？
加算器モジュロ
(p-1)の入力データの特性により、つまり、両方の入力が
p-1より小さい数を受け取るため、合計が
2*(p-1)より小さいことを意味します。 このことから、標準加算器のいずれかを使用でき、その出力は次のアルゴリズムに従って調整されます：値が
(p-1)以上の場合、結果から
(p-1)減算し、そうでない場合はそのままにします。
Verilogジェネレーター
余暇には、モジュロインデックス乗数を実装するためにVerilogのオンラインジェネレーターを作成しました。 そこには、彼の作品の図が描かれています。
11を法とする乗算のVerilogモジュロ31乗算のVerilog1000までの任意の数のVerilogジェネレーター文学
[1]
en.wikipedia.org/wiki/%D0%9F%D0%B5%D1%80%D0%B2%D0%BE%D0%BE%D0%B1%D1%80%D0%B0%D0% B7％D0％BD％D1％8B％D0％B9_％D0％BA％D0％BE％D1％80％D0％B5％D0％BD％D1％8C_％28％D1％82％D0％B5％D0％ BE％D1％80％D0％B8％D1％8F_％D1％87％D0％B8％D1％81％D0％B5％D0％BB％29[2]
www.researchgate.net/publication/224735018_A_fast_RNS_Galois_field_multiplier著者から
記事への追加がある場合は、コメントでそれらを見て喜んでいます。 それでも、誰かが投げる何かを持っている場合、記事は詳細とのリンクで貧弱であることが判明しました。 =）