2217.sagews

# The purpose of this exercise is to give you some intuition as to 
# the complexity of the problem of factoring large integers.
# The program factors integers that are 30 digits to 65 digits long, and
# plots how long it takes to factor each randomly selected number.
# Your challenge is to explain why the graph appears as it does.
ttab = [n for n in range(30, 65)]
for i in range(30,65):
    t = cputime()
    n = ZZ.random_element(10^i)
    print " "
    print "The number to be factored has ",i,"  decimal digits"
    print "The number is ",n
    print "Its factors are:"
    print factor(n)
    print "The CPU time taken in milliseconds is"
    print 1000*cputime(t)
    ttab[i-30]=1000*cputime(t)
point(((40,ttab[9]), (41,ttab[10]), (42,ttab[11]),(43,ttab[12]),(44,ttab[13]),(45,ttab[14]),(46,ttab[15]),(47,ttab[16]),(48,ttab[17]),(49,ttab[18]),(50,ttab[19]),(51,ttab[20]),(52,ttab[21]),(53,ttab[22]),(54,ttab[23]),(55,ttab[24]),(56,ttab[25]),(57,ttab[26]),(58,ttab[27]),(59,ttab[28]),(60,ttab[29]),(61,ttab[30]),(62,ttab[31]),(63,ttab[32]),(64,ttab[33]),(65,ttab[34])),  rgbcolor=hue(1), pointsize=50)

ttab