3 ms·
Don't confuse brute forcing 2^65 possibilities with factoring a 2^65 bit semi-prime (n in RSA). I factored a 2^65.4 bit semi-prime using Sagemath on an M1 in m
by john_alan 6y ago
Don't confuse brute forcing 2^65 possibilities with factoring a 2^65 bit semi-prime (n in RSA).
I factored a 2^65.4 bit semi-prime using Sagemath on an M1 in milliseconds.
// get two random primes (pretend P, Q)
sage: random_prime(2^34)
12697300267
sage: random_prime(2^33)
3962800609
// make a semi-prime (pretend N)
sage: 12697300267*3962800609
50316869230723462603
// check length of semi-prime (65-bits)
sage: log(50316869230723462603,2).n()
65.4476759618453
// factor it in 18milliseconds.
sage: time factor(50316869230723462603)
CPU times: user 9.78 ms, sys: 9.07 ms, total: 18.8 ms
Wall time: 23.2 ms
2^1024 bit RSA is about 2^80 in bit strength.
This example was 2^65 bit RSA, which is negligible in bit-strength.
- photon-torpedo 6y agoGNU coreutils `factor` program can do so as well: bash$ time factor 50316869230723462603 50316869230723462603: 3962800609 12697300267 real 0m0.009s user 0m0.009s sys 0m0.000s