java - Fermat的Java小定理

This question already has answers here:

Large Numbers in Java
                                
                                    （6个答案）
                                
                        
                4年前关闭。
            
        

我正在尝试使用Java解决此问题，但似乎无法弄清楚我的代码出了什么问题。

5 ^ 30000和6 ^ 123456的差是31的倍数吗？

public class fermat {
  public static int fermat(int x, int y, int n){
    return (int)(Math.pow(x,y)%n);
  }
 public static void main(String[] args) {
   int result1=fermat(5,30000,31);
   int result2=fermat(6,123456,31);
   System.out.println(result1);
   System.out.println(result2);
  } // main
} // class Fermat

返回0。

最佳答案

您是否注意到5 ^ 30000大致等于

1.25930254358409145729153078521520405922516958025249... × 10^20969 ??

这些输入显然会带来一些溢出问题。

对于具有模数的大幂，可以根据以下规则使用模幂运算：

c mod m = (a ⋅ b) mod m
c mod m = [(a mod m) ⋅ (b mod m)] mod m

从wikipedia，这是伪代码：

function modular_pow(base, exponent, modulus)
    if modulus = 1 then return 0
    c := 1
    for e_prime = 1 to exponent
        c := (c * base) mod modulus
    return c