Factoring using Lehman's method

From: Christian Bau (christian.bau_at_cbau.freeserve.co.uk)
Date: 01/30/05 

Date: Sun, 30 Jan 2005 23:43:36 +0000

I am trying to implement Lehman's factoring method, which is probably
the simplest method that is faster than trial division. I found a small
amount of info on the internet, so what I have now to factor N is this:

   1. Make sure N has no prime factors <= N^(1/3)
   2. Find x, k such that x^2 - 4kN is a square; this leads quickly to a
prime factor of N.
   3. If enough values x, k have been tried without finding a factor
then N is prime.

The clever part of the algorithm is that the only values of k and x that
are considered are 1 <= k <= N^(1/3), and

   x = ceil (sqrt (4kN)) + m

for integers m >= 0 where m^2 * k <= N^(1/3); so this requires that
about 2.6 * N^(1/3) values are tried, and there is a proof by Lehman
that if this doesn't find a prime factor of N, then there are none.

I tried for a huge range of products of moderately sized primes that
this will (1) actually find a solution, and that (2) the whole range
actually has to be searched, otherwise factors will be missed. Then I
tried what happens if I start by excluding prime factors up to say 2 *
N^(1/3) first, and it seems that I can always find factors by searching
through a much smaller range, which would speed up the method by
slightly more than a factor 2 (if I can prove that it works).

Experimentally, it seems that if I find all prime factors <= (c*N)^(1/3)
for 1 <= c <= 4, then I only need to consider values k, m^2*k <= (N /
c^2)^(1/3). This will be fun to prove.

Question: Are there any known results about this? (Lehman's method was
published in 1974, and I could find only one article describing the
method at all).

Relevant Pages

  • Re: Hawking HWU8DD Dish any good for extending WIFI range ?
    ... a murky question and from searching the web you get conflicting views, ... some saying it's illegal, ... Guess if you ignore any legal aspects (which probably vary state by ... they use a moderate bandwidth under some amount that the system would ...
    (rec.outdoors.rv-travel)
  • Re: Using with
    ... It reduces readability and makes searching in your code more difficult and ... it's actually slower by a small amount. ...
    (microsoft.public.vb.general.discussion)
  • Re: Im A Celebrity - confirmed line up
    ... geriatric actor would need the career boost (or the relatively small ... amount of money) and was searching for someone else of the same name. ...
    (uk.media.tv.misc)
  • Re: Parameter Query-enter just once for use in multiple places
    ... > I have an Excel spreadsheet where I have multiple places I am searching ... > an amount within a range of dates. ...
    (microsoft.public.excel.misc)