5dpf, 5 digits from the end partial factors

dsouza123 · 2004-04-23, 01:33

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

cheesehead · 2004-04-24, 04:41

Will you please explain more of what you're getting at?

Perhaps some more-fully-worked-out numerical examples involving smaller numbers?

Maybeso · 2004-04-25, 07:09

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.

dsouza123 · 2004-04-25, 16:27

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.

Maybeso · 2004-04-25, 23:56

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!

Maybeso · 2004-04-26, 03:05

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.

R.D. Silverman · 2004-04-26, 16:57

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.

2004-04-23, 01:33	#1
dsouza123 Sep 2002 1226₈ 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-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, 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

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
a partial sudoku puzzle	MattcAnderson	Miscellaneous Math	4	2017-06-29 07:14
Reporting partial ECM results?	apsen	PrimeNet	3	2011-07-03 14:54
Moving partial work done with prime95 to other pc	Damian	Information & Answers	3	2008-02-21 01:40
partial relations in SIQS	ThiloHarich	Factoring	6	2007-12-03 18:48
Partial fraction of this expression?please!!	tinhnho	Miscellaneous Math	4	2005-01-17 19:45

2004-04-24, 04:41	#2
cheesehead "Richard B. Woods" Aug 2002 Wisconsin USA 7692₁₀ 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, 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-26, 03:05	#6
Maybeso Aug 2002 Portland, OR USA 2·137 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 k10^5 + 45903 and k10^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.