|20-CS-472||Design and Analysis of Algorithms 2||Winter 2011|
|Inverse Modulo a Number|
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*nwhose 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: