Package edu.jas.arith
Class PrimeInteger
- java.lang.Object
-
- edu.jas.arith.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 Symjaorg/matheclipse/core/expression/Primality.java
for Pollard algorithm.
-
-
Field Summary
Fields Modifier and Type Field Description static long
BETA
Maximal long, which can be factored by IFACT(long).(package private) static long
IMPDS_MAX
(package private) static long
IMPDS_MIN
Medium prime divisor range.private static org.apache.logging.log4j.Logger
logger
(package private) static java.util.Random
random
Random number generator.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.static java.util.SortedMap<java.math.BigInteger,java.lang.Integer>
factors(java.math.BigInteger n)
Integer factorization.static java.util.SortedMap<java.lang.Long,java.lang.Integer>
factorsPollard(long n)
Integer factorization, Pollard rho algorithm.static void
factorsPollardRho(long n, java.util.SortedMap<java.lang.Long,java.lang.Integer> F)
Integer factorization using Pollards rho algorithm.static void
factorsPollardRho(java.math.BigInteger n, java.util.SortedMap<java.math.BigInteger,java.lang.Integer> F)
Integer factorization using Pollards rho algorithm.(package private) static long
gcd(long a, long b)
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.static boolean
isPrime(long n)
Integer primality test.static boolean
isPrime(java.math.BigInteger N)
Integer primality test.static boolean
isPrimeFactorization(long n, java.util.SortedMap<java.lang.Long,java.lang.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, java.util.SortedMap<java.lang.Long,java.lang.Integer> F)
Integer selfridge primality test.static java.util.List<ModLong>
residueListFermat(long n)
Fermat residue list.static java.util.List<ModLong>
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 java.math.BigInteger
rho(java.math.BigInteger n)
Search cycle with Pollards rho algorithm x**2 + c mod n.static long
smallPrimeDivisors(long n, java.util.SortedMap<java.lang.Long,java.lang.Integer> F)
Integer small prime divisors.static java.math.BigInteger
smallPrimeDivisors(java.math.BigInteger n, java.util.SortedMap<java.math.BigInteger,java.lang.Integer> F)
Integer small prime divisors.static java.util.List<java.lang.Long>
smallPrimes(long m, int K)
Digit prime generator.
-
-
-
Field Detail
-
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:
- Constant Field Values
-
IMPDS_MAX
static final long IMPDS_MAX
- See Also:
- Constant Field Values
-
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.
-
random
static final java.util.Random random
Random number generator.
-
-
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 integerK
- 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<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 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. 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.
-
rho
static java.math.BigInteger rho(java.math.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, 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.
-
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)
-
-