Re: Special factorization method sought

From: Risto Lankinen (rlankine_at_hotmail.com)
Date: 07/01/05 

Date: Fri, 01 Jul 2005 07:44:15 GMT

"Risto Lankinen" <rlankine@hotmail.com> wrote in message
news:%HMwe.3202$_k2.57534@news2.nokia.com...
>
> "Pubkeybreaker" <Robert_silverman@raytheon.com> wrote in message
> news:1120055009.875911.92990@z14g2000cwz.googlegroups.com...
> >
> > Unless of course, the numbers are *so* extremely close that
> > difference of squares can be used. However, for even
> > moderately large N, if N = A*B and the size of A and B
> > differs by only 1 bit, then this method is useless. Its run time
> > will be O( (A+B)/2 - SQRT(N)). But you specified x >
> > y > x/2 and this is not close enough in general.
>
> The gap can be reduced to 'x > y > x/SQRT(2)' by doubling the
> effort: Process both 'n*2^b' and 'n*2^(b+1)' with the algorithm.
> The idea is that if the smaller factor 'y' is smaller than 'x' by a ratio
> greater than SQRT(2) but still less than 2, then 'x' will be smaller
> than '2*y' by less than SQRT(2).

It has occurred to me, that by multiplying by 'n*p*2^b' (where 'p'
is each one of a set of suitably chosen primes), the gap can be made
arbitrarily small, with the expense of having to multiply the effort by
the number of primes in the set.

For instance, with 'p=181 ~ SQRT(2)*2^7', one of 'n' and '181*n'
is going to have factors 'x > y > x/SQRT(SQRT(2))+epsilon'.

Cheers!

 - Risto -