mersenneforum.org 5dpf, 5 digits from the end partial factors
 Register FAQ Search Today's Posts Mark Forums Read

 2004-04-23, 01:33 #1 dsouza123     Sep 2002 2×331 Posts 5dpf, 5 digits from the end partial factors Rather than fully factoring a RSA number, factor the first and last 5 digits of the two factors. For example RSA-576 (174 digits) 18819881292060796383869723946165043980716356 33794173827007633564229888597152346654853190 60606504743045317388011303396716199692321205 734031879550656996221305168759307650257059 The two factors (both 87 digits) are 39807508642406493739712550055038649119906436 2342526708406385189575946388957261768583317 47277214610743530253622307197304822463291469 5302097116459852171130520711256363590397527 so the 5dpf, 5 digits from the end partial factors, are 39807r and r83317 47277s and s97527 r and s are used to both match the parts and indicate the ends. Here is RSA-640 (193 digits) 310741824049004372135075003588856793003 734602284272754572016194882320644051808 150455634682967172328678243791627283803 341547107310850191954852900733772482278 3525742386454014691736602477652346609 Each of the two full factors will be very close to half the digits of the RSA-640 number. What are the values for any/all of the four 5dpf ? Also the reasoning behind the choice(s).
 2004-04-24, 04:41 #2 cheesehead     "Richard B. Woods" Aug 2002 Wisconsin USA 22×3×641 Posts Will you please explain more of what you're getting at? Perhaps some more-fully-worked-out numerical examples involving smaller numbers?
 2004-04-25, 07:09 #3 Maybeso     Aug 2002 Portland, OR USA 2·137 Posts Blind stab in the dark. This is a BSITD (swag), but Do you mean, pick a large group of primes/prp's near the root of the RSA number, and pair them up so the product of the first 5 digits matches the RSA, and the same for the last 5? If RSA = 18124... ...32589 and first candidate factor = 34209... ...74208 then look for a second candidate factor = 52983... ...44023. If you don't find a match, the first can't be a factor. hmm, if there was a way to determine a narrow boundry to keep the search fast, it might be worth the time.
 2004-04-25, 16:27 #4 dsouza123     Sep 2002 2×331 Posts 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.
 2004-04-25, 23:56 #5 Maybeso     Aug 2002 Portland, OR USA 2·137 Posts dsouza123, After some experimenting, I don't think the first 5 digits will help reduce the search. Using the first 10 digits of RSA-640, we make a real number, like this: 310741.8240 then look for pairs of smaller reals, like this: Code: 310.75 999.97 500.00 621.48 550.00 564.98 310.76 999.94 500.01 621.47 550.01 564.97 310.77 999.90 500.02 621.45 550.02 564.96 310.78 999.87 500.03 621.44 550.03 564.95 310.79 999.84 500.04 621.43 550.04 564.94 Because each of the smaller numbers has 90 digits trailing it, we can't treat them like 5 digit integers. So given 'a', c = a/b has a solution for any b. We can only use the first 5 digits to finish constructing a factor pair after we find them using the last 5 digits. But you have success, because we are thinking about it! Last fiddled with by Maybeso on 2004-04-25 at 23:57
 2004-04-26, 03:05 #6 Maybeso     Aug 2002 Portland, OR USA 1000100102 Posts Using brute force on the end 5dpf's: ~ 50000 odds less than 100000 ~ 40000 with 5's removed, there should be ~ 20000 pairs, but we lose those matched with the missing 5's, so actual pairs = 11145. So the plan could be to sieve a block of k*10^5 + 45903 and k*10^5 + 46303. Removing a number from the low end of one group should also remove one from the high end of the other. If handled properly, that will reduce the work by a factor of 7.
2004-04-26, 16:57   #7
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 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
method.

(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.

 Similar Threads Thread Thread Starter Forum Replies Last Post MattcAnderson Miscellaneous Math 4 2017-06-29 07:14 apsen PrimeNet 3 2011-07-03 14:54 Damian Information & Answers 3 2008-02-21 01:40 ThiloHarich Factoring 6 2007-12-03 18:48 tinhnho Miscellaneous Math 4 2005-01-17 19:45

All times are UTC. The time now is 07:35.

Fri Apr 23 07:35:33 UTC 2021 up 15 days, 2:16, 0 users, load averages: 2.21, 2.41, 2.29