18783^3323 (mod20227)の計算

質問

暗号化の計算を必要としています。

18783^3323 (mod20227) のような大きい桁数を計算できる　サイト、またはフリーのアプリケーションを教えてください。　よろしくお願いします。

回答No.1

info222_ · ベストアンサー

WorframAlphaサイトで計算すると
http://www.wolframalpha.com/
mod(18783^3323,20227) ⇒ 4961

フリーソフトの数式処理ソフトwxMaxima
ダウンロード先URL:
http://sourceforge.jp/projects/sfnet_wxmaxima/releases/
で計算しても
mod(18783^3323,20227);
4961
と同じ結果が得られます。

なので合っていると思います。

回答No.2

stomachman

Excelで計算してみました。
　　mod(K^(p+q), N) = mod(mod(K^p,N)×mod(K^q,N), N)
　　mod(K^(pq), N) = mod(mod(K^p,N))^q, N)
という関係を利用します。
　　K=18783, N = 20227
の場合、mod(K^3,N)はエラーになっちゃうけれども
　　mod(K^2,N)=1755
なら計算できたんで、
　　3323 = 3321+2
　　3321 = 369×3
　　1107 = 369×3
　　369 = 41×3
　　123 = 41×3
　　36 = 12×3
　　41 = 36+5
　　12 = 6×2
　　6 = 3×2
　　5 =2+3
　　3 = 2+1
と分解すると、
　　mod(K^3,N)=mod(mod(K^2,N)×mod(K,N), N)=14382
　　mod(K^5,N)=mod(mod(K^3,N)×mod(K^2,N), N)=17341
　　mod(K^6,N)=mod(mod(K^3,N)×mod(K^3,N), N)=622
　　mod(K^9,N)=mod(mod(K^6,N)×mod(K^3,N), N)=5270
　　mod(K^12,N)=mod(mod(K^6,N)^2, N)=2571
　　mod(K^36,N)=mod(mod(K^12,N)^3, N)=13643
　　mod(K^41,N)=mod(mod(K^36,N)×mod(K^5,N), N)=8271
　　mod(K^123,N)=mod(mod(K^41,N)^3, N)=3755
　　mod(K^369,N)=mod(mod(K^41,N)^3, N)=5485
　　mod(K^1107,N)=mod(mod(K^41,N)^3, N)=10473
　　mod(K^3321,N)=mod(mod(K^41,N)^3, N)=8036
　　mod(K^3323,N)=mod(mod(K^3321,N)×mod(K^2,N), N)=4961

要するに数値を扱える範囲に収まるところまで、テキトーにこまかくばらしてやれば良いんです。

　実は、x^nを計算するのに、掛け算の回数が最小になるばらしかたを構成するアルゴリズムが知られています。たとえばx^9を計算するなら、
　　a = x×x;
　　b = a×x;
　　c = b×b;
　　d = b×c;
とやる。コンパイラに利用されている技術です。このアルゴリズムを応用すれば、
　　mod(K^(p+q), N) = mod(mod(K^p,N)×mod(K^q,N), N)
だけを使うやり方で、システマティックに手際良くばらせるんですが…

お礼

ありがとうございます　　excelで計算するのは　なかなか難しいですけど　自分でもやってみたいと思います。お二人ともベストアンサーをつけたかったんですが、レポートに使用させていただいた　NO.1の方につけさせていただきました。