mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Factoring (https://www.mersenneforum.org/forumdisplay.php?f=19)
-   -   5dpf, 5 digits from the end partial factors (https://www.mersenneforum.org/showthread.php?t=2386)

dsouza123 2004-04-23 01:33

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

cheesehead 2004-04-24 04:41

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

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

Maybeso 2004-04-25 07:09

Blind stab in the dark.
 
This is a BSITD (swag), :unsure: 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. :no:

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[/CODE]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! :banana:

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=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.[/QUOTE]

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


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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.