mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > YAFU

Reply
 
Thread Tools
Old 2012-11-12, 12:25   #1
Ogonia
 
Nov 2012

510 Posts
Default 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)
Ogonia is offline   Reply With Quote
Old 2012-11-12, 14:48   #2
bearnol
 
bearnol's Avatar
 
Sep 2005

127 Posts
Default

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
bearnol is offline   Reply With Quote
Old 2012-11-12, 15:33   #3
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

2×5×7×47 Posts
Default

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
bsquared is offline   Reply With Quote
Old 2012-11-12, 15:38   #4
axn
 
axn's Avatar
 
Jun 2003

13×192 Posts
Default

Quote:
Originally Posted by Ogonia View Post
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?
axn is offline   Reply With Quote
Old 2012-11-12, 16:08   #5
lorgix
 
lorgix's Avatar
 
Sep 2010
Scandinavia

3×5×41 Posts
Default

Quote:
Originally Posted by Ogonia View Post
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
lorgix is offline   Reply With Quote
Old 2012-11-12, 16:10   #6
bearnol
 
bearnol's Avatar
 
Sep 2005

1778 Posts
Default

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
bearnol is offline   Reply With Quote
Old 2012-11-12, 17:30   #7
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

280216 Posts
Default

Quote:
Originally Posted by Ogonia View Post
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.

Note added in edit:

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
xilman is online now   Reply With Quote
Old 2012-11-12, 17:31   #8
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

100010000111102 Posts
Default

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
LaurV is offline   Reply With Quote
Old 2012-11-12, 18:51   #9
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

33×72 Posts
Default

Quote:
Originally Posted by xilman View Post
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.
alpertron is offline   Reply With Quote
Old 2012-11-12, 21:17   #10
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

33×72 Posts
Default

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
alpertron is offline   Reply With Quote
Old 2012-11-13, 00:13   #11
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

132310 Posts
Default

The previous message works if the factors are both even or odd. Naturally we are interested in the second case.
alpertron is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
factoring special form of 1024-bit RSA key Johnatan YAFU 20 2016-04-22 04:33
Factoring a 1024-bit RSA with GNFS? BotXXX Factoring 25 2015-09-02 08:27
Factoring 1024-bit number using Yafu Anyone YAFU 30 2015-09-01 13:25
Riesel and Sierp numbers bases <= 1024 R. Gerbicz Conjectures 'R Us 22 2009-12-29 20:21
[finished] prime field ECC curves up to 1024 bits retina Math 0 2007-12-09 03:30

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

Sat Sep 19 19:36:51 UTC 2020 up 9 days, 16:47, 1 user, load averages: 1.59, 1.60, 1.50

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.