Package cc.redberry.rings.primes

Class SmallPrimes

java.lang.Object
cc.redberry.rings.primes.SmallPrimes
public final class SmallPrimes
extends Object
Prime factorization of 32-bit integers. The code is taken from Apache Commons Math.
Since:
1.0

  • Method Summary

    Modifier and Type Method Description
    static int boundedTrialDivision​(int n, int maxFactor, gnu.trove.list.array.TIntArrayList factors)
    Extract factors in the range PRIME_LAST+2 to maxFactors.
    static boolean isPrime​(int n)
    Primality test: tells if the argument is a (provable) prime or not.
    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 nextPrime​(int n)
    Return the smallest prime greater than or equal to n.
    static int[] primeFactors​(int n)
    Prime factors decomposition.
    static int smallTrialDivision​(int n, gnu.trove.list.array.TIntArrayList factors)
    Extract small factors.

    Methods inherited from class java.lang.Object

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

  • Method Details

    • isPrime

      public static boolean isPrime​(int n)
      Primality test: tells if the argument is a (provable) prime or not.

      It uses the Miller-Rabin probabilistic test in such a way that a result is guaranteed: it uses the firsts prime numbers as successive base (see Handbook of applied cryptography by Menezes, table 4.1).

      Parameters:
      n - number to test.
      Returns:
      true if n is prime. (All numbers < 2 return false).

    • nextPrime

      public static int nextPrime​(int n)
      Return the smallest prime greater than or equal to n.
      Parameters:
      n - a positive number.
      Returns:
      the smallest prime greater than or equal to n.
      Throws:
      IllegalArgumentException - if n < 0.

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

    • smallTrialDivision

      public static int smallTrialDivision​(int n, gnu.trove.list.array.TIntArrayList 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, gnu.trove.list.array.TIntArrayList 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.

    • primeFactors

      public static int[] primeFactors​(int n)
      Prime factors decomposition. Uses trial divisions (that is quite fast for ints).
      Parameters:
      n - number to factorize: must be ≥ 2
      Returns:
      list of prime factors of n
      Throws:
      IllegalArgumentException - if n < 2.
      See Also:
      BigPrimes.primeFactors(cc.redberry.rings.bigint.BigInteger)