Package edu.jas.arith

Class PrimeInteger


  • public final class PrimeInteger
    extends java.lang.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.
    Author:
    Heinz Kredel
    • Field Summary

      Fields 
      Modifier and Type Field Description
      static long BETA
      Maximal long, which can be factored by IFACT(long).
      static java.util.List<java.lang.Long> SMPRM
      List of small prime numbers.
      static java.util.List<java.lang.Long> UZ210
      List of units of Z mod 210.
    • Constructor Summary

      Constructors 
      Constructor Description
      PrimeInteger()  
    • Method Summary

      All Methods Static Methods Concrete Methods 
      Modifier and Type Method Description
      static java.util.SortedMap<java.lang.Long,​java.lang.Integer> factors​(long n)
      Integer factorization. n is a positive integer.
      static java.util.SortedMap<java.math.BigInteger,​java.lang.Integer> factors​(java.math.BigInteger n)
      Integer factorization. n is a positive integer.
      static java.util.SortedMap<java.lang.Long,​java.lang.Integer> factorsPollard​(long n)
      Integer factorization, Pollard rho algorithm. n is a positive integer.
      static void factorsPollardRho​(long n, java.util.SortedMap<java.lang.Long,​java.lang.Integer> F)
      Integer factorization using Pollards rho algorithm. n is a positive integer.
      static void factorsPollardRho​(java.math.BigInteger n, java.util.SortedMap<java.math.BigInteger,​java.lang.Integer> F)
      Integer factorization using Pollards rho algorithm. n is a positive integer.
      static java.util.List<java.lang.Long> getUZ210()
      Compute units of Z sub 210.
      static boolean isFactorization​(long n, java.util.SortedMap<java.lang.Long,​java.lang.Integer> F)
      Test factorization. n is a positive integer. r is true, if n = product_i(pi**ei), else false.
      static boolean isPrime​(long n)
      Integer primality test. n is a positive integer. r is true, if n is prime, else false.
      static boolean isPrime​(java.math.BigInteger N)
      Integer primality test. n is a positive integer. r is true, if n is prime, else false.
      static boolean isPrimeFactorization​(long n, java.util.SortedMap<java.lang.Long,​java.lang.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.
      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.
      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.
      static int primalityTestSelfridge​(long m, long mp, java.util.SortedMap<java.lang.Long,​java.lang.Integer> F)
      Integer selfridge primality test. m is an integer greater than or equal to 3. mp=m-1.
      static java.util.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.
      static java.util.List<ModLong> residueListFermatSingle​(long m, long a)
      Fermat residue list, single modulus. m is a positive beta-integer. a belongs to Z(m).
      static long smallPrimeDivisors​(long n, java.util.SortedMap<java.lang.Long,​java.lang.Integer> F)
      Integer small prime divisors. n is a positive integer.
      static java.math.BigInteger smallPrimeDivisors​(java.math.BigInteger n, java.util.SortedMap<java.math.BigInteger,​java.lang.Integer> F)
      Integer small prime divisors. n is a positive integer.
      static java.util.List<java.lang.Long> smallPrimes​(long m, int K)
      Digit prime generator.
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Field Detail

      • BETA

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

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

        public static final java.util.List<java.lang.Long> UZ210
        List of units of Z mod 210.
    • Method Detail

      • smallPrimes

        public static java.util.List<java.lang.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,
                                              java.util.SortedMap<java.lang.Long,​java.lang.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 java.math.BigInteger smallPrimeDivisors​(java.math.BigInteger n,
                                                              java.util.SortedMap<java.math.BigInteger,​java.lang.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​(java.math.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,
                                                   java.util.SortedMap<java.lang.Long,​java.lang.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,
                                              java.util.SortedMap<java.lang.Long,​java.lang.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 java.util.SortedMap<java.lang.Long,​java.lang.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 java.util.SortedMap<java.lang.Long,​java.lang.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,
                                                 java.util.SortedMap<java.lang.Long,​java.lang.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 java.util.List<ModLongresidueListFermatSingle​(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 java.util.List<ModLongresidueListFermat​(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 java.util.List<java.lang.Long> getUZ210()
        Compute units of Z sub 210. See also SACPRIM.UZ210.
        Returns:
        list of units of Z sub 210.
      • factors

        public static java.util.SortedMap<java.math.BigInteger,​java.lang.Integer> factors​(java.math.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​(java.math.BigInteger n,
                                             java.util.SortedMap<java.math.BigInteger,​java.lang.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.
      • factorsPollardRho

        public static void factorsPollardRho​(long n,
                                             java.util.SortedMap<java.lang.Long,​java.lang.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.