Contact
CoCalc Logo Icon
StoreFeaturesDocsShareSupport News Sign UpSign In
| Download

Linear Complexity for DH-GCS_8

Project: DH8
Views: 67
############# The linear complexity LC(p,q,g) of DH-GCS_d 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() ############# The result L(p,q) in Theorem 2 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 ############# Check whether LC(p,q,g)=L(p,q) for p,q <= D 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= 539, L(p,q)= 696, L(q,p)= 696 p= 17, q= 73, g= 1201, L(p,q)= 1204, L(q,p)= 916 p= 17, q= 89, g= 972, L(p,q)= 1468, L(q,p)= 764 p= 17, q=137, g= 482, L(p,q)= 2328, L(q,p)= 2328 p= 17, q=233, g= 726, L(p,q)= 3844, L(q,p)= 2916 p= 17, q=281, g= 2115, L(p,q)= 4776, L(q,p)= 2536 p= 17, q=313, g= 1125, L(p,q)= 5320, L(q,p)= 5320 p= 17, q=409, g= 6059, L(p,q)= 6952, L(q,p)= 6952 p= 17, q=457, g= 1516, L(p,q)= 7768, L(q,p)= 7768 p= 41, q= 73, g= 1182, L(p,q)= 2956, L(q,p)= 2956 p= 41, q= 89, g= 1910, L(p,q)= 3604, L(q,p)= 2724 p= 41, q= 97, g= 3127, L(p,q)= 3976, L(q,p)= 3976 p= 41, q=113, g= 89, L(p,q)= 4632, L(q,p)= 4632 p= 41, q=137, g= 1912, L(p,q)= 5616, L(q,p)= 5616 p= 41, q=193, g= 3511, L(p,q)= 7912, L(q,p)= 7912 p= 41, q=233, g= 4406, L(p,q)= 9436, L(q,p)= 7116 p= 41, q=257, g= 4163, L(p,q)= 10408, L(q,p)= 7848 p= 41, q=313, g= 8890, L(p,q)= 12832, L(q,p)= 12832 p= 41, q=337, g= 8752, L(p,q)= 13648, L(q,p)= 13648 p= 41, q=353, g= 9583, L(p,q)= 14472, L(q,p)= 14472 p= 41, q=409, g= 10790, L(p,q)= 16768, L(q,p)= 16768 p= 41, q=433, g= 12985, L(p,q)= 17752, L(q,p)= 17752 p= 41, q=449, g= 12885, L(p,q)= 18408, L(q,p)= 18408 p= 41, q=457, g= 8024, L(p,q)= 18736, L(q,p)= 18736 p= 73, q= 89, g= 5136, L(p,q)= 3248, L(q,p)= 3248 p= 73, q=113, g= 2842, L(p,q)= 4180, L(q,p)= 8212 p= 73, q=137, g= 7285, L(p,q)= 5068, L(q,p)= 9964 p= 73, q=233, g= 13609, L(p,q)= 8504, L(q,p)= 8504 p= 73, q=257, g= 7578, L(p,q)= 9380, L(q,p)= 9380 p= 73, q=281, g= 14047, L(p,q)= 10396, L(q,p)= 20476 p= 73, q=353, g= 4057, L(p,q)= 13060, L(q,p)= 25732 p= 73, q=401, g= 29186, L(p,q)= 29236, L(q,p)= 29236 p= 73, q=449, g= 15018, L(p,q)= 24676, L(q,p)= 32740 p= 89, q= 97, g= 3663, L(p,q)= 8588, L(q,p)= 8588 p= 89, q=113, g= 8040, L(p,q)= 5084, L(q,p)= 10012 p= 89, q=137, g= 6271, L(p,q)= 9156, L(q,p)= 12148 p= 89, q=193, g= 6557, L(p,q)= 12908, L(q,p)= 17132 p= 89, q=233, g= 273, L(p,q)= 10368, L(q,p)= 10368 p= 89, q=241, g= 20655, L(p,q)= 16124, L(q,p)= 21404 p= 89, q=257, g= 15400, L(p,q)= 11436, L(q,p)= 11436 p= 89, q=281, g= 24955, L(p,q)= 12644, L(q,p)= 24964 p= 89, q=313, g= 12117, L(p,q)= 20948, L(q,p)= 27812 p= 89, q=337, g= 12178, L(p,q)= 14996, L(q,p)= 14996 p= 89, q=401, g= 34217, L(p,q)= 35644, L(q,p)= 35644 p= 89, q=409, g= 3003, L(p,q)= 18404, L(q,p)= 36356 p= 89, q=433, g= 23701, L(p,q)= 28988, L(q,p)= 38492 p= 89, q=449, g= 8873, L(p,q)= 20204, L(q,p)= 39916 p= 89, q=457, g= 741, L(p,q)= 30596, L(q,p)= 40628 p= 97, q=137, g= 4084, L(p,q)= 13288, L(q,p)= 13288 p= 97, q=233, g= 985, L(p,q)= 22484, L(q,p)= 16916 p= 97, q=281, g= 1416, L(p,q)= 27256, L(q,p)= 20536 p=113, q=137, g= 4013, L(p,q)= 11672, L(q,p)= 15480 p=113, q=233, g= 12812, L(p,q)= 26212, L(q,p)= 13220 p=113, q=313, g= 24813, L(p,q)= 35368, L(q,p)= 35368 p=113, q=409, g= 44832, L(p,q)= 34792, L(q,p)= 46216 p=113, q=457, g= 11514, L(p,q)= 38872, L(q,p)= 51640 p=137, q=193, g= 1554, L(p,q)= 26440, L(q,p)= 26440 p=137, q=233, g= 19063, L(p,q)= 31804, L(q,p)= 23916 p=137, q=241, g= 13904, L(p,q)= 33016, L(q,p)= 33016 p=137, q=257, g= 14878, L(p,q)= 35080, L(q,p)= 35080 p=137, q=281, g= 35041, L(p,q)= 38496, L(q,p)= 19456 p=137, q=313, g= 41152, L(p,q)= 42880, L(q,p)= 42880 p=137, q=337, g= 24777, L(p,q)= 46000, L(q,p)= 23152 p=137, q=353, g= 36026, L(p,q)= 48360, L(q,p)= 36392 p=137, q=401, g= 17050, L(p,q)= 54936, L(q,p)= 54936 p=137, q=433, g= 28443, L(p,q)= 59320, L(q,p)= 59320 p=137, q=449, g= 30456, L(p,q)= 61512, L(q,p)= 61512 p=137, q=457, g= 3122, L(p,q)= 62608, L(q,p)= 62608 p=193, q=233, g= 39773, L(p,q)= 44852, L(q,p)= 33716 p=193, q=281, g= 25867, L(p,q)= 54232, L(q,p)= 40792 p=233, q=241, g= 36625, L(p,q)= 56036, L(q,p)= 56036 p=233, q=257, g= 33639, L(p,q)= 29940, L(q,p)= 29940 p=233, q=281, g= 23297, L(p,q)= 32876, L(q,p)= 65356 p=233, q=313, g= 44409, L(p,q)= 54716, L(q,p)= 72812 p=233, q=337, g= 2890, L(p,q)= 39260, L(q,p)= 39260 p=233, q=353, g= 77436, L(p,q)= 41300, L(q,p)= 82132 p=233, q=401, g= 68941, L(p,q)= 70116, L(q,p)= 93316 p=233, q=409, g= 11958, L(p,q)= 71516, L(q,p)= 95180 p=233, q=433, g= 772, L(p,q)= 50660, L(q,p)=100772 p=233, q=449, g= 10653, L(p,q)= 78516, L(q,p)=104500 p=233, q=457, g= 28969, L(p,q)=106364, L(q,p)=106364 p=257, q=281, g= 50591, L(p,q)= 36248, L(q,p)= 72088 p=257, q=313, g= 17398, L(p,q)= 60344, L(q,p)= 80312 p=257, q=409, g= 42665, L(p,q)= 78872, L(q,p)=104984 p=257, q=457, g=112004, L(p,q)= 58952, L(q,p)=117320 p=281, q=313, g= 54209, L(p,q)= 44272, L(q,p)= 87952 p=281, q=353, g= 47299, L(p,q)= 99192, L(q,p)= 99192 p=281, q=409, g= 28913, L(p,q)= 57808, L(q,p)=114928 p=281, q=433, g= 57345, L(p,q)= 91432, L(q,p)=121672 p=281, q=457, g= 24899, L(p,q)= 96496, L(q,p)=128416 p=313, q=353, g= 77807, L(p,q)=110488, L(q,p)= 83032 p=313, q=401, g=107318, L(p,q)=125512, L(q,p)=125512 p=313, q=449, g= 22376, L(p,q)=140536, L(q,p)=140536 p=353, q=409, g= 93846, L(p,q)=108472, L(q,p)=144376 p=353, q=457, g= 30139, L(p,q)=121192, L(q,p)=161320 p=401, q=409, g= 3235, L(p,q)=164008, L(q,p)=164008 p=401, q=457, g=132728, L(p,q)=183256, L(q,p)=183256 p=409, q=449, g= 55244, L(p,q)=183640, L(q,p)=183640 p=449, q=457, g=127856, L(p,q)=205192, L(q,p)=205192