Fermat's little theorem in java

Question

I'm trying to solve this question using Java but can't seem to figure out what is wrong with my code.

Is the difference of 5^30000 and 6^123456 a multiple of 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

It returns 0.

1

int is only 32-bits. – Elliott Frisch Jan 31 '16 at 08:11

Derlin · Answer 1 · 2016-01-31T08:24:33.277

Did you notice that 5^30000 equals roughly

1.25930254358409145729153078521520405922516958025249... × 10^20969 ??

You will clearly have some overflow issues with these kind of inputs.

For large powers with modulo, you can use the modular exponentiation method, based on theses rules:

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

From wikipedia, here is the pseudocode:

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

score 1 · Answer 2 · answered Feb 01 '16 at 00:46

I solved my own question. The issue was I was using int and had to use BigInteger.

Here's my solution.

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

Fermat's little theorem in java

2 Answers2