如何在java中获取大数字的剩余部分

Question

有没有解决这个问题的方法？为什么它返回541而不是3.

public class Test {
    public static void main(String[] args) {
        double a = Math.pow(3, 561);

        // it returns 541 instead of 3
        System.out.println(a % 561);
    }
}

Answer 1

根据费马的小定理:

Math.pow(a, p) % p == a % p

所以:

Math.pow(3, 561) % 561 = 3 % 561 = 3

因此,您不需要进行繁重的计算.只是数学.

Answer 2

doubles实际上并不像整数那样.Java的真正整数类型是java.math.BigInteger.

public static void main(String[] args) {
    BigInteger a = new BigInteger("3").pow(561);
    System.out.println(a.mod(new BigInteger("561")));
}

Answer 3

该BigInteger课程有一个专门的方法:

import java.math.BigInteger;

public class BigModPow
{
    public static void main(String[] args)
    {
        BigInteger b = new BigInteger("3");
        BigInteger e = new BigInteger("561");
        BigInteger m = new BigInteger("560");
        BigInteger result = b.modPow(e, m);
        System.out.println(result);
    }
}

(编辑:我将模数改为与指数不同的值,以表明计算了一个非平凡的结果 - 尽管561不是素数)