Package edu.jas.arith

Class PrimeInteger

java.lang.Object
edu.jas.arith.PrimeInteger

public final class PrimeInteger extends Object
Integer prime factorization. Code from ALDES/SAC2 and MAS module SACPRIM. See ALDES/SAC2 or MAS code in SACPRIM. See Symja org/matheclipse/core/expression/Primality.java for Pollard algorithm.
  • Field Details

    • logger

      private static final org.apache.logging.log4j.Logger logger
    • BETA

      public static final long BETA
      Maximal long, which can be factored by IFACT(long). Has nothing to do with SAC2.BETA.
    • IMPDS_MIN

      static final long IMPDS_MIN
      Medium prime divisor range.
      See Also:
    • IMPDS_MAX

      static final long IMPDS_MAX
      See Also:
    • SMPRM

      public static final List<Long> SMPRM
      List of small prime numbers.
    • UZ210

      public static final List<Long> UZ210
      List of units of Z mod 210.
    • random

      static final Random random
      Random number generator.
  • Constructor Details

    • PrimeInteger

      public PrimeInteger()
  • Method Details

    • smallPrimes

      public static List<Long> smallPrimes(long m, int K)
      Digit prime generator. K and m are positive beta-integers. L is the list (p(1),...,p(r)) of all prime numbers p such that m le p lt m+2*K, with p(1) lt p(2) lt ... lt p(r). See also SACPRIM.DPGEN.
      Parameters:
      m - start integer
      K - number of integers
      Returns:
      the list L of prime numbers p with m ≤ p < m + 2*K.
    • smallPrimeDivisors

      public static long smallPrimeDivisors(long n, SortedMap<Long,Integer> F)
      Integer small prime divisors. n is a positive integer. F is a list of primes (q(1),q(2),...,q(h)), h non-negative, q(1) le q(2) le ... lt q(h), such that n is equal to m times the product of the q(i) and m is not divisible by any prime in SMPRM. Either m=1 or m gt 1,000,000.
      In JAS F is a map and m=1 or m > 4.000.000. See also SACPRIM.ISPD.
      Parameters:
      n - integer to factor.
      F - a map of pairs of prime numbers and multiplicities (p,e) with p**e divides n and e maximal, F is modified.
      Returns:
      n/F a factor of n not divisible by any prime number in SMPRM.
    • smallPrimeDivisors

      public static BigInteger smallPrimeDivisors(BigInteger n, SortedMap<BigInteger,Integer> F)
      Integer small prime divisors. n is a positive integer. F is a list of primes (q(1),q(2),...,q(h)), h non-negative, q(1) le q(2) le ... lt q(h), such that n is equal to m times the product of the q(i) and m is not divisible by any prime in SMPRM. Either m=1 or m gt 1,000,000.
      In JAS F is a map and m=1 or m > 4.000.000. See also SACPRIM.ISPD.
      Parameters:
      n - integer to factor.
      F - a map of pairs of prime numbers and multiplicities (p,e) with p**e divides n and e maximal, F is modified.
      Returns:
      n/F a factor of n not divisible by any prime number in SMPRM.
    • isPrime

      public static boolean isPrime(long n)
      Integer primality test. n is a positive integer. r is true, if n is prime, else false.
      Parameters:
      n - integer to test.
      Returns:
      true if n is prime, else false.
    • isPrime

      public static boolean isPrime(BigInteger N)
      Integer primality test. n is a positive integer. r is true, if n is prime, else false.
      Parameters:
      N - integer to test.
      Returns:
      true if N is prime, else false.
    • isPrimeFactorization

      public static boolean isPrimeFactorization(long n, SortedMap<Long,Integer> F)
      Test prime factorization. n is a positive integer. r is true, if n = product_i(pi**ei) and each pi is prime, else false.
      Parameters:
      n - integer to test.
      F - a map of pairs of prime numbers (p,e) with p**e divides n.
      Returns:
      true if n = product_i(pi**ei) and each pi is prime, else false.
    • isFactorization

      public static boolean isFactorization(long n, SortedMap<Long,Integer> F)
      Test factorization. n is a positive integer. r is true, if n = product_i(pi**ei), else false.
      Parameters:
      n - integer to test.
      F - a map of pairs of numbers (p,e) with p**e divides n.
      Returns:
      true if n = product_i(pi**ei), else false.
    • factors

      public static SortedMap<Long,Integer> factors(long n)
      Integer factorization. n is a positive integer. F is a list (q(1), q(2),...,q(h)) of the prime factors of n, q(1) le q(2) le ... le q(h), with n equal to the product of the q(i).
      In JAS F is a map. See also SACPRIM.IFACT.
      Parameters:
      n - integer to factor.
      Returns:
      a map of pairs of numbers (p,e) with p**e divides n.
    • factorsPollard

      public static SortedMap<Long,Integer> factorsPollard(long n)
      Integer factorization, Pollard rho algorithm. n is a positive integer. F is a list (q(1), q(2),...,q(h)) of the prime factors of n, q(1) le q(2) le ... le q(h), with n equal to the product of the q(i).
      In JAS F is a map. See also SACPRIM.IFACT.
      Parameters:
      n - integer to factor.
      Returns:
      a map F of pairs of numbers (p,e) with p**e divides n and p probable prime.
    • mediumPrimeDivisorSearch

      public static long mediumPrimeDivisorSearch(long n, long a, long b)
      Integer medium prime divisor search. n, a and b are positive integers such that a le b le n and n has no positive divisors less than a. If n has a prime divisor in the closed interval from a to b then p is the least such prime and q=n/p. Otherwise p=1 and q=n. See also SACPRIM.IMPDS.
      Parameters:
      n - integer to factor.
      a - lower bound.
      b - upper bound.
      Returns:
      p a prime factor of n, with a ≤ p ≤ b < n.
    • primalityTestSelfridge

      public static int primalityTestSelfridge(long m, long mp, SortedMap<Long,Integer> F)
      Integer selfridge primality test. m is an integer greater than or equal to 3. mp=m-1. F is a list (q(1),q(2),...,q(k)), q(1) le q(2) le ... le q(k), of the prime factors of mp, with mp equal to the product of the q(i). An attempt is made to find a root of unity modulo m of order m-1. If the existence of such a root is discovered then m is prime and s=1. If it is discovered that no such root exists then m is not a prime and s=-1. Otherwise the primality of m remains uncertain and s=0. See also SACPRIM.ISPT.
      Parameters:
      m - integer to test.
      mp - integer m-1.
      F - a map of pairs (p,e), with primes p, multiplicity e and with p**e divides mp and e maximal.
      Returns:
      s = -1 (not prime), 0 (unknown) or 1 (prime).
    • largePrimeDivisorSearch

      public static long largePrimeDivisorSearch(long n, long a, long b)
      Integer large prime divisor search. n is a positive integer with no prime divisors less than 17. 1 le a le b le n. A search is made for a divisor p of the integer n, with a le p le b. If such a p is found then np=n/p, otherwise p=1 and np=n. A modular version of Fermats method is used, and the search goes from a to b. See also SACPRIM.ILPDS.
      Parameters:
      n - integer to factor.
      a - lower bound.
      b - upper bound.
      Returns:
      p a prime factor of n, with a ≤ p ≤ b < n.
    • residueListFermatSingle

      public static List<ModLong> residueListFermatSingle(long m, long a)
      Fermat residue list, single modulus. m is a positive beta-integer. a belongs to Z(m). L is a list of the distinct b in Z(m) such that b**2-a is a square in Z(m). See also SACPRIM.FRLSM.
      Parameters:
      m - integer to factor.
      a - element of Z mod m.
      Returns:
      Lp a list of Fermat residues for modul m.
    • residueListFermat

      public static List<ModLong> residueListFermat(long n)
      Fermat residue list. n is a positive integer with no prime divisors less than 17. m is a positive beta-integer and L is an ordered list of the elements of Z(m) such that if x**2-n is a square then x is congruent to a (modulo m) for some a in L. See also SACPRIM.FRESL.
      Parameters:
      n - integer to factor.
      Returns:
      Lp a list of Fermat residues for different modules.
    • getUZ210

      public static List<Long> getUZ210()
      Compute units of Z sub 210. See also SACPRIM.UZ210.
      Returns:
      list of units of Z sub 210.
    • factors

      public static SortedMap<BigInteger,Integer> factors(BigInteger n)
      Integer factorization. n is a positive integer. F is a list (q(1), q(2),...,q(h)) of the prime factors of n, q(1) le q(2) le ... le q(h), with n equal to the product of the q(i).
      In JAS F is a map. See also SACPRIM.IFACT, uses Pollards rho method.
      Parameters:
      n - integer to factor.
      Returns:
      a map of pairs of numbers (p,e) with p**e divides n.
    • factorsPollardRho

      public static void factorsPollardRho(BigInteger n, SortedMap<BigInteger,Integer> F)
      Integer factorization using Pollards rho algorithm. n is a positive integer. F is a list (q(1), q(2),...,q(h)) of the prime factors of n, q(1) le q(2) le ... le q(h), with n equal to the product of the q(i).
      In JAS F is a map.
      Parameters:
      n - integer to factor.
      F - a map of pairs of numbers (p,e) with p**e divides n and p is probable prime, F is modified.
    • rho

      static BigInteger rho(BigInteger n)
      Search cycle with Pollards rho algorithm x**2 + c mod n. n is a positive integer.
      Parameters:
      n - integer test.
      Returns:
      x-y with gcd(x-y, n) = 1.
    • factorsPollardRho

      public static void factorsPollardRho(long n, SortedMap<Long,Integer> F)
      Integer factorization using Pollards rho algorithm. n is a positive integer. F is a list (q(1), q(2),...,q(h)) of the prime factors of n, q(1) le q(2) le ... le q(h), with n equal to the product of the q(i).
      In JAS F is a map.
      Parameters:
      n - integer to factor.
      F - a map of pairs of numbers (p,e) with p**e divides n and p is probable prime, F is modified.
    • rho

      static long rho(long n)
      Search cycle with Pollards rho algorithm x**2 + c mod n. n is a positive integer. c is a random constant.
      Parameters:
      n - integer test.
      Returns:
      x-y with gcd(x-y, n) == 1.
    • gcd

      static long gcd(long a, long b)