SharedPub.sagewsOpen in CoCalc
Check DH
def LC(p,q,g):
f = mod(g,p).crt(mod(1,q)); K.<x> = GF(2)[]
d = gcd(p-1,q-1); e = (p-1)*(q-1)/d; S = 0
for i in range(d/2,d):
for t in range(e/d):
gidt = g^(i+d*t)
for v in range(d): S = S + x^((gidt * f^v)%(p*q))
for t in range((p-1)/d): S = S + x^(q * (g^(i+d*t)%p))
for t in range((q-1)/d): S = S + x^(p * (g^(i+d*t)%q))
return p*q - gcd(x^(p*q)-1,S).degree()

def L(p,q):
rp = mod(2,p).log(); rq = mod(2,q).log(); rpq = mod(p,q).log();
L = p*q - 1
if rq%8==0: L = L - (q-1)/2
if rp%8==0:
L = L - (p-1)/2
if rq%4==0 or rpq%4==0: L = L - (p-1)*(q-1)/2
if rp%8==4 and rq%4!=0 and rpq%4==2: L = L - (p-1)*(q-1)/2
if rp%4==0 and rq%4!=0 and rpq%2==1: L = L - (p-1)*(q-1)/4
return L

D = 500; import random
for p in prime_range(D):
for q in prime_range(p,D):
if gcd(p-1,q-1) != 8: continue
Lpq = L(p,q); Lqp = L(q,p)
R = random.randint(0,p*q)
for g in range(R,R+p*q):
mp = mod(g,p).is_primitive_root()
mq = mod(g,q).is_primitive_root()
if mp == mq == True: break
if LC(p,q,g) != Lpq:
print ("Wrong for p = %s, q = %s, g = %s" % (p,q,g))
if LC(q,p,g) != Lqp:
print ("Wrong for p = %s, q = %s, g = %s" % (q,p,g))
else:
print ("p=%3s, q=%3s, g=%6s, L(p,q)=%6s, L(q,p)=%6s" %
(p,q,g,Lpq,Lqp))


