210 http://inventwithpython.com/hacking

Email questions to the author: [email protected]

The // Integer Division Operator

You may have noticed the // operator used in the findModInverse() function above. This
is the integer division operator. It divides two numbers and rounds down. Try typing the
following into the interactive shell:

41 // 7
5
41 / 7
5.857142857142857
10 // 5
2
10 / 5
2.0

Notice that an expression with the // integer division operator always evaluates to an int, not a
float.

Source Code of the cryptomath Module

The gcd() and findModInverse() functions will be used by more than one of our cipher
programs later in this book, so we should put this code into a separate module. In the file editor,
type in the following code and save it as cryptomath.py:

Source code for cryptomath.py

1. 
   

   Cryptomath Module

   
   


2. 
   

   http://inventwithpython.com/hacking (BSD Licensed)

   
   


3. 
   


4. def gcd(a, b):


5. 
   

   Return the GCD of a and b using Euclid's Algorithm

   
   


6. while a != 0:


7. a, b = b % a, a


8. return b


9. 
   


10. 
    


11. def findModInverse(a, m):


12. 
    

    Returns the modular inverse of a % m, which is

    
    


13. 
    

    the number x such that a*x % m = 1

    
    


14. 
    


15. if gcd(a, m) != 1:


16. return None # no mod inverse if a & m aren't relatively prime


17. 
    


18. 
    

    Calculate using the Extended Euclidean Algorithm: