费马在java中的小定理

我正在尝试使用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。

Answer 1

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

1.25930254358409145729153078521520405922516958025249... × 10^20969 ??

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

对于具有模数的大功率，您可以使用基于这些规则的模幂运算方法：

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

从维基百科 ，这是伪代码：

 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 

Answer 2

我解决了自己的问题。 问题是我使用int并且不得不使用BigInteger。

这是我的解决方案。

 import java.math.*; import java.util.*; public class fermat { public static BigInteger fermat(BigInteger x, BigInteger y, BigInteger n){ return (x.modPow(y,n)); } public static void main(String[] argv) { BigInteger a=new BigInteger("5"); BigInteger b=new BigInteger("30000"); BigInteger c=new BigInteger("31"); BigInteger d=new BigInteger("6"); BigInteger e=new BigInteger("123456"); BigInteger f=new BigInteger("31"); BigInteger result1=fermat(a,b,c); System.out.println(result1); BigInteger result2=fermat(d,e,f); System.out.println(result2); } }//end of class