20040423, 01:33  #1 
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 RSA576 (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 RSA640 (193 digits) 310741824049004372135075003588856793003 734602284272754572016194882320644051808 150455634682967172328678243791627283803 341547107310850191954852900733772482278 3525742386454014691736602477652346609 Each of the two full factors will be very close to half the digits of the RSA640 number. What are the values for any/all of the four 5dpf ? Also the reasoning behind the choice(s). 
20040424, 04:41  #2 
"Richard B. Woods"
Aug 2002
Wisconsin USA
2^{2}×3×641 Posts 
Will you please explain more of what you're getting at?
Perhaps some morefullyworkedout numerical examples involving smaller numbers? 
20040425, 07:09  #3 
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. 
20040425, 16:27  #4 
Sep 2002
296_{16} 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. 
20040425, 23:56  #5 
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 RSA640, 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 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 20040425 at 23:57 
20040426, 03:05  #6 
Aug 2002
Portland, OR USA
100010010_{2} 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. 
20040426, 16:57  #7  
Nov 2003
16444_{8} Posts 
Quote:
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 NPComplete 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 nbit 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. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
a partial sudoku puzzle  MattcAnderson  Miscellaneous Math  4  20170629 07:14 
Reporting partial ECM results?  apsen  PrimeNet  3  20110703 14:54 
Moving partial work done with prime95 to other pc  Damian  Information & Answers  3  20080221 01:40 
partial relations in SIQS  ThiloHarich  Factoring  6  20071203 18:48 
Partial fraction of this expression?please!!  tinhnho  Miscellaneous Math  4  20050117 19:45 