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.- Author:
- Heinz Kredel
-
-
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.
-
-
-
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.
-
-
Constructor Detail
-
PrimeInteger
public PrimeInteger()
-
-
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.
-
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.
-
-