We're examining the RSA algorithm and would like to know how much time it would take an intel i-7 core (@ 2.50 gHz) to factorise the RSA-public key.
we wrote a piece of java for this, and I don't know how effective it is
public static String factorise(long l)
{
double a = Math.floor(Math.sqrt(l));
while(l/a != Math.round(l/a))
{
a--;
}
return (long)a + ", " + (long)(l/a);
}
With a number around 2^45 it took the PC approximately 33 milliseconds. In theory, how long would it take to factorise a number around 2^1024?
Thanks in advance :)
Your algorithm is O(2^n), where n is the number of bits in the original number l
. (that means that a single bit more will double the runtime, because twice as many numbers a
must be checked - on average)
If 45 bits took 33 ms, then 1024 bits will take approx. 2^1024 / 2^45 * 33ms = 5.34654 * 10^285 years.
This of course assumes, that the 1024bit code is exactly as efficient as your code for long numbers (64bit?). Which is a bold statement, considering that 10^285 years is more than enough time to switch to the General number field sieve and scratch a few million years of that time...
In 2009 the 768 bit number rsa-768 was cracked using about 1000 cores and 2 years of calculations. Assuming they used the General number field sieve (a very fair assumption) it would take them 7481 years to crack a 1024 bit number using the same hardware.
Or using only your i7 with this algorithm: about 3 million years. Still a long time.... ;)