Class SmallPrimes

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

  • Field Details

    • 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 Details

    • SmallPrimes

      private SmallPrimes()
      Hide utility class.

  • Method Details

    • smallTrialDivision

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