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 Symja org/matheclipse/core/expression/Primality.java for Pollard algorithm.

Author:

Heinz Kredel

Field Summary

Fields

Modifier and Type	Field and 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 and Description
PrimeInteger()

Method Summary

Modifier and Type	Method and Description
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>	factors(long 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(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 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 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	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 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 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.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.

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 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.

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.