コハンスキー乗算

コハンスキー乗算^[1]は、係数が大きい場合（通常数百ビット）にモジュラ演算（乗算またはそれに基づく演算、例えば指数関数）を効率的に実行できるようにするアルゴリズムです。これは特に数論と暗号化の分野で応用されています。たとえば、RSA暗号システムとディフィー・ヘルマン鍵交換です。

ハードウェアで大きな整数の乗算を実装する最も一般的な方法は、乗数を2 進数で表現し、最上位ビットから始めて 1 ビットずつビットを列挙し、アキュムレータに対して次の操作を実行することです。

1. アキュムレータの内容を 2 倍にします (通常の場合のように、アキュムレータが数値を 2 進数で格納している場合、これは実際の計算を必要としない単純な「左シフト」です)。
2. 乗算器の現在のビットが 1 の場合、被乗数を累算器に追加します。0 の場合は何もしません。

nビットの乗算器の場合、これにはnクロック サイクルかかります(各サイクルではシフトまたはシフトと加算のいずれかが実行されます)。

これをモジュラ乗算のアルゴリズムに変換するには、係数rで、各段階で条件付きで r を減算する必要があります。

1. アキュムレータの内容を 2 倍にします。
2. 結果がr以上の場合は、r を減算します。(同様に、アキュムレータからr を減算し、結果が負でない場合にのみ結果をアキュムレータに戻します)。
3. 乗算器の現在のビットが 1 の場合、被乗数を累算器に追加します。0 の場合は何もしません。
4. 加算の結果がr以上の場合は、r を減算します。加算が行われなかった場合は、何も行いません。

このアルゴリズムは機能します。ただし、加算の速度に大きく依存します。

長整数の加算には、キャリーを右から左に伝播する必要があり、このプロセスが完了するまで最終結果がわからないという問題があります。キャリー伝播はキャリー先読みロジックで高速化できますが、それでも加算は必要以上に遅くなります (512 ビットの加算の場合、キャリー先読みを使用した加算は、キャリーをまったく使用しない加算よりも 32 倍遅くなります)。

非モジュラ乗算では、キャリー保存加算器を使用できます。これは、各桁位置からのキャリーを保存して後で使用することで時間を節約します。たとえば、111111111111+000000000010 を 111111111121 として計算し、キャリーが数値全体に伝播して真のバイナリ値 1000000000001 が得られるまで待つ必要はありません。バイナリ結果を得るためには、最終的な伝播も実行する必要がありますが、これは乗算の最後に 1 回だけ実行する必要があります。

残念ながら、上で概説したモジュラ乗算法では、 r を減算するかどうかを決定するために、各ステップで累積された値の大きさを知る必要があります。たとえば、アキュムレータの値が 10000000000000 より大きいかどうかを知る必要がある場合、キャリー保存表現 111111111121 は役に立たないため、比較を行うには実際の 2 進値に変換する必要があります。

したがって、キャリーセーブの速度かモジュラー乗算の速度のいずれかを得ることはできるが、両方を得ることはできないようです。

Kochanski アルゴリズムの原理は、アキュムレータ内の桁上げ保存値の最上位数ビットに基づいて、 r を減算するかどうかを推測することです。このような推測は、下位桁 (検査されていない) の潜在的な桁上げによって比較結果が無効になるかどうかを知る方法がないため、間違っている場合があります。したがって、次のようになります。

• 減算が必要なときに減算が行われなかった可能性があります。その場合、アキュムレータの結果はrよりも大きくなります(アルゴリズムはまだそれを認識していませんが)。そのため、次の左シフトの後に、アキュムレータから2 r を減算する必要があります。
• 減算が不要なときに行われた可能性があります。その場合、アキュムレータの結果は 0 未満になります (アルゴリズムはまだそれを認識していませんが)。そのため、次の左シフトの後、rまたは 2 r をアキュムレータに再度追加して、再び正の値にする必要があります。

本質的には、左にシフトするたびに倍増する誤った推測から生じるエラーと、エラーが何であるかの推測に基づいて rの倍数を加算または減算することによって行われる修正との間の競争が起こっています。

^[2]によれば、累算器の最上位4ビットを調べるだけで誤差を制限内に抑えることができ、累算器に追加する必要がある値は−2 r、− r、0、+ r、および+2 rのみであり、これらはすべて単純なシフトと否定演算によって瞬時に生成できることがわかります。

完全なモジュラー乗算の最後に、演算の真の 2 進結果を評価する必要があり、その後に発見される桁上げの結果としてrの追加の加算または減算が必要になる可能性があります。ただし、乗算の全体的なコストの大部分を占める数百のシフトおよび加算ステップで償却すると、その追加ステップのコストは小さくなります。

Brickell ^[3]は、アキュムレータの各桁ごとに電子機器の複雑さをさらに高める同様のアルゴリズムを公開している。

モンゴメリ乗算は、乗数を「逆方向に」（最下位桁を先頭に）処理し、累算器の最下位桁を使用して係数を追加するかどうかを制御する代替アルゴリズムです。これにより、桁上げを伝播する必要がなくなります。ただし、このアルゴリズムは、処理前にオペランドを特殊な形式に変換し、最後に結果を従来のバイナリに戻すために、2 つまたは 3 つの追加のモンゴメリ手順を実行する必要があるため、単一のモジュラー乗算には実用的ではありません。

• Kochanski, Martin. 「FAP4 チップの作成」。2018 年 5 月 9 日にオリジナルからアーカイブされました。実際のハードウェア実装の詳細を含む、アルゴリズムの非公式な説明と動機。