20121112, 12:25  #1 
Nov 2012
5 Posts 
Factor 1024bit on 2x512 bit (help)
need to find a pair of 512bit 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) 
20121112, 14:48  #2 
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 2digit 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 builtin to YAFU... J 
20121112, 15:33  #3 
"Ben"
Feb 2007
3,271 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 20121112 at 15:36 Reason: result doesn't need to be prime AFAICT... just close to an integer 
20121112, 15:38  #4  
Jun 2003
2×2,333 Posts 
Quote:
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? 

20121112, 16:08  #5  
Sep 2010
Scandinavia
3·5·41 Posts 
Quote:
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 20121112 at 16:21 Reason: misinterpretation 

20121112, 16:10  #6 
Sep 2005
7F_{16} 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 digitlevel. 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 20121112 at 16:23 Reason: prob ought to mention wrote this before seeing lorgix's post 
20121112, 17:30  #7  
Bamboozled!
May 2003
Down not across
3^{2}×1,129 Posts 
Quote:
Let your known 1024bit number be M. Let your 750bit number be n. Then 2^274 * n + (2^274  1) is a 1024bit number which shares the first 750 bits of M. Call this value N. Chose an arbitrary 512but integer p. Let q = int (N/p) The 1024bit 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 512bit 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 20121112 at 17:33 

20121112, 17:31  #8 
Romulan Interpreter
Jun 2011
Thailand
5×11×157 Posts 
Write down your 750 bits, write a 1, write 1024751=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*(x1), 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 20121112 at 17:34 
20121112, 18:51  #9  
Aug 2002
Buenos Aires, Argentina
2^{3}×3×5×11 Posts 
Quote:
Let N = M+2^{274}1 Let p = 7*2^{509} Let q = int(N/p) Then log(Mp*q)/log(2) = 511 So only the first 513 bits are the same. 

20121112, 21:17  #10 
Aug 2002
Buenos Aires, Argentina
2^{3}×3×5×11 Posts 
Let N be a nonsquare 1024bit number.
Let From: (1) We find: The factors are in this case x+y and xy. Error calculation: From (1) the error is less than So the first 1024258 = 766 bits do not change. Last fiddled with by alpertron on 20121112 at 21:19 
20121113, 00:13  #11 
Aug 2002
Buenos Aires, Argentina
2^{3}·3·5·11 Posts 
The previous message works if the factors are both even or odd. Naturally we are interested in the second case.

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