SharedPub.sagewsOpen in CoCalc
Check DH
sage_server.MAX_OUTPUT_MESSAGES = 1000
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 = 1000; 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= 345, L(p,q)= 696, L(q,p)= 696 p= 17, q= 73, g= 1163, L(p,q)= 1204, L(q,p)= 916 p= 17, q= 89, g= 1448, L(p,q)= 1468, L(q,p)= 764 p= 17, q=137, g= 261, L(p,q)= 2328, L(q,p)= 2328 p= 17, q=233, g= 2587, L(p,q)= 3844, L(q,p)= 2916 p= 17, q=281, g= 2173, L(p,q)= 4776, L(q,p)= 2536 p= 17, q=313, g= 2748, L(p,q)= 5320, L(q,p)= 5320 p= 17, q=409, g= 471, L(p,q)= 6952, L(q,p)= 6952 p= 17, q=457, g= 6352, L(p,q)= 7768, L(q,p)= 7768 p= 17, q=521, g= 6185, L(p,q)= 8856, L(q,p)= 8856 p= 17, q=569, g= 9177, L(p,q)= 9672, L(q,p)= 9672 p= 17, q=601, g= 4789, L(p,q)= 9916, L(q,p)= 7516 p= 17, q=617, g= 4104, L(p,q)= 10488, L(q,p)= 8024 p= 17, q=761, g= 3992, L(p,q)= 12936, L(q,p)= 12936 p= 17, q=809, g= 6701, L(p,q)= 13752, L(q,p)= 13752 p= 17, q=857, g= 3057, L(p,q)= 14568, L(q,p)= 14568 p= 17, q=937, g= 14181, L(p,q)= 15460, L(q,p)= 15460 p= 17, q=953, g= 10722, L(p,q)= 16200, L(q,p)= 16200 p= 41, q= 73, g= 2794, L(p,q)= 2956, L(q,p)= 2956 p= 41, q= 89, g= 3227, L(p,q)= 3604, L(q,p)= 2724 p= 41, q= 97, g= 1511, L(p,q)= 3976, L(q,p)= 3976 p= 41, q=113, g= 34, L(p,q)= 4632, L(q,p)= 4632 p= 41, q=137, g= 2384, L(p,q)= 5616, L(q,p)= 5616 p= 41, q=193, g= 5623, L(p,q)= 7912, L(q,p)= 7912 p= 41, q=233, g= 1418, L(p,q)= 9436, L(q,p)= 7116 p= 41, q=257, g= 6730, L(p,q)= 10408, L(q,p)= 7848 p= 41, q=313, g= 9613, L(p,q)= 12832, L(q,p)= 12832 p= 41, q=337, g= 10304, L(p,q)= 13648, L(q,p)= 13648 p= 41, q=353, g= 9361, L(p,q)= 14472, L(q,p)= 14472 p= 41, q=409, g= 15914, L(p,q)= 16768, L(q,p)= 16768 p= 41, q=433, g= 17652, L(p,q)= 17752, L(q,p)= 17752 p= 41, q=449, g= 12061, L(p,q)= 18408, L(q,p)= 18408 p= 41, q=457, g= 18398, L(p,q)= 18736, L(q,p)= 18736 p= 41, q=569, g= 4728, L(p,q)= 23328, L(q,p)= 23328 p= 41, q=577, g= 22475, L(p,q)= 23656, L(q,p)= 17896 p= 41, q=593, g= 7276, L(p,q)= 24312, L(q,p)= 18392 p= 41, q=617, g= 5706, L(p,q)= 25296, L(q,p)= 12976 p= 41, q=673, g= 4741, L(p,q)= 27592, L(q,p)= 27592 p= 41, q=769, g= 6138, L(p,q)= 31528, L(q,p)= 31528 p= 41, q=809, g= 5588, L(p,q)= 33168, L(q,p)= 33168 p= 41, q=857, g= 34392, L(p,q)= 35136, L(q,p)= 35136 p= 41, q=929, g= 34552, L(p,q)= 38088, L(q,p)= 38088 p= 41, q=937, g= 6700, L(p,q)= 37948, L(q,p)= 28588 p= 41, q=953, g= 11303, L(p,q)= 39072, L(q,p)= 39072 p= 41, q=977, g= 39928, L(p,q)= 40056, L(q,p)= 40056 p= 73, q= 89, g= 5066, L(p,q)= 3248, L(q,p)= 3248 p= 73, q=113, g= 5026, L(p,q)= 4180, L(q,p)= 8212 p= 73, q=137, g= 9422, L(p,q)= 5068, L(q,p)= 9964 p= 73, q=233, g= 321, L(p,q)= 8504, L(q,p)= 8504 p= 73, q=257, g= 3077, L(p,q)= 9380, L(q,p)= 9380 p= 73, q=281, g= 13053, L(p,q)= 10396, L(q,p)= 20476 p= 73, q=353, g= 25205, L(p,q)= 13060, L(q,p)= 25732 p= 73, q=401, g= 6337, L(p,q)= 29236, L(q,p)= 29236 p= 73, q=449, g= 16034, L(p,q)= 24676, L(q,p)= 32740 p= 73, q=521, g= 28809, L(p,q)= 28636, L(q,p)= 37996 p= 73, q=569, g= 25225, L(p,q)= 31276, L(q,p)= 41500 p= 73, q=593, g= 24554, L(p,q)= 21940, L(q,p)= 43252 p= 73, q=617, g= 21807, L(p,q)= 22828, L(q,p)= 45004 p= 73, q=641, g= 23736, L(p,q)= 46756, L(q,p)= 46756 p= 73, q=761, g= 32592, L(p,q)= 41836, L(q,p)= 55516 p= 73, q=809, g= 21190, L(p,q)= 29932, L(q,p)= 59020 p= 73, q=857, g= 27198, L(p,q)= 62524, L(q,p)= 62524 p= 73, q=881, g= 41623, L(p,q)= 32156, L(q,p)= 32156 p= 73, q=929, g= 62736, L(p,q)= 51076, L(q,p)= 67780 p= 73, q=953, g= 17419, L(p,q)= 69532, L(q,p)= 69532 p= 73, q=977, g= 45200, L(p,q)= 53716, L(q,p)= 71284 p= 89, q= 97, g= 328, L(p,q)= 8588, L(q,p)= 8588 p= 89, q=113, g= 3456, L(p,q)= 5084, L(q,p)= 10012 p= 89, q=137, g= 4488, L(p,q)= 9156, L(q,p)= 12148 p= 89, q=193, g= 8715, L(p,q)= 12908, L(q,p)= 17132 p= 89, q=233, g= 11967, L(p,q)= 10368, L(q,p)= 10368 p= 89, q=241, g= 8102, L(p,q)= 16124, L(q,p)= 21404 p= 89, q=257, g= 9140, L(p,q)= 11436, L(q,p)= 11436 p= 89, q=281, g= 2960, L(p,q)= 12644, L(q,p)= 24964 p= 89, q=313, g= 2566, L(p,q)= 20948, L(q,p)= 27812 p= 89, q=337, g= 1205, L(p,q)= 14996, L(q,p)= 14996 p= 89, q=401, g= 19265, L(p,q)= 35644, L(q,p)= 35644 p= 89, q=409, g= 29919, L(p,q)= 18404, L(q,p)= 36356 p= 89, q=433, g= 7851, L(p,q)= 28988, L(q,p)= 38492 p= 89, q=449, g= 2396, L(p,q)= 20204, L(q,p)= 39916 p= 89, q=457, g= 4641, L(p,q)= 30596, L(q,p)= 40628 p= 89, q=521, g= 43240, L(p,q)= 34884, L(q,p)= 46324 p= 89, q=569, g= 35320, L(p,q)= 38100, L(q,p)= 50596 p= 89, q=577, g= 34138, L(p,q)= 25964, L(q,p)= 51308 p= 89, q=593, g= 7817, L(p,q)= 26684, L(q,p)= 52732 p= 89, q=601, g= 982, L(p,q)= 26744, L(q,p)= 26744 p= 89, q=641, g= 48419, L(p,q)= 57004, L(q,p)= 57004 p= 89, q=673, g= 56156, L(p,q)= 59852, L(q,p)= 59852 p= 89, q=761, g= 37183, L(p,q)= 34244, L(q,p)= 67684 p= 89, q=769, g= 16478, L(p,q)= 68396, L(q,p)= 68396 p= 89, q=809, g= 50486, L(p,q)= 36404, L(q,p)= 71956 p= 89, q=857, g= 27053, L(p,q)= 57396, L(q,p)= 76228 p= 89, q=929, g= 27652, L(p,q)= 41804, L(q,p)= 82636 p= 89, q=937, g= 58034, L(p,q)= 41696, L(q,p)= 41696 p= 89, q=953, g= 7825, L(p,q)= 63828, L(q,p)= 84772 p= 89, q=977, g= 4334, L(p,q)= 43964, L(q,p)= 86908 p= 97, q=137, g= 3693, L(p,q)= 13288, L(q,p)= 13288 p= 97, q=233, g= 13151, L(p,q)= 22484, L(q,p)= 16916 p= 97, q=281, g= 21345, L(p,q)= 27256, L(q,p)= 20536 p= 97, q=521, g= 3723, L(p,q)= 50536, L(q,p)= 50536 p= 97, q=569, g= 15169, L(p,q)= 55192, L(q,p)= 55192 p= 97, q=617, g= 37322, L(p,q)= 59848, L(q,p)= 59848 p= 97, q=761, g= 71208, L(p,q)= 73816, L(q,p)= 73816 p= 97, q=809, g= 14994, L(p,q)= 78472, L(q,p)= 78472 p= 97, q=857, g= 34054, L(p,q)= 83128, L(q,p)= 83128 p= 97, q=953, g= 31338, L(p,q)= 92440, L(q,p)= 92440 p=113, q=137, g= 4214, L(p,q)= 11672, L(q,p)= 15480 p=113, q=233, g= 11327, L(p,q)= 26212, L(q,p)= 13220 p=113, q=313, g= 25517, L(p,q)= 35368, L(q,p)= 35368 p=113, q=409, g= 7581, L(p,q)= 34792, L(q,p)= 46216 p=113, q=457, g= 11366, L(p,q)= 38872, L(q,p)= 51640 p=113, q=521, g= 38571, L(p,q)= 29752, L(q,p)= 58872 p=113, q=569, g= 14889, L(p,q)= 64296, L(q,p)= 64296 p=113, q=601, g= 19871, L(p,q)= 67612, L(q,p)= 34012 p=113, q=761, g= 71897, L(p,q)= 43432, L(q,p)= 85992 p=113, q=809, g= 20951, L(p,q)= 91416, L(q,p)= 91416 p=113, q=857, g= 94840, L(p,q)= 72872, L(q,p)= 96840 p=113, q=937, g= 54879, L(p,q)=105412, L(q,p)= 52996 p=137, q=193, g= 22104, L(p,q)= 26440, L(q,p)= 26440 p=137, q=233, g= 23422, L(p,q)= 31804, L(q,p)= 23916 p=137, q=241, g= 29207, L(p,q)= 33016, L(q,p)= 33016 p=137, q=257, g= 2487, L(p,q)= 35080, L(q,p)= 35080 p=137, q=281, g= 23019, L(p,q)= 38496, L(q,p)= 19456 p=137, q=313, g= 21818, L(p,q)= 42880, L(q,p)= 42880 p=137, q=337, g= 21535, L(p,q)= 46000, L(q,p)= 23152 p=137, q=353, g= 29991, L(p,q)= 48360, L(q,p)= 36392 p=137, q=401, g= 610, L(p,q)= 54936, L(q,p)= 54936 p=137, q=433, g= 46455, L(p,q)= 59320, L(q,p)= 59320 p=137, q=449, g= 13566, L(p,q)= 61512, L(q,p)= 61512 p=137, q=457, g= 20069, L(p,q)= 62608, L(q,p)= 62608 p=137, q=521, g= 47810, L(p,q)= 71376, L(q,p)= 71376 p=137, q=569, g= 48721, L(p,q)= 77952, L(q,p)= 77952 p=137, q=577, g= 2806, L(p,q)= 79048, L(q,p)= 59464 p=137, q=593, g= 27433, L(p,q)= 81240, L(q,p)= 61112 p=137, q=601, g= 38768, L(p,q)= 82036, L(q,p)= 61636 p=137, q=617, g= 12930, L(p,q)= 84528, L(q,p)= 42640 p=137, q=641, g= 31718, L(p,q)= 87816, L(q,p)= 87816 p=137, q=673, g= 56250, L(p,q)= 92200, L(q,p)= 92200 p=137, q=761, g=102482, L(p,q)=104256, L(q,p)=104256 p=137, q=769, g= 75070, L(p,q)=105352, L(q,p)=105352 p=137, q=809, g= 73213, L(p,q)=110832, L(q,p)=110832 p=137, q=857, g= 37193, L(p,q)=117408, L(q,p)=117408 p=137, q=881, g= 11598, L(p,q)=120256, L(q,p)= 60416 p=137, q=929, g= 90609, L(p,q)=127272, L(q,p)=127272 p=137, q=937, g= 46626, L(p,q)=127900, L(q,p)= 64252 p=137, q=977, g= 87996, L(p,q)=133848, L(q,p)=133848 p=193, q=233, g= 16668, L(p,q)= 44852, L(q,p)= 33716 p=193, q=281, g= 17392, L(p,q)= 54232, L(q,p)= 40792 p=193, q=521, g= 85662, L(p,q)=100552, L(q,p)=100552 p=193, q=569, g= 35239, L(p,q)=109816, L(q,p)=109816 p=193, q=617, g= 41312, L(p,q)=119080, L(q,p)= 89512 p=193, q=761, g= 31538, L(p,q)=146872, L(q,p)=146872 p=193, q=809, g= 94517, L(p,q)=156136, L(q,p)=156136 p=193, q=857, g= 14745, L(p,q)=165400, L(q,p)=165400 p=193, q=953, g=155661, L(p,q)=183928, L(q,p)=183928 p=233, q=241, g= 42911, L(p,q)= 56036, L(q,p)= 56036 p=233, q=257, g= 29082, L(p,q)= 29940, L(q,p)= 29940 p=233, q=281, g= 34885, L(p,q)= 32876, L(q,p)= 65356 p=233, q=313, g= 58643, L(p,q)= 54716, L(q,p)= 72812 p=233, q=337, g= 14872, L(p,q)= 39260, L(q,p)= 39260 p=233, q=353, g= 23040, L(p,q)= 41300, L(q,p)= 82132 p=233, q=401, g= 62322, L(p,q)= 70116, L(q,p)= 93316 p=233, q=409, g= 12442, L(p,q)= 71516, L(q,p)= 95180 p=233, q=433, g= 26940, L(p,q)= 50660, L(q,p)=100772 p=233, q=449, g= 83324, L(p,q)= 78516, L(q,p)=104500 p=233, q=457, g= 11927, L(p,q)=106364, L(q,p)=106364 p=233, q=521, g=108794, L(p,q)= 60956, L(q,p)=121276 p=233, q=569, g=123713, L(p,q)= 99516, L(q,p)=132460 p=233, q=577, g= 29038, L(p,q)= 67508, L(q,p)=134324 p=233, q=593, g= 54123, L(p,q)= 69380, L(q,p)=138052 p=233, q=601, g= 13591, L(p,q)= 70016, L(q,p)= 70016 p=233, q=617, g= 92972, L(p,q)= 72188, L(q,p)=143644 p=233, q=641, g= 3966, L(p,q)= 74996, L(q,p)=149236 p=233, q=673, g= 40349, L(p,q)=156692, L(q,p)=156692 p=233, q=761, g= 55465, L(p,q)= 89036, L(q,p)=177196 p=233, q=769, g= 8232, L(p,q)=134516, L(q,p)=179060 p=233, q=809, g= 85079, L(p,q)=188380, L(q,p)=188380 p=233, q=857, g= 58037, L(p,q)=149916, L(q,p)=199564 p=233, q=881, g=128989, L(p,q)=102636, L(q,p)=102636 p=233, q=937, g=108030, L(p,q)=109160, L(q,p)=109160 p=233, q=953, g=109121, L(p,q)=166716, L(q,p)=221932 p=233, q=977, g= 8739, L(p,q)=170916, L(q,p)=227524 p=241, q=569, g= 57909, L(p,q)=137128, L(q,p)=137128 p=241, q=617, g=125934, L(p,q)=148696, L(q,p)=148696 p=241, q=809, g= 42650, L(p,q)=194968, L(q,p)=194968 p=241, q=857, g=121627, L(p,q)=206536, L(q,p)=206536 p=241, q=953, g=206423, L(p,q)=229672, L(q,p)=229672 p=257, q=281, g= 41944, L(p,q)= 36248, L(q,p)= 72088 p=257, q=313, g= 42588, L(p,q)= 60344, L(q,p)= 80312 p=257, q=409, g= 38543, L(p,q)= 78872, L(q,p)=104984 p=257, q=457, g= 86462, L(p,q)= 58952, L(q,p)=117320 p=257, q=521, g= 37728, L(p,q)=100488, L(q,p)=133768 p=257, q=569, g= 34746, L(p,q)=109752, L(q,p)=146104 p=257, q=601, g=112076, L(p,q)= 77228, L(q,p)= 77228 p=257, q=617, g= 59924, L(p,q)= 79592, L(q,p)=158440 p=257, q=761, g= 43074, L(p,q)=146808, L(q,p)=195448 p=257, q=809, g= 93680, L(p,q)=156072, L(q,p)=207784 p=257, q=857, g=190617, L(p,q)=165336, L(q,p)=220120 p=257, q=937, g= 88866, L(p,q)=120404, L(q,p)=120404 p=257, q=953, g=119285, L(p,q)=183864, L(q,p)=244792 p=281, q=313, g= 52162, L(p,q)= 44272, L(q,p)= 87952 p=281, q=353, g= 19938, L(p,q)= 99192, L(q,p)= 99192 p=281, q=409, g= 10040, L(p,q)= 57808, L(q,p)=114928 p=281, q=433, g= 4290, L(p,q)= 91432, L(q,p)=121672 p=281, q=457, g= 98725, L(p,q)= 96496, L(q,p)=128416 p=281, q=569, g= 48092, L(p,q)=159888, L(q,p)=159888 p=281, q=577, g= 75945, L(p,q)=162136, L(q,p)=162136 p=281, q=593, g= 42607, L(p,q)=166632, L(q,p)=166632 p=281, q=769, g=150305, L(p,q)=162328, L(q,p)=216088 p=281, q=809, g=108642, L(p,q)=227328, L(q,p)=227328 p=281, q=857, g=156049, L(p,q)=120976, L(q,p)=240816 p=281, q=929, g=180212, L(p,q)=131128, L(q,p)=261048 p=281, q=937, g= 3285, L(p,q)=262828, L(q,p)=131788