Conference rusure::math

195.0. "funny factor. idea - comments?" by TAV02::NITSAN () Thu Dec 27 1984 01:20

 This is just something I thought about, maybe somebody will comment about or
improve the idea, and if not - nothing happened...

 Suppose we need to factor N to P*Q. We can assume N odd (otherwise divide by 2
until odd). Thus if N = P*Q then P and Q are odd: P = 2*K+1 , Q = 2*L+1 , so:
N =  P*Q  =  (2*K+1) * (2*L+1)  =  4*K*L + 2*(K+L) + 1

 In binary representation:

                 mmmmmmmmmmmmmmmmmmmm00          mm...mm = K*L , log N bits
              +             ssssssssss0          ss...ss = K+L , 1/2 log N bits
                                      1
                 ----------------------
                 nnnnnnnnnnnnnnnnnnnnnn          nn...nn = N , known to us

 Now, we can easily find last (least significant) bit of K+L (most right "s").
The point is that know we have some info about last "m" as well (e.g. if K+L is
odd then K*L is even), so we have a distribution which is not 0.5/0.5 to the
last "m", and sometimes it is even determined. Knowing (or guessing...) the
last "m", we get easily the second "s", and then by knowing two "s"'s and one
"m" we again get much info about the second "m", and sometimes it is even
determined (try all 8 combinations...).

 To summarize, we have about 1/2 log N phases in which we don't guess 0.5/0.5,
but better, so we get less than SQRT(N) average # steps. It sure doesn't look
like N ** 1/4 (Pollard etc.), but it's just an idea to improve, or am I talking
some Xmas nonsense?...

>Suppose we need to factor N to P*Q. We can assume N odd (otherwise divide by 2
>until odd). Thus if N = P*Q then P and Q are odd: P = 2*K+1 , Q = 2*L+1 , so:
>N =  P*Q  =  (2*K+1) * (2*L+1)  =  4*K*L + 2*(K+L) + 1

Have you seen "Factoring with HYPER" in Byte, March 1985? His PHI is your
4*K*L. He arrives at it being a multiple of 4, and searches downwards 
(order of SQRT(N)). I wonder if a method can't be found that combines the
two approaches? 

A word of caution: really dumb methods like trial division are O(SQRT(N)) too,
what we really need is a method that is O(LOG(N)), i.e. proportional to
the number of *digits* in N and not some power of N.

- Giles