p= 17, q= 41, g= 71, L(p,q)= 696, L(q,p)= 696 p= 17, q= 73, g= 1042, L(p,q)= 1204, L(q,p)= 916 p= 17, q= 89, g= 414, L(p,q)= 1468, L(q,p)= 764 p= 17, q=137, g= 269, L(p,q)= 2328, L(q,p)= 2328 p= 17, q=233, g= 250, L(p,q)= 3844, L(q,p)= 2916 p= 17, q=281, g= 1382, L(p,q)= 4776, L(q,p)= 2536 p= 17, q=313, g= 4323, L(p,q)= 5320, L(q,p)= 5320 p= 17, q=409, g= 1958, L(p,q)= 6952, L(q,p)= 6952 p= 17, q=457, g= 6421, L(p,q)= 7768, L(q,p)= 7768 p= 41, q= 73, g= 252, L(p,q)= 2956, L(q,p)= 2956 p= 41, q= 89, g= 3474, L(p,q)= 3604, L(q,p)= 2724 p= 41, q= 97, g= 2268, L(p,q)= 3976, L(q,p)= 3976 p= 41, q=113, g= 2126, L(p,q)= 4632, L(q,p)= 4632 p= 41, q=137, g= 2939, L(p,q)= 5616, L(q,p)= 5616 p= 41, q=193, g= 7146, L(p,q)= 7912, L(q,p)= 7912 p= 41, q=233, g= 2486, L(p,q)= 9436, L(q,p)= 7116 p= 41, q=257, g= 626, L(p,q)= 10408, L(q,p)= 7848 p= 41, q=313, g= 9682, L(p,q)= 12832, L(q,p)= 12832 p= 41, q=337, g= 790, L(p,q)= 13648, L(q,p)= 13648 p= 41, q=353, g= 6595, L(p,q)= 14472, L(q,p)= 14472 p= 41, q=409, g= 9026, L(p,q)= 16768, L(q,p)= 16768 p= 41, q=433, g= 17000, L(p,q)= 17752, L(q,p)= 17752 p= 41, q=449, g= 18128, L(p,q)= 18408, L(q,p)= 18408 p= 41, q=457, g= 190, L(p,q)= 18736, L(q,p)= 18736 p= 73, q= 89, g= 2998, L(p,q)= 3248, L(q,p)= 3248 p= 73, q=113, g= 5344, L(p,q)= 4180, L(q,p)= 8212 p= 73, q=137, g= 1664, L(p,q)= 5068, L(q,p)= 9964 p= 73, q=233, g= 1252, L(p,q)= 8504, L(q,p)= 8504 p= 73, q=257, g= 7094, L(p,q)= 9380, L(q,p)= 9380 p= 73, q=281, g= 589, L(p,q)= 10396, L(q,p)= 20476 p= 73, q=353, g= 15830, L(p,q)= 13060, L(q,p)= 25732 p= 73, q=401, g= 10645, L(p,q)= 29236, L(q,p)= 29236 p= 73, q=449, g= 30196, L(p,q)= 24676, L(q,p)= 32740 p= 89, q= 97, g= 3258, L(p,q)= 8588, L(q,p)= 8588 p= 89, q=113, g= 9043, L(p,q)= 5084, L(q,p)= 10012 p= 89, q=137, g= 8808, L(p,q)= 9156, L(q,p)= 12148 p= 89, q=193, g= 594, L(p,q)= 12908, L(q,p)= 17132 p= 89, q=233, g= 11160, L(p,q)= 10368, L(q,p)= 10368 p= 89, q=241, g= 4011, L(p,q)= 16124, L(q,p)= 21404 p= 89, q=257, g= 14959, L(p,q)= 11436, L(q,p)= 11436 p= 89, q=281, g= 9566, L(p,q)= 12644, L(q,p)= 24964 p= 89, q=313, g= 26261, L(p,q)= 20948, L(q,p)= 27812 p= 89, q=337, g= 11601, L(p,q)= 14996, L(q,p)= 14996 p= 89, q=401, g= 27495, L(p,q)= 35644, L(q,p)= 35644 p= 89, q=409, g= 24205, L(p,q)= 18404, L(q,p)= 36356 p= 89, q=433, g= 20142, L(p,q)= 28988, L(q,p)= 38492 p= 89, q=449, g= 1430, L(p,q)= 20204, L(q,p)= 39916 p= 89, q=457, g= 5956, L(p,q)= 30596, L(q,p)= 40628 p= 97, q=137, g= 9156, L(p,q)= 13288, L(q,p)= 13288 p= 97, q=233, g= 20041, L(p,q)= 22484, L(q,p)= 16916 p= 97, q=281, g= 11145, L(p,q)= 27256, L(q,p)= 20536 p=113, q=137, g= 796, L(p,q)= 11672, L(q,p)= 15480 p=113, q=233, g= 19730, L(p,q)= 26212, L(q,p)= 13220 p=113, q=313, g= 13024, L(p,q)= 35368, L(q,p)= 35368 p=113, q=409, g= 45875, L(p,q)= 34792, L(q,p)= 46216 p=113, q=457, g= 23023, L(p,q)= 38872, L(q,p)= 51640 p=137, q=193, g= 25160, L(p,q)= 26440, L(q,p)= 26440 p=137, q=233, g= 21208, L(p,q)= 31804, L(q,p)= 23916 p=137, q=241, g= 22902, L(p,q)= 33016, L(q,p)= 33016 p=137, q=257, g= 16256, L(p,q)= 35080, L(q,p)= 35080 p=137, q=281, g= 161, L(p,q)= 38496, L(q,p)= 19456 p=137, q=313, g= 22763, L(p,q)= 42880, L(q,p)= 42880 p=137, q=337, g= 4956, L(p,q)= 46000, L(q,p)= 23152 p=137, q=353, g= 38317, L(p,q)= 48360, L(q,p)= 36392 p=137, q=401, g= 28636, L(p,q)= 54936, L(q,p)= 54936 p=137, q=433, g= 13630, L(p,q)= 59320, L(q,p)= 59320 p=137, q=449, g= 56721, L(p,q)= 61512, L(q,p)= 61512 p=137, q=457, g= 15015, L(p,q)= 62608, L(q,p)= 62608 p=193, q=233, g= 18476, L(p,q)= 44852, L(q,p)= 33716 p=193, q=281, g= 10191, L(p,q)= 54232, L(q,p)= 40792 p=233, q=241, g= 30753, L(p,q)= 56036, L(q,p)= 56036 p=233, q=257, g= 18800, L(p,q)= 29940, L(q,p)= 29940 p=233, q=281, g= 58879, L(p,q)= 32876, L(q,p)= 65356 p=233, q=313, g= 49052, L(p,q)= 54716, L(q,p)= 72812 p=233, q=337, g= 5936, L(p,q)= 39260, L(q,p)= 39260 p=233, q=353, g= 74850, L(p,q)= 41300, L(q,p)= 82132 p=233, q=401, g= 34164, L(p,q)= 70116, L(q,p)= 93316 p=233, q=409, g= 89478, L(p,q)= 71516, L(q,p)= 95180 p=233, q=433, g= 5892, L(p,q)= 50660, L(q,p)=100772 p=233, q=449, g= 66045, L(p,q)= 78516, L(q,p)=104500 p=233, q=457, g= 80978, L(p,q)=106364, L(q,p)=106364 p=257, q=281, g= 16088, L(p,q)= 36248, L(q,p)= 72088 p=257, q=313, g= 41072, L(p,q)= 60344, L(q,p)= 80312 p=257, q=409, g= 62432, L(p,q)= 78872, L(q,p)=104984 p=257, q=457, g= 42468, L(p,q)= 58952, L(q,p)=117320 p=281, q=313, g= 50003, L(p,q)= 44272, L(q,p)= 87952 p=281, q=353, g= 24434, L(p,q)= 99192, L(q,p)= 99192 p=281, q=409, g= 60648, L(p,q)= 57808, L(q,p)=114928 p=281, q=433, g= 79324, L(p,q)= 91432, L(q,p)=121672 p=281, q=457, g=128365, L(p,q)= 96496, L(q,p)=128416 p=313, q=353, g= 43879, L(p,q)=110488, L(q,p)= 83032 p=313, q=401, g= 92123, L(p,q)=125512, L(q,p)=125512 p=313, q=449, g= 76594, L(p,q)=140536, L(q,p)=140536 p=353, q=409, g= 65870, L(p,q)=108472, L(q,p)=144376 p=353, q=457, g=118114, L(p,q)=121192, L(q,p)=161320 p=401, q=409, g= 79698, L(p,q)=164008, L(q,p)=164008 p=401, q=457, g=151086, L(p,q)=183256, L(q,p)=183256 p=409, q=449, g=169797, L(p,q)=183640, L(q,p)=183640 p=449, q=457, g= 47561, L(p,q)=205192, L(q,p)=205192