daily pastebin goal
75%
SHARE
TWEET

Untitled

a guest Dec 11th, 2017 44 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. def egcd(a,b):
  2.     # Extended Euclidean Algorithm
  3.     # returns x, y, gcd(a,b) such that ax + by = gcd(a,b)
  4.     u, u1 = 1, 0
  5.     v, v1 = 0, 1
  6.     while b:
  7.         q = a // b
  8.         u, u1 = u1, u - q * u1
  9.         v, v1 = v1, v - q * v1
  10.         a, b = b, a - q * b
  11.     return u, v, a
  12.  
  13. def modInverse(e,n):
  14.     # d such that de = 1 (mod n)
  15.     # e must be coprime to n
  16.     # this is assumed to be true
  17.     return egcd(e,n)[0]%n
RAW Paste Data
Top