mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2004-04-23, 01:33   #1
dsouza123
 
dsouza123's Avatar
 
Sep 2002

2·331 Posts
Default 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).
dsouza123 is offline   Reply With Quote
Old 2004-04-24, 04:41   #2
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22·3·641 Posts
Question

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

Perhaps some more-fully-worked-out numerical examples involving smaller numbers?
cheesehead is offline   Reply With Quote
Old 2004-04-25, 07:09   #3
Maybeso
 
Maybeso's Avatar
 
Aug 2002
Portland, OR USA

4228 Posts
Default 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.
Maybeso is offline   Reply With Quote
Old 2004-04-25, 16:27   #4
dsouza123
 
dsouza123's Avatar
 
Sep 2002

2·331 Posts
Default

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.
dsouza123 is offline   Reply With Quote
Old 2004-04-25, 23:56   #5
Maybeso
 
Maybeso's Avatar
 
Aug 2002
Portland, OR USA

2×137 Posts
Default

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
Maybeso is offline   Reply With Quote
Old 2004-04-26, 03:05   #6
Maybeso
 
Maybeso's Avatar
 
Aug 2002
Portland, OR USA

2·137 Posts
Default

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.
Maybeso is offline   Reply With Quote
Old 2004-04-26, 16:57   #7
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

1D2416 Posts
Thumbs up

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.
R.D. Silverman is offline   Reply With Quote
Reply

Thread Tools


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

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

Thu Apr 15 09:14:49 UTC 2021 up 7 days, 3:55, 0 users, load averages: 0.85, 0.90, 1.14

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

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.