Project 6, 2015 Research Experience for Teachers Project 4, 2016
Inverse of m Modulo n
Secret Key, Public Key, Hash Algorithms, Protocols, Authentication, Integrity, Confidentiality, Availability

 

Operation:
    Enter a number m and a number n in the boxes at the top left. Click on Start to begin the gcd algorithm for finding the inverse of m mod n. Repeated clicks on the Next button will update an equation 
                    R = U*m + V*n
whose values are shown on the bottom line of the applet in separate boxes. When an inverse is found, if it exists, it will appear in the box labeled inv:. One click later, the check field will verify this by showing a 1. If an inverse does not exist, "None" will appear in the inv: box.

Further details:
    Boxes larger and smaller contain the two numbers that the algorithm is currently trying to find the greatest common divisor for. Initially these numbers are m and n. The box labeled divisor shows the number of times the smaller number divides the larger number, and the box labeled remainder shows the remainder of that division. There are two rows of three columns that record numbers which are used to compute new factors. Initially these are:
  • left column - 1 and -1 times the divisor.
  • middle column - 0 and 1
  • right column - blank
On each click of Next the contents of a column moves to the next column to its right or disappears in the case of the right column. Also, a new left column is computed from the new divisor and column values as shown in the labels of the two rows. The number in the first row, left column becomes the U and the number in the second row, left column becomes the V.