Contact
CoCalc Logo Icon
StoreFeaturesDocsShareSupport News AboutSign UpSign In
| Download

Cocalc tutorial sheet

Views: 43
Kernel: SageMath (Development)
#Greatest Common Divisor g = gcd(252, 105); print g gcd(252,105) == gcd(147, 105) == gcd(42, 105) == gcd(42, 63) == gcd(42, 21) == gcd(21,21) == gcd(21,0) == 21
21
True
#Extended Euclid's Algorithm a = 252; b = 105; g,alpha,beta = xgcd(a,b); print 'gcd('+str(a)+', '+str(b)+') = ' + str(g) + ' = ' + str(a)+'*'+str(alpha) +' + '+ str(b)+'*'+str(beta)
gcd(252, 105) = 21 = 252*-2 + 105*5
#Modular Inverses Z13 = IntegerModRing(13); print list(Z13) Z13star = [x for x in Z13 if gcd(13, x)==1]; print Z13star euler_phi(13)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12] [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
12
#Modular Inverses (non prime) -- this is one reason why we like prime numbers Z15 = IntegerModRing(15); print list(Z15); Z15star = [x for x in Z15 if gcd(15, x)==1]; print Z15star; euler_phi(15)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14] [1, 2, 4, 7, 8, 11, 13, 14]
8
#e.g. Specific Modular Inverse: 7^-1 mod 13 a = 7 b = 13 invexists = gcd(a,b); invexists #This true if inv 7 exists g,alpha,beta = xgcd(7,13); print 'gcd('+str(a)+', '+str(b)+') = ' + str(g) + ' = ' + str(a)+'*'+str(alpha) +' + '+ str(b)+'*'+str(beta); inv7 = mod(alpha, 13); print 'The inverse of 7 mod 13 is ' + str(inv7)
gcd(7, 13) = 1 = 7*2 + 13*-1 The inverse of 7 mod 13 is 2
#RSA example P = Primes(); p = P.unrank(ZZ.random_element(0,15)); q = p; while(p==q): # Make sure p!=q q = P.unrank(ZZ.random_element(0,15)); print 'p = ' + str(p) + ', q = ' +str(q) #N = p*q N = p*q; print 'N = ' + str(N); #phi(N) = (p-1)*(q-1) phiN = euler_phi(N); print 'phiN = ' + str(phiN) #Choose an integer e such that 1 < e < λ(n) and gcd(e, λ(n)) = 1; i.e., e and λ(n) are coprime. ZphiNstar = [x for x in IntegerModRing(N) if gcd(N, x)==1] loop = True while (loop): e = int(choice(ZphiNstar)); if e > 1 and e < phiN and gcd(e,phiN) == 1: loop = False print 'public key e = ' + str(e) # compute private key d g,alpha,beta = xgcd(e,phiN); print alpha d = mod(alpha, phiN); print 'private key d = ' + str(d)
p = 7, q = 2 N = 14 phiN = 6 public key e = 5 -1 private key d = 5
# Encrypt M = 12; C = mod(M^e, N); print C
331
# Decrypt M = mod(C^d, N); print M
12