mersenneforum.org > YAFU Factor 1024-bit on 2x512 bit (help)
 Register FAQ Search Today's Posts Mark Forums Read

 2012-11-12, 12:25 #1 Ogonia   Nov 2012 510 Posts Factor 1024-bit on 2x512 bit (help) need to find a pair of 512-bit numbers that when multiplied will give 1024 bit number, similar to a 1024 bit number given in the first 750 binary digits (is there some function in yafu? or some one know algoritm for this task)
 2012-11-12, 14:48 #2 bearnol     Sep 2005 127 Posts Interesting question. (don't know whether it's homework or not! :) ) If one knows definitely in advance that there are exactly two factors of the same length (ie it's a semiprime), then it might be possible to 'unzip' the number down to 3/4 of its length, as you surmise. [Consider the case for 2 2-digit numbers determining the first 3 digits of their product - though I'll admit I haven't actually tried this] Then if the rest of the digits match, one actually has an (exact) factorization. AFAIK, there is no such functionality already built-in to YAFU... J
 2012-11-12, 15:33 #3 bsquared     "Ben" Feb 2007 23×419 Posts There is nothing built into YAFU to do this automatically. There are a few tools that might be useful, like randb() and nextprime(), but probably no more useful than equivalent things in a more fully featured program like PARI/GP. After thinking about it for a full 60 seconds the best I can come up with is generate a random 512 bit prime, divide it into your 1024 bit number, and hope the result is very close to an integer. Repeat as necessary. I have no idea how likely the success this 'random trial' approach would be, so I don't know how many times you'd need to try, on average. Its very likely it could take a long time, and the expectation would of course increase the more 'similar' you want the product to be. Last fiddled with by bsquared on 2012-11-12 at 15:36 Reason: result doesn't need to be prime AFAICT... just close to an integer
2012-11-12, 15:38   #4
axn

Jun 2003

478910 Posts

Quote:
 Originally Posted by Ogonia need to find a pair of 512-bit numbers that when multiplied will give 1024 bit number, similar to a 1024 bit number given in the first 750 binary digits (is there some function in yafu? or some one know algoritm for this task)
Let me see if I understood you correctly.

You have a target number that is 1024 bits in length. You want to find another 1024 bit number that is a product of 2 512 bit numbers, and which also matches the target number in the first 750 MSB?

Did I get that right?

2012-11-12, 16:08   #5
lorgix

Sep 2010
Scandinavia

11478 Posts

Quote:
 Originally Posted by Ogonia need to find a pair of 512-bit numbers that when multiplied will give 1024 bit number, similar to a 1024 bit number given in the first 750 binary digits (is there some function in yafu? or some one know algoritm for this task)
You can not factor a kilobit RSA-key on your own.

Even if you could it would cost a fortune.

If you understand what you'll read in this document, then you'll also understand why you can not factor the number you're looking at.

Edit: Seems I misunderstood. Did axn get it right?

Last fiddled with by lorgix on 2012-11-12 at 16:21 Reason: misinterpretation

 2012-11-12, 16:10 #6 bearnol     Sep 2005 127 Posts Couple more observations (hopefully!) 1) I imagine one could could equally well attack the number from the LSB (rather than) MSB end 2) To remove the restriction on semiprimes, pad with zeroes, and equivalently 3) To remove the restriction on only two (prime) factors, check for exact divisibility at each digit-level. I'd be interested to see some analysis of how well this would work - I imagine it would get quite hairy [between 1/4 length and 3/4 length], but you never know... :) J Last fiddled with by bearnol on 2012-11-12 at 16:23 Reason: prob ought to mention wrote this before seeing lorgix's post
2012-11-12, 17:30   #7
xilman
Bamboozled!

"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

37×281 Posts

Quote:
 Originally Posted by Ogonia need to find a pair of 512-bit numbers that when multiplied will give 1024 bit number, similar to a 1024 bit number given in the first 750 binary digits (is there some function in yafu? or some one know algoritm for this task)
Trivial.

Let your known 1024-bit number be M.

Let your 750-bit number be n. Then 2^274 * n + (2^274 - 1) is a 1024-bit number which shares the first 750 bits of M. Call this value N. Chose an arbitrary 512-but integer p. Let q = int (N/p)

The 1024-bit number p*q now shares the first 750 bits of your number.

This is very similar to the machinations used to create the 512-bit RSA challenge in Simon Singh's The Code Book but in that instance much more stringent conditions were imposed.

Last fiddled with by xilman on 2012-11-12 at 17:33

 2012-11-12, 17:31 #8 LaurV Romulan Interpreter     Jun 2011 Thailand 214028 Posts Write down your 750 bits, write a 1, write 1024-751=273 zeros. This is the middle of the interval you are targeting. Take x=square root of it. Play with (x^2), x*(x+1), x*(x-1), etc, around the square root. You will almost always find a solution in seconds with pari (depending of your 750 bits, the solution is almost always the square root +/- something very small, you have 2^273 numbers there, and one must split right). edit, grr, crosspost, but xilman's solution is more nice. Last fiddled with by LaurV on 2012-11-12 at 17:34
2012-11-12, 18:51   #9
alpertron

Aug 2002
Buenos Aires, Argentina

24728 Posts

Quote:
 Originally Posted by xilman Trivial. Let your known 1024-bit number be M. Let your 750-bit number be n. Then 2^274 * n + (2^274 - 1) is a 1024-bit number which shares the first 750 bits of M. Call this value N. Chose an arbitrary 512-but integer p. Let q = int (N/p) The 1024-bit number p*q now shares the first 750 bits of your number.
Let M = 9*21020 be the product of two 512-bit numbers: it is the square of 3*2510.

Let N = M+2274-1

Let p = 7*2509

Let q = int(N/p)

Then log(M-p*q)/log(2) = 511

So only the first 513 bits are the same.

 2012-11-12, 21:17 #10 alpertron     Aug 2002 Buenos Aires, Argentina 53A16 Posts Let N be a non-square 1024-bit number. Let $x \,=\, ceil(sqrt{N})$ From: $x^2-y^2 \,=\, N$ (1) We find: $y \,=\, round(sqrt{x^2-N})$ The factors are in this case x+y and x-y. Error calculation: $x < 2^{512}$ $x^2-N\,<\,x^2-(x-1)^2\. <\, 2x+1\, <\, 2^{513}$ $y < 2^{257}$ From (1) the error is less than $(y+1)^2-y^2\, = \,2y+1 \,< \,2^{258}$ So the first 1024-258 = 766 bits do not change. Last fiddled with by alpertron on 2012-11-12 at 21:19
 2012-11-13, 00:13 #11 alpertron     Aug 2002 Buenos Aires, Argentina 2·3·223 Posts The previous message works if the factors are both even or odd. Naturally we are interested in the second case.

 Similar Threads Thread Thread Starter Forum Replies Last Post Johnatan YAFU 20 2016-04-22 04:33 BotXXX Factoring 25 2015-09-02 08:27 Anyone YAFU 30 2015-09-01 13:25 R. Gerbicz Conjectures 'R Us 22 2009-12-29 20:21 retina Math 0 2007-12-09 03:30

All times are UTC. The time now is 19:49.

Thu Dec 3 19:49:11 UTC 2020 up 16 hrs, 1 user, load averages: 1.09, 1.16, 1.23