私はSAFER +アルゴリズムを実装しようとしています。 、パワー関数の結果をもたらす非常に大きくすることができる大きな数値のモジュラスパワー
pow(45, x) mod 257
変数xは、従って、0から255の範囲とすることができるこのようバイトであり、そして：アルゴリズムは次のように累乗関数の係数を求める必要32ビットまたは64ビットの整数を使用して実装されている場合、不正な値。
この計算はどのように実行できますか？
いくつかの擬似コード
function powermod(base, exponent, modulus) {
if (base < 1 || exponent < 0 || modulus < 1)
return -1
result = 1;
while (exponent > 0) {
if ((exponent % 2) == 1) {
result = (result * base) % modulus;
}
base = (base * base) % modulus;
exponent = floor(exponent/2);
}
return result;
}
各操作後弾性率低減、繰り返し二乗によってべき乗を実行
powermod(45, x, 257)
基本的なアプローチは、指数ビットに応じて2乗または乗算し、各ステップでモジュラ減算を実行することです。アルゴリズムは(binary) modular exponentiationと呼ばれます。
を呼び出します。これは非常に標準的な手法です。 45^13 mod 257：
まず計算45^2、45^4、45^8 MOD 257：
45^2のmod 257 = 2025のmod 257 = 226
Aは一例を働い
45^4のmod 257 = 226^2のmod 257 = 51076のmod 257 = 190
45^8のmod 257 = 190^2のmod 257 = 36100のmod 257 = 120
は、結果を得るために、これらを結合する13のバイナリ拡張を使用する：
^13 MOD 25745^13のmod 257 = 45^1 * 45^4 * 45^8 MOD 257
45 = 45 * 190 * 120 257
45^13のmod 257 = 69 * 120 MOD 257
45^13のmod 257 = 8280のmod 257 = 8550 * 120 MOD MOD 257
45^13のMOD 257
45^13のmod 257 = 56
注計算の中間結果は、* 257 257よりも大きいことはありませんので、これは容易に32ビット整数型で行うことができます。
最も美しい答え.. – Kokizzu
は、単純なアイデンティティを考えてみましょう：
mod(A^2,p) = mod(A,p)*mod(A,p)
はまた、あなたが計算したい最後の指数のバイナリ表現を知っていれば
A^4 = (A^2)^2
他の勢力が自明に計算されていることに注意してください。
どのようなプログラミング言語ですか？ – esskar
@esskar：私が完全に間違っていないと、モジュラス空間で力を計算するための特別な公式があることを正しく覚えていないと、モジュラス計算が問題の重要な部分です。したがって、問題は言語に依存しません。 – thiton
入門読書：[整数の乗法群]（http://en.wikipedia.org/wiki/Multiplicative_group_of_integers_modulo_n#Powers_of_odd_primes）これは私が答えるにはあまりにもずっと前ですが、誰かが覚えているかもしれません。 – thiton