Package de.tilman_neumann.jml.factor.lehman

Class Lehman_Fast

  • public class Lehman_Fast
extends FactorAlgorithm
    Fast implementation of Lehman's factor algorithm. Works flawlessly for N up to 60 bit.

    It is quite surprising that the exact sqrt test of test = a^2 - 4kN works for N >= 45 bit. At that size, both a^2 and 4kN start to overflow Long.MAX_VALUE. But the error - comparing correct results vs. long results - is just the same for both a^2 and 4kN (and a multiple of 2^64). Thus test is correct and b is correct, too. a is correct anyway. Lehman_CustomKOrder is considerably faster for any kind of test numbers. This class is kept for reference as it was implemented by bSquare, see https://www.mersenneforum.org/showpost.php?p=506294&postcount=7

    • Constructor Detail

      • Lehman_Fast

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

      • main

        public static void main​(String[] args)
        Test.
        Parameters:
        args - ignored