137.sagews

# (i)
# heuristic estimate
counter=0
B=12
for i in srange(1000):
    x=floor(1000*random())+1
    F=factor(x)
    if x==1 or F[-1][0]<B:
        counter=counter+1
counter

203

# precise number
count=0
B=12
for i in srange(1,1001):
    F=factor(i)
    if i==1 or F[-1][0]<B:
        count=count+1
count

192

# (ii)
p=227
g=2
B=11
# unknowns
# BB=[2,3,5,7,11]
a,b,c,d,e = var('a,b,c,d,e')

EE=[40,59,66]
for expo in EE:
    print [expo, factor(power_mod(g,expo,p))]

[40, 2 * 5 * 11] [59, 2^2 * 3 * 5] [66, 3^3 * 7]

g1= 40==a + c + e
g2= 59==2*a + b + c
g3= 66==3*b+d
[g1, g2, g3]

[40 == e + c + a, 59 == c + b + 2*a, 66 == d + 3*b]

# (iii)
g4= a == 1
for expo in srange(11,20):
    print [expo, factor(power_mod(g,expo,p))]

[11, 5] [12, 2 * 5] [13, 2^2 * 5] [14, 2^3 * 5] [15, 2^4 * 5] [16, 2^5 * 5] [17, 3 * 31] [18, 2 * 3 * 31] [19, 5 * 29]

g5= 12==a + c
[g1, g2, g3, g4, g5]

[40 == e + c + a, 59 == c + b + 2*a, 66 == d + 3*b, a == 1, 12 == c + a]

# (iv)
solve_mod([g1,g2,g3,g4,g5],p)

# double-check
a == 1
b == 46
c == 11
d == 154
e == 28

# (v)
x = 224
for i in srange(10):
    e=floor(p*random())
    y=mod(x*power_mod(g,e,p),p)
    F=factor(y)
    if y==1 or F[-1][0]<B:
        print e,F

x=Mod(224,p) 
g=Mod(2,p)
discrete_log(x,g)

159