CoCalc Shared Filessupport / 2016-06-02-151908-factoring-times.sagews
Authors: Harald Schilly, William A. Stein
Description: 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