How long would it take my i-7 processor to factorise a 1024 bits number (consisting of just 2 prime factors) [closed]

Question

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center.

Closed 9 years ago.

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 :)

Answer 1

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.... ;)