Package org.apache.commons.numbers.primes

Class SmallPrimes

java.lang.Object
org.apache.commons.numbers.primes.SmallPrimes
final class SmallPrimes extends Object
Utility methods to work on primes within the int range.

  • Field Details

    • 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 Map.Entry<Set<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 Details

    • SmallPrimes

      private SmallPrimes()
      Utility class.

  • Method Details

    • smallTrialDivision

      static int smallTrialDivision(int n, List<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, List<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 List<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.