Package de.tilman_neumann.jml.factor.lehman

Class Lehman_Simple

java.lang.Object

de.tilman_neumann.jml.factor.FactorAlgorithm

de.tilman_neumann.jml.factor.lehman.Lehman_Simple

public class Lehman_Simple
extends FactorAlgorithm

Simple implementation of Lehmans factor algorithm, following https://programmingpraxis.com/2017/08/22/lehmans-factoring-algorithm/, using fast inverse trial division. This implementation is pretty slow, but useful for illustrating the basic algorithm. It may fail for N>=47 bit where 4*k*N produces a long-overflow.

Author:

Tilman Neumann

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
Lehman_Simple(boolean doTDivFirst)	Full constructor.

Method Summary

Modifier and Type	Method	Description
long	findSingleFactor(long 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, factor, searchFactors

Methods inherited from class java.lang.Object

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

Constructor Detail

Lehman_Simple

public Lehman_Simple(boolean doTDivFirst)

Full constructor.

Parameters:

doTDivFirst - If true then trial division is done before the Lehman loop. This is recommended if arguments N are known to have factors < cbrt(N) frequently.

Method Detail

getName

public String getName()

Specified by:

getName in class FactorAlgorithm

Returns:

The name of the algorithm, possibly including important parameters.

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 long findSingleFactor(long N)