LucasTest

LucasTest.java

import java.math.BigInteger;

public class LucasTest {
  public static void main(String[] args) {
    int p = 521;
    System.out.println(lucas(p - 1, BigInteger.valueOf(2).pow(p).subtract(BigInteger.ONE)));
  }

  static BigInteger lucas(int n, BigInteger mod) {
    return lucasIter(BigInteger.valueOf(4), n, mod);
  }

  static BigInteger lucasIter(BigInteger a, int n, BigInteger m) {
    BigInteger r = a.mod(m);
    if (n == 1) return r;
    BigInteger b = r.multiply(r).mod(m).subtract(BigInteger.valueOf(2));
    if (b.compareTo(BigInteger.ZERO) < 0) b = b.add(m);
    return lucasIter(b, n - 1, m);
  }
}