Factor 1024-bit on 2x512 bit (help)

Ogonia · 2012-11-12, 12:25

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)

bearnol · 2012-11-12, 14:48

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

bsquared · 2012-11-12, 15:33

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.

axn · 2012-11-12, 15:38

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?

lorgix · 2012-11-12, 16:08

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?

bearnol · 2012-11-12, 16:10

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

xilman · 2012-11-12, 17:30

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.

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.

LaurV · 2012-11-12, 17:31

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.

alpertron · 2012-11-12, 18:51

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*2¹⁰²⁰ be the product of two 512-bit numbers: it is the square of 3*2⁵¹⁰.

Let N = M+2²⁷⁴-1

Let p = 7*2⁵⁰⁹

Let q = int(N/p)

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

So only the first 513 bits are the same.

alpertron · 2012-11-12, 21:17

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.

alpertron · 2012-11-13, 00:13

The previous message works if the factors are both even or odd. Naturally we are interested in the second case.

2012-11-12, 12:25	#1
Ogonia Nov 2012 5 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, 15:33	#3
bsquared "Ben" Feb 2007 3·1,171 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, 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:31	#8
LaurV Romulan Interpreter Jun 2011 Thailand 7·1,373 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, 21:17	#10
alpertron Aug 2002 Buenos Aires, Argentina 2×683 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-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-13, 00:13	#11
alpertron Aug 2002 Buenos Aires, Argentina 10101010110₂ 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
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