108.sagews

# 6.1 (i)
d=72
factor(d)

2^3 * 3^2

g=5
d1=36
d2=24
power_mod(g,d1,73)==1, power_mod(g,d2,73)==1

(False, False)

# 6.2 (ii)
g=5
x=6
G=power_mod(g,9,73)
X=power_mod(x,9,73)
for i in srange (0,8):
    if power_mod(G,i,73)==X:
        print('X='),
    print power_mod(G,i,73)

1 10 27 51 72 63 X= 46 22

g=5
x=6
G=power_mod(g,8,73)
X=power_mod(x,8,73)
for i in srange (0,9):
    if power_mod(G,i,73)==X:
        print('X='),
    print power_mod(G,i,73)

1 2 4 8 16 X= 32 64 55 37

# combine the discrete logs in the subgroup for the discrete log in the large group
a=crt(6,5,8,9)
a

14

# test
x==power_mod(g,a,73)

True

# 6.1 (iii)
d=162
factor(d)

2 * 3^4

g=7
d1=81
d2=54
power_mod(g,d1,163)==1, power_mod(g,d2,163)==1

(False, False)

# 6.2 (iii)
# First the easy part in the subgroup generated by g^81
g=7
x=20
G=power_mod(g,81,163)
X=power_mod(x,81,163)
G, X

(162, 162)

# Now the harder part in the subgroup generated by g^2.
# The corresponding quantities therein are marked with a tilde, or shorter with the prefix t
# First, consider the "small" subgroup generated by tg^27.
a=[[],[],[],[]]
tg=power_mod(g,2,163)
tx=power_mod(x,2,163)
print [tg, tx]
G=power_mod(tg,27,163)
X=power_mod(tx,27,163)
print [G,X]
for i in srange (0,3):
    if power_mod(G,i,163)==X:
        a[0]=i
        print('X='),
    print power_mod(G,i,163)

[49, 74] [104, 58] 1 104 X= 58

a[0]

2

# Second, consider the "slightly larger" subgroup generated by tg^9. 
GG=power_mod(tg,9,163)
XX=power_mod(tx,9,163)
print [GG,XX]
YY=mod(XX*inverse_mod(power_mod(GG,a[0],163), 163), 163)
print YY
for i in srange (0,3):
    if power_mod(G,i,163)==YY:
        a[1]=i
        print('YY='),
    print power_mod(G,i,163)

[40, 53] 58 1 104 YY= 58

power_mod(GG,a[0],163)

133

a[1]

2

# Third, make it larger going for the subgroup generated by tg^3. 
GGG=power_mod(tg,3,163)
XXX=power_mod(tx,3,163)
print [GGG,XXX]
YYY=mod(XXX*inverse_mod(power_mod(GGG,a[0],163)*power_mod(GG,a[1],163), 163), 163)
print YYY
for i in srange (0,3):
    if power_mod(G,i,163)==YYY:
        a[2]=i
        print('YYY='),
    print power_mod(G,i,163)

[126, 6] 1 YYY= 1 104 58

mod(power_mod(GGGG,a[0],163)*power_mod(GGG,a[1],163)*power_mod(GG,a[2],163),163)

74

a[2]

0

# Finally in the group by tg itself. 
GGGG=tg
XXXX=tx
print [GGGG,XXXX]
YYYY=mod(XXXX*inverse_mod(power_mod(GGGG,a[0],163)*power_mod(GGG,a[1],163)*power_mod(GG,a[2],163), 163), 163)
print YYYY
for i in srange (0,3):
    if power_mod(G,i,163)==YYYY:
        a[3]=i
        print('YYYY='),
    print power_mod(G,i,163)

[49, 74] 1 YYYY= 1 104 58

27*a[3]+9*a[2]+3*a[1]+a[0]

8

mod(crt(1,8,2,81),162)

89

power_mod(7,89,163)

20