在Java中的費馬的小定理

Question

我想用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 

從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 

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