View Single Post
Old 2004-04-26, 16:57   #7
R.D. Silverman
R.D. Silverman's Avatar
Nov 2003

22·5·373 Posts
Thumbs up

Originally Posted by dsouza123
Yes, that was what I originally was thinking but for larger numbers I didn't
see a way of generating them so I came up with just using the ends
of the numbers because the results of multiplying the pairs have verifiable
correct matching digits.

I was hoping there was a way to get the first five digits correct of the eventual large prime factors. Though in the case of the 576 digit number
having 10 digits of both of the two factors wouldn't solve it but may help
narrow the search space.

Doing more research shows there are many possible pairs, by presenting it
I hoped someone might figure a way to accomplish determining a few digits
with certainty or at least get people thinking about factoring in a different way.
(1) Even if you can limit the search space this way it is useless as a
practical method... It will still be an exponential time algorithm.
In fact, if you "extend" the proposed method (matching first 5 & last 5 digits)
it leads to an attempt to factor by "reverse engineering" the process of
multiplication. It is well known that such techniques do not and can not
work. The technique leads to a simultaneous set of diophantine equations
whose solution is known to be an NP-Complete problem. Now unless P=NP,
attempting to factor by this method will always result in an exponential time

(2) The best current methods do not "search the solution space". Solution
space search methods are exponential time.

(3) What makes you believe that people have not already "thought about
factoring in a different way"???

(4) The proposed method looks at [sqrt(N)] and attempts to force the
other factor to have a value such that their product matches N to the
first 5 digits. However, there is no reason to believe that either factor
must be within the range [sqrt(N)] +/- (1 + 1/10^5)[sqrt(N)]. The best
you can do (assuming an RSA key where both factors have equal size) is
that the factors must be within a factor of 2 of [sqrt(N)]. Note that we
already ALWAYS know the first two bits of the factors if they are the same
size regardless of (the value of) N. Hint: look at the product of two n-bit
numbers where the second bit is 0. (e.g. 101 * 101 = 11001 --> 5 bit result)
In theory we can have one of the two numbers with the second bit 0
provided that the last partial sum generates a carry, but in practice the way
standards deal with this is to set the first two bits of each prime to 1.

And the method says nothing about general integers....

My advice is not to waste any more time on this. The subject has been
investigated thoroughly.
R.D. Silverman is offline   Reply With Quote