回答編集履歴
3
追記
answer
CHANGED
|
@@ -7,5 +7,8 @@
|
|
|
7
7
|
「`a*bをnで割った余り`は、`(aをnで割った余り)*(bをnで割った余り)` を`n`で割った余りに等しい」
|
|
8
8
|
という性質を使って普通計算します。
|
|
9
9
|
|
|
10
|
+
端的に言えば、掛け算を複数回した余りを求めるときは、掛け算1回ごとに余りを取ります。
|
|
11
|
+
例えば`(a*b*c)%n`は`((((a%n)*b)%n)*c)%n`と計算した方がいいということです。
|
|
12
|
+
|
|
10
13
|
参考
|
|
11
14
|
[mod の下での指数計算をするアルゴリズムを python で書いてみる - わかばめにっき](https://wakabame.hatenablog.com/entry/2017/09/21/012844)
|
2
修正追記
answer
CHANGED
|
@@ -1,7 +1,11 @@
|
|
|
1
1
|
`double tmpd = Math.pow(tmpi,d) % n; //復号化` など各所で`double`を使っていますが、
|
|
2
2
|
|
|
3
3
|
`double`の有効桁数は10進数で約16桁です。
|
|
4
|
+
`Math.pow(a,b)`の戻り値は`double`なので結果が大きな値になる累乗の計算はどうしようもありません。
|
|
4
5
|
|
|
5
|
-
な
|
|
6
|
+
値が大きくなることを避けるために累乗の剰余算については、
|
|
6
|
-
「a
|
|
7
|
+
「`a*bをnで割った余り`は、`(aをnで割った余り)*(bをnで割った余り)` を`n`で割った余りに等しい」
|
|
7
|
-
という性質を使って普通計算します。
|
|
8
|
+
という性質を使って普通計算します。
|
|
9
|
+
|
|
10
|
+
参考
|
|
11
|
+
[mod の下での指数計算をするアルゴリズムを python で書いてみる - わかばめにっき](https://wakabame.hatenablog.com/entry/2017/09/21/012844)
|
1
追記
answer
CHANGED
|
@@ -1,3 +1,7 @@
|
|
|
1
|
-
`double tmpd = Math.pow(tmpi,d) % n; //復号化`
|
|
1
|
+
`double tmpd = Math.pow(tmpi,d) % n; //復号化` など各所で`double`を使っていますが、
|
|
2
2
|
|
|
3
|
-
`double`の有効桁数は10進数で約16桁です。
|
|
3
|
+
`double`の有効桁数は10進数で約16桁です。
|
|
4
|
+
|
|
5
|
+
なお、累乗の剰余算については、
|
|
6
|
+
「aのk乗をnで割った余りは、(aをnで割った余り)のk乗 をnで割った余りに等しい」
|
|
7
|
+
という性質を使って普通計算します。
|