java 累乗後の数の余りを求める計算の結果が想定と異なっている問題

Question

RSA暗号のアルゴリズムを簡単に実装してみたのですが、暗号化した文章を復号化するときに失敗することがありました。
調べたところ"pow(tmpi,d) % n"の計算結果が関数電卓の結果と異なるときがあるのですが原因が分からないので教えていただきたいです。

該当のソースコード

import java.util.Scanner;
import java.util.ArrayList;
import java.util.List;

public class Main{
    public static void main(String[] args){

        //鍵共有
        int p = 3;
        int q = 43;
        int n = p*q; //129
        int pq2 = (p-1)*(q-1); // 84
        
        int i = 2;
        int judgement = 1;
        int e = 0;
        while(judgement == 1){ //ユークリッドの互除法でたがいに素なeを求める
            if(Calc.euclid(pq2,i) == 1){ //eが求まった場合
                e = i;
                break;
            };
            i++;
        }

        System.out.println("e = " + e);

        int d = 0;
        while(judgement == 1){ //dを求める
            int tmp = (e*i) % pq2; //余りを求め1なら終了
            if(tmp == 1){
                d = i;
                break;
            }
            i++;
        }
        System.out.println("d = " + d);


        Scanner scan = new Scanner(System.in);
        System.out.println("暗号化なら1 , 復号化なら2 を入力してください。");
        String judge = scan.nextLine(); 

        //暗号化
        if(judge.equals("1")){
            List<String> C = new ArrayList<>();
            System.out.println("暗号化したい文章を入力してください。");
            System.out.print("M = ");
        
            String word = scan.nextLine();//文章の読み込み
            C = Encryption.Enc(word, e, n);//暗号化

            System.out.print("C = "); //暗号文の表示
            for(i=0;i<C.size();i++){
                System.out.print(C.get(i));
            }
            scan.close();
        }
        
        //復号化
        else if(judge.equals("2")){
            List<Character> M = new ArrayList<>();
            List<String> Mtmp = new ArrayList<>();

            System.out.println("復号化したい文章を入力してください。");
            System.out.print("C = ");
            String word = scan.nextLine();
            for(int j=0;j<word.length();j++){ //8文字ごとに切り出し
                String tmps = word.substring(j, j+8);
                j = j+7;
                Mtmp.add(tmps);
            }

            M = Decryption.Dec(Mtmp, d, n); //復号化

            System.out.print("M = "); //平文の表示
            for(int j=0;j<M.size();j++){
                System.out.print(M.get(j));
            }
            scan.close();
        }
        
    }
    
}
 ----------------------------------------------------------------------------------
import java.util.ArrayList;
import java.util.List;

public class Encryption {
    public static List<String> Enc(String word, int e, int n){
        List<Integer> M = new ArrayList<>();
        List<String> C = new ArrayList<>();

        for(int i=0;i<word.length();i++){ //平文をASCⅡコードに変換し一文字ずつリストに格納
            char tmpc = word.charAt(i);
            System.out.println("ASC2 = " + (int)tmpc);
            M.add((int)tmpc);
        }

        for(int i=0;i<word.length();i++){ //暗号化を行う
            int tmpi = M.get(i);
            double tmpd = Math.pow(tmpi,e) % n; //暗号獲得
            System.out.println("10進数 = " + tmpd);
            Integer tmpin = Integer.valueOf((int)tmpd); //int型に変換
            System.out.println("int = " + tmpin);
            String tmps = Integer.toBinaryString(tmpin); //2進数に変換
            System.out.println("2進数 = " + tmps);
            Integer tmpin2 = Integer.valueOf(tmps); //int型に変換
            System.out.println("int = " + tmpin2);
            String tmps2 = String.format("%08d", tmpin2); //0パディング
            C.add(tmps2);
        }

        return C;

    }
}

 ----------------------------------------------------------------------------------
import java.util.ArrayList;
import java.util.List;

