Sharedsupport / 2016-06-02-151908-factoring-times.sagewsOpen in CoCalc
Examples for support purposes...
def time_to_factor(bits):
    p = next_prime(ZZ.random_element(2^(bits-1)+1000000, 2^bits-1000000))
    q = next_prime(ZZ.random_element(2^bits+100000, 2^(bits+1)-1000000))
    print 'bits =', len((p*q).bits())
    t = cputime()
    factor(p*q)
    return cputime(t)
time_to_factor(30)
bits = 60 0.0
time_to_factor(40)
bits = 81 0.01199999999999335
time_to_factor(50)
bits = 101 0.02400000000000091
time_to_factor(70)
bits = 140 0.38800000000000523
time_to_factor(85)
bits = 171 2.239999999999995
time_to_factor(90)
bits = 180 3.4639999999999986
time_to_factor(91)
bits = 183 5.2719999999999985
time_to_factor(92)
bits = 185 7.520000000000003
time_to_factor(93)
bits = 187 6.412000000000006
time_to_factor(94)
bits = 189 10.951999999999998
time_to_factor(95)
bits = 191 7.804000000000016
time_to_factor(96)
bits = 193 7.583999999999989
time_to_factor(97)
bits = 195 10.348000000000013
time_to_factor(98)
bits = 197 13.887999999999991
time_to_factor(99)
bits = 199 12.800000000000011
time_to_factor(100)
bits = 200 15.591999999999985

Roughly doubles in time every 5 bits.

est_s = 2^((310-200)//5) * 15
est_s
62914560
# years to finish
est_s / 3600/24/365.
1.99500761035008

msieve: "faster than any other code implementing any other algorithm [...] for completely factoring general inputs between 40 and 100 digits"

and 100 digits is:

len((10^100).bits())
333