Package org.apache.commons.math3.primes

Class SmallPrimes

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

    • Field Summary

      Fields 
      Modifier and Type Field Description
      static int[] PRIMES
      The first 512 prime numbers.
      static int PRIMES_LAST
      The last number in PRIMES.

    • Constructor Summary

      Constructors 
      Modifier Constructor Description
      private SmallPrimes()
      Hide utility class.

    • Method Summary

      All Methods Static Methods Concrete Methods 
      Modifier and Type Method Description
      static int boundedTrialDivision​(int n, int maxFactor, java.util.List<java.lang.Integer> factors)
      Extract factors in the range PRIME_LAST+2 to maxFactors.
      static boolean millerRabinPrimeTest​(int n)
      Miller-Rabin probabilistic primality test for int type, used in such a way that a result is always guaranteed.
      static int smallTrialDivision​(int n, java.util.List<java.lang.Integer> factors)
      Extract small factors.
      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

        public 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

        public static final int PRIMES_LAST
        The last number in PRIMES.

    • Constructor Detail

      • SmallPrimes

        private SmallPrimes()
        Hide utility class.

    • Method Detail

      • smallTrialDivision

        public static int smallTrialDivision​(int n,
                                     java.util.List<java.lang.Integer> factors)
        Extract small factors.
        Parameters:
        n - the number to factor, must be > 0.
        factors - the 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

        public static int boundedTrialDivision​(int n,
                                       int maxFactor,
                                       java.util.List<java.lang.Integer> factors)
        Extract factors in the range PRIME_LAST+2 to maxFactors.
        Parameters:
        n - the number to factorize, must be >= PRIME_LAST+2 and must not contain any factor below PRIME_LAST+2
        maxFactor - the upper bound of trial division: if it is reached, the method gives up and returns n.
        factors - the list where to add the factors.
        Returns:
        n or 1 if factorization is completed.

      • trialDivision

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

      • millerRabinPrimeTest

        public 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 n is definitely composite.