Package org.apache.commons.numbers.primes

Class SmallPrimes

  • final class SmallPrimes
extends java.lang.Object
    Utility methods to work on primes within the int range.

    • Field Summary

      Fields 
      Modifier and Type Field Description
      (package private) static java.util.Map.Entry<java.util.Set<java.lang.Integer>,​int[]> PRIME_NUMBERS_AND_COPRIME_EQUIVALENCE_CLASSES
      A set of prime numbers mapped to an array of all integers between 0 (inclusive) and the least common multiple, i.e.
      (package private) static int[] PRIMES
      The first 512 prime numbers.
      (package private) static int PRIMES_LAST
      The last number in PRIMES.

    • Constructor Summary

      Constructors 
      Modifier Constructor Description
      private SmallPrimes()
      Utility class.

    • Method Summary

      All Methods Static Methods Concrete Methods 
      Modifier and Type Method Description
      (package private) static void boundedTrialDivision​(int n, int maxFactor, java.util.List<java.lang.Integer> factors)
      Extract factors between PRIME_LAST + 2 and maxFactors.
      (package private) static boolean millerRabinPrimeTest​(int n)
      Miller-Rabin probabilistic primality test for int type, used in such a way that a result is always guaranteed.
      (package private) static int smallTrialDivision​(int n, java.util.List<java.lang.Integer> factors)
      Extract small factors.
      (package private) static java.util.List<java.lang.Integer> trialDivision​(int n)
      Factorization by trial division.

      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

    • Field Detail

      • PRIMES

        static final int[] PRIMES
        The first 512 prime numbers.

        It contains all primes smaller or equal to the cubic square of Integer.MAX_VALUE. As a result, int numbers which are not reduced by those primes are guaranteed to be either prime or semi prime.

      • PRIMES_LAST

        static final int PRIMES_LAST
        The last number in PRIMES.

      • PRIME_NUMBERS_AND_COPRIME_EQUIVALENCE_CLASSES

        static final java.util.Map.Entry<java.util.Set<java.lang.Integer>,​int[]> PRIME_NUMBERS_AND_COPRIME_EQUIVALENCE_CLASSES
        A set of prime numbers mapped to an array of all integers between 0 (inclusive) and the least common multiple, i.e. the product, of those prime numbers (exclusive) that are not divisible by any of these prime numbers. The prime numbers in the set are among the first 512 prime numbers, and the int array containing the numbers undivisible by these prime numbers is sorted in ascending order.

        The purpose of this field is to speed up trial division by skipping multiples of individual prime numbers, specifically those contained in the key of this Entry, by only trying integers that are equivalent to one of the integers contained in the value of this Entry modulo the least common multiple of the prime numbers in the set.

        Note that, if product is the product of the prime numbers, the last number in the array of coprime integers is necessarily product - 1, because if product ≡ 0 mod p, then product - 1 ≡ -1 mod p, and 0 ≢ -1 mod p for any prime number p.

    • Constructor Detail

      • SmallPrimes

        private SmallPrimes()
        Utility class.

    • Method Detail

      • smallTrialDivision

        static int smallTrialDivision​(int n,
                              java.util.List<java.lang.Integer> factors)
        Extract small factors.
        Parameters:
        n - Number to factor, must be > 0.
        factors - List where to add the factors.
        Returns:
        the part of n which remains to be factored, it is either a prime or a semi-prime.

      • boundedTrialDivision

        static void boundedTrialDivision​(int n,
                                 int maxFactor,
                                 java.util.List<java.lang.Integer> factors)
        Extract factors between PRIME_LAST + 2 and maxFactors.
        Parameters:
        n - Number to factorize, must be larger than PRIME_LAST + 2 and must not contain any factor below PRIME_LAST + 2.
        maxFactor - Upper bound of trial division: if it is reached, the method gives up and returns n.
        factors - the list where to add the factors.

      • trialDivision

        static java.util.List<java.lang.Integer> trialDivision​(int n)
        Factorization by trial division.
        Parameters:
        n - Number to factor.
        Returns:
        the list of prime factors of n.

      • millerRabinPrimeTest

        static boolean millerRabinPrimeTest​(int n)
        Miller-Rabin probabilistic primality test for int type, used in such a way that a result is always guaranteed.

        It uses the prime numbers as successive base therefore it is guaranteed to be always correct (see Handbook of applied cryptography by Menezes, table 4.1).

        Parameters:
        n - Number to test: an odd integer ≥ 3.
        Returns:
        true if n is prime, false if it is definitely composite.