Package de.tilman_neumann.jml.factor.tdiv

Class TDiv31Inverse

java.lang.Object

de.tilman_neumann.jml.factor.FactorAlgorithm

de.tilman_neumann.jml.factor.tdiv.TDiv31Inverse

public class TDiv31Inverse
extends FactorAlgorithm

Trial division factor algorithm using double-valued Barrett reduction, thus replacing division by multiplications. Instead of dividing N by consecutive primes, we store the reciprocals of those primes, too, and multiply N by those reciprocals. Only if such a result is near to an integer we need to do a division. This variant abstains from testing N%primes[i] when the discriminator test indicates a neat division, and unrolls the loop in findSingleFactor().

Field Summary

Fields inherited from class de.tilman_neumann.jml.factor.FactorAlgorithm

DEFAULT, NUM_PRIMES_FOR_31_BIT_TDIV, tdivLimit

Constructor Summary

Constructors

Constructor	Description
TDiv31Inverse()

Method Summary

Modifier and Type	Method	Description
void	factor(BigInteger Nbig, int Nexp, SortedMultiset<BigInteger> primeFactors)	Find all factor of NBig, which must have less than 32 bit.
void	factor(BigInteger Nbig, SortedMultiset<BigInteger> primeFactors)	Decomposes the argument N into prime factors.
int	findSingleFactor(int N)
BigInteger	findSingleFactor(BigInteger N)	Find a single factor of the given N, which is composite and odd.
String	getName()

Methods inherited from class de.tilman_neumann.jml.factor.FactorAlgorithm

factor, searchFactors

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

TDiv31Inverse

public TDiv31Inverse()

Method Detail

getName

public String getName()

Specified by:

getName in class FactorAlgorithm

Returns:

The name of the algorithm, possibly including important parameters.

factor

public void factor(BigInteger Nbig,
                   SortedMultiset<BigInteger> primeFactors)

Description copied from class: FactorAlgorithm

Decomposes the argument N into prime factors.

Overrides:

factor in class FactorAlgorithm

Parameters:

Nbig - Number to factor.

primeFactors - a map to which found factors are added

factor

public void factor(BigInteger Nbig,
                   int Nexp,
                   SortedMultiset<BigInteger> primeFactors)

Find all factor of NBig, which must have less than 32 bit.

Parameters:

Nbig -

Nexp - the exponent which with found factors are added to primeFactors

primeFactors -

findSingleFactor

public BigInteger findSingleFactor(BigInteger N)

Description copied from class: FactorAlgorithm

Find a single factor of the given N, which is composite and odd.

Specified by:

findSingleFactor in class FactorAlgorithm

Returns:

factor

findSingleFactor

public int findSingleFactor(int N)