Thread: Fast Lehman implementation View Single Post
 2019-02-15, 20:46 #30 ThiloHarich     Nov 2005 101 Posts brief java implementation Here is a brief java implementation of our last version. It works fine for odd numbers up to 40 bits. For simplicity we have no primes table so it does not works super fast for numbers with factors below n^1/3. The gcd implementation is also missing. For numbers with factors above n^1/3 it has the same performance as the latest version of our lehman implementation. The main loop basically checks for small numbers with a modified trial division and for big numbers with the lehman approach. In the Lehman part we focus just on numbers of the form k = 3*3*5*7 * i. Even and odd k cause some limitations on the number 'a' of a^2 - N = y^2. By choosing k as a multiple of some primes a satisfies a^2 - N = y^2 modulus this primes. Enough talking here is the code: Code: public class HartSimpleMin { private static final double DISCRIMINATOR = 1.0/(1<<10); // experimental result /** * We only test k-values that are multiples of this constant. * Best values for performance are 315, 45, 105, 15 and 3, in that order. * The multiplier ensures that the generated test values are always a square mod K_MULT * Since the K_MULT consists out of 4 primes these numbers have a 2^4 = 16 times * higher chance of being a square then random numbers. This is very helpful */ private static final int K_MULT = 3 * 3 * 5* 7; /** This constant is used for fast rounding of double values to long. */ private static final double ROUND_UP_DOUBLE = 0.9999999665; private static double[] sqrt; // static double[] primes; with a table of primes the algorithm is much faster for small factors; here we just use odd numbers 3,5,7,9,.. static double[] primesInv; // works for numbers up to 40 Bits private static int maxFactor = 1 << 19; static { // Precompute sqrts for all k required for N <= MAX_N and multiplier K_MULT sqrt = new double[maxFactor+1]; primesInv = new double[maxFactor+1]; for (int i = 1; i <= maxFactor; i++) { sqrt[i] = Math.sqrt(i*K_MULT); primesInv[i] = 1.0 / i; } } public HartSimpleMin() { } /** * Find a factor of long N. * @param N * @return factor of N */ public long findSingleFactor(long N) { long a,b,test, gcd; final long fourN = N<<2; final double sqrt4N = Math.sqrt(fourN); for (int sqrtIndex = 1, k = sqrtIndex * K_MULT, prime = 3; ;k += K_MULT, prime += 2, sqrtIndex++) { // do trial division if ((long) (N * primesInv[prime] + DISCRIMINATOR) * prime == N) return prime; a = (long) (sqrt4N * sqrt[sqrtIndex] + ROUND_UP_DOUBLE); // adjust a mod 8 if ((sqrtIndex & 1) == 0) { a |= 1; } else { final long kPlusN = k + N; a += (kPlusN & 3) == 0 ? ((kPlusN - a) & 7) : ((kPlusN - a) & 3); } test = a*a - k * fourN; b = (long) Math.sqrt(test); if (b*b == test && (gcd = gcd(a+b, N))>1 && gcd < N) { return gcd; } } } } Last fiddled with by ThiloHarich on 2019-02-15 at 21:11