public class Decryption {
    public static List<Character> Dec(List<String> C, int d, int n){
        List<Character> M = new ArrayList<>();

        for(int i=0;i<C.size();i++){ //復号化
            int tmpi = Integer.parseInt(C.get(i),2); //10進数に変換
            System.out.println("10進数 = " + tmpi);

            System.out.println("d : n = " + d + " : " + n);
            double tmpid = Math.pow(tmpi, d);
            System.out.println("tmpi^d  : " + tmpi + "^" + d + " = " + Math.pow(tmpi, d));           
            System.out.println("tmpid % n : " + tmpid + "%" + n + " = " + tmpid % n);

            double tmpd = Math.pow(tmpi,d) % n; //復号化
            System.out.println("変換後 = " + tmpd);
            int tmpin = Integer.valueOf((int)tmpd); //int型に変換
            System.out.println("int = " + tmpin);
            M.add((char)tmpin); //ASCⅡに変換
        }

        return M;
    }
}

----------------------------------------------------------------------------------
public class Calc {
    public static int euclid(int n, int i){
        int big = Math.max(n, i);
        int small = Math.min(n, i);

        int sur = big % small;

        if(sur == 0){
            return small;
        }

        sur = euclid(small, sur);

        return sur;
    }

}

実行結果

C:\Users\RSA暗号_ソースコード>java Main
e = 5
d = 17
暗号化なら1 , 復号化なら2 を入力してください。
1
暗号化したい文章を入力してください。
M = a
ASC2 = 97
10進数 = 16.0
int = 16
2進数 = 10000
int = 10000
C = 00010000
C:\Users\RSA暗号_ソースコード>java Main
e = 5
d = 17
暗号化なら1 , 復号化なら2 を入力してください。
2
復号化したい文章を入力してください。
C = 00010000
10進数 = 16
d : n = 17 : 129
tmpi^d  : 16^17 = 2.9514790517935283E20
tmpid % n : 2.9514790517935283E20%129 = 97.0
変換後 = 97.0
int = 97
M = a
C:\Users\RSA暗号_ソースコード>java Main
e = 5
d = 17
暗号化なら1 , 復号化なら2 を入力してください。
1
暗号化したい文章を入力してください。
M = I
ASC2 = 73
10進数 = 55.0
int = 55
2進数 = 110111
int = 110111
C = 00110111
C:\Users\RSA暗号_ソースコード>java Main
e = 5
d = 17
暗号化なら1 , 復号化なら2 を入力してください。
2
復号化したい文章を入力してください。
C = 00110111
10進数 = 55
d : n = 17 : 129
tmpi^d  : 55^17 = 3.856254795069075E29
tmpid % n : 3.856254795069075E29%129 = 64.0
変換後 = 64.0
int = 64
M = @

追記

３回目の実行時にclass Decryptionのdouble tmpd = Math.pow(tmpi,d) % n; //復号化の計算結果が73になると想定したが実行すると64が返されてしまう点が違っている。

Comments

[y_waiwai]

どこがどういうふうに違ってるんでしょうか

[tamintya]

ご指摘ありがとうございます。
違っている点を質問文に追記しました。

Answer 1

double tmpd = Math.pow(tmpi,d) % n; //復号化 など各所でdoubleを使っていますが、

doubleの有効桁数は10進数で約16桁です。
Math.pow(a,b)の戻り値はdoubleなので結果が大きな値になる累乗の計算はどうしようもありません。

値が大きくなることを避けるために累乗の剰余算については、
「a*bをnで割った余りは、(aをnで割った余り)*(bをnで割った余り) をnで割った余りに等しい」
という性質を使って普通計算します。

端的に言えば、掛け算を複数回した余りを求めるときは、掛け算1回ごとに余りを取ります。
例えば(a*b*c)%nは((((a%n)*b)%n)*c)%nと計算した方がいいということです。

参考
mod の下での指数計算をするアルゴリズムを python で書いてみる - わかばめにっき

Comments

[tamintya]

回答ありがとうございます。そのような性質があることを初めて知りました！
しかし、ご指摘の計算方法を変更しても結果が変わらないのですが他にどの部分に間違いがあるのでしょうか。

[ozwk]

追記編集しました

[tamintya]

掛け算1回ごとに余りを求める用に変更したところ目的の結果を得ることができました。
分かりやすく説明していただきありがとうございました。