Package edu.jas.arith
Class PrimeInteger
java.lang.Object
edu.jas.arith.PrimeInteger
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 Summary
FieldsModifier and TypeFieldDescriptionstatic final long
Maximal long, which can be factored by IFACT(long).(package private) static final long
(package private) static final long
Medium prime divisor range.private static final org.apache.logging.log4j.Logger
(package private) static final Random
Random number generator.List of small prime numbers.List of units of Z mod 210. -
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionfactors
(long n) Integer factorization.static SortedMap
<BigInteger, Integer> Integer factorization.factorsPollard
(long n) Integer factorization, Pollard rho algorithm.static void
factorsPollardRho
(long n, SortedMap<Long, Integer> F) Integer factorization using Pollards rho algorithm.static void
Integer factorization using Pollards rho algorithm.(package private) static long
gcd
(long a, long b) getUZ210()
Compute units of Z sub 210.static boolean
isFactorization
(long n, SortedMap<Long, Integer> F) Test factorization.static boolean
isPrime
(long n) Integer primality test.static boolean
Integer primality test.static boolean
isPrimeFactorization
(long n, SortedMap<Long, Integer> F) Test prime factorization.static long
largePrimeDivisorSearch
(long n, long a, long b) Integer large prime divisor search.static long
mediumPrimeDivisorSearch
(long n, long a, long b) Integer medium prime divisor search.static int
primalityTestSelfridge
(long m, long mp, SortedMap<Long, Integer> F) Integer selfridge primality test.residueListFermat
(long n) Fermat residue list.residueListFermatSingle
(long m, long a) Fermat residue list, single modulus.(package private) static long
rho
(long n) Search cycle with Pollards rho algorithm x**2 + c mod n.(package private) static BigInteger
rho
(BigInteger n) Search cycle with Pollards rho algorithm x**2 + c mod n.static long
smallPrimeDivisors
(long n, SortedMap<Long, Integer> F) Integer small prime divisors.static BigInteger
Integer small prime divisors.smallPrimes
(long m, int K) Digit prime generator.
-
Field Details
-
logger
private static final org.apache.logging.log4j.Logger logger -
BETA
public static final long BETAMaximal long, which can be factored by IFACT(long). Has nothing to do with SAC2.BETA. -
IMPDS_MIN
static final long IMPDS_MINMedium prime divisor range.- See Also:
-
IMPDS_MAX
static final long IMPDS_MAX- See Also:
-
SMPRM
List of small prime numbers. -
UZ210
List of units of Z mod 210. -
random
Random number generator.
-
-
Constructor Details
-
PrimeInteger
public PrimeInteger()
-
-
Method Details
-
smallPrimes
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 integerK
- number of integers- Returns:
- the list L of prime numbers p with m ≤ p < m + 2*K.
-
smallPrimeDivisors
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
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
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
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
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
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
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
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
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
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
Compute units of Z sub 210. See also SACPRIM.UZ210.- Returns:
- list of units of Z sub 210.
-
factors
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
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
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
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)
-