Skip to content

Instantly share code, notes, and snippets.

@EdDuarte
Last active August 4, 2019 23:16
Show Gist options
  • Save EdDuarte/ea564df58d317f98ec0d811c32ca6608 to your computer and use it in GitHub Desktop.
Save EdDuarte/ea564df58d317f98ec0d811c32ca6608 to your computer and use it in GitHub Desktop.
Primality tests (Trial division, Fermat and Miller-Rabin) in Java.
/**
* @author Ed Duarte (<a href="mailto:hi@edduarte.com">hi@edduarte.com</a>)
*/
public class Prime {
private java.security.SecureRandom random;
public Prime() {
this.random = new java.security.SecureRandom();
}
/**
* Tests if n is a prime number using Trial division.
*/
public boolean isPrime(long n) {
if (n < 2) return false;
if (n == 2 || n == 3) return true;
if (n % 2 == 0 || n % 3 == 0) return false;
long sqrtN = (long) Math.sqrt(n) + 1;
for (long i = 6L; i <= sqrtN; i += 6) {
if (n % (i - 1) == 0 || n % (i + 1) == 0) {
return false;
}
}
return true;
}
/**
* Tests if n is a prime number using Fermat primality test with certainty k.
*/
public boolean isProbablePrime1(long n, long k) {
for (int i = 0; i < k; i++) {
int alloc = 0;
long bound = n;
if (n > 4) {
alloc = 2;
bound = n - 4;
}
long v = alloc + randomPositiveLong(bound);
if (Math.pow(v, n - 1) % n != 1) {
return false;
}
}
return true;
}
/**
* Tests if n is a prime number using Miller-Rabin primality test with certainty k.
*/
public boolean isProbablePrime2(long n, long k) {
if (n < 2) return false;
if (n == 2 || n == 3) return true;
if (n % 2 == 0 || n % 3 == 0) return false;
for (long i = 0; i < k; i++) {
long v = 2 + randomBoundedLong(2, n - 2);
if (Math.pow(v, n - 1) % n != 1) {
return false;
}
}
return true;
}
public long randomBoundedLong(long minBound, long maxBound) {
return normalize(random.nextLong(), Long.MIN_VALUE, Long.MAX_VALUE, minBound, maxBound);
}
public long randomPositiveLong(long maxBound) {
long l = random.nextLong();
return normalize(l, Long.MIN_VALUE, Long.MAX_VALUE, 0, maxBound);
}
public static long normalize(long value, long oldMin, long oldMax, long newMin, long newMax) {
double percent = ((double) value - (double) oldMin) / ((double) oldMax - (double) oldMin);
return (long) ((percent * ((double) newMax - (double) newMin)) + newMin);
}
}
@EdDuarte
Copy link
Author

EdDuarte commented Aug 4, 2019

The following analysis is based on a number of tests to methods isPrime, isProbablePrime1 and isProbablePrime2 for numbers 1 to 200.

When the certainty is set to 1, both the Fermat test and the Miller-Rabin test will attempt to raise a random number to the power of the number being tested in order to possibly find non-primes. For all 46 prime numbers found between 1 and 200, the Fermat test successfully found 12 while the Miller-Rabin test found a measly 9. However, for all of the 154 non-primes, these tests successfully return a True Negative, so there are zero False Positives (Precision = 100%).

In other words, when these tests say that a certain number is a prime number, we know with a high degree of confidence that this number is indeed a prime (there are no False Positives), but when these say that it is not prime, we do not know that it definitely isn't (as there are still False Negatives). This works similarly to how a Bloom Filter would (but in reverse), where we know if an element is definitely not part of a set but not if an element definitely is.

Moreover, while Trial Divisions can take between 16 to 20 μs on average, the Fermat test takes an average of 427.0 ns and the Miller-Rabin test takes an average of 5 μs. This means that both of the probabilistic tests are great candidates for usage in a resource-heavy environment or for cryptographic algorithms, but their usefulness is somewhat limited due to the high error-rate.

Fermat:

  • Accuracy = (TP + TN) / (TP + TN + FP + FN) ≈ 80%
  • Precision = TP / (TP + FP) = 100%
  • Recall = TP / (TP + FN) ≈ 13%
  • F-Measure = 2 * (Precision * Recall) / (Precision + Recall) ≈ 23%

Miller-Rabin:

  • Accuracy = (TP + TN) / (TP + TN + FP + FN) ≈ 82%
  • Precision = TP / (TP + FP) = 100%
  • Recall = TP / (TP + FN) ≈ 23%
  • F-Measure = 2 * (Precision * Recall) / (Precision + Recall) ≈ 37%

Although both tests provide 100% precision, Miller-Rabin has a better Recall and F-Measure, so it provides a lower probability of error. This error-rate can be reduced further the more these tests are repeated, so a higher certainty K will reduce the probability of error, but it will also increase the overall elapsed time. When the certainty is set to 10, Fermat takes 38.466 μs while Miller-Rabin takes 40.893 μs, but the number of False Negatives is decreased and the number of True Negatives is increased, improving test accuracy.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment