Exponentiation mod n - comments on the logic

In my previous post I presented some logic for obtaining the remainder when a number like 67¹¹ is divided by 41. I now want to go through how this logic works.

We are interested in dividing 67¹¹ by 41 and these positive integers are input and stored in X, A and B in the 2nd, 3rd and 4th lines of the logic. The first 'while' loop determines the remainder on dividing 67 by 41 and the result, 26, is stored in X. Essentially, 67 is reduced by 41 on each iteration until X is less than 41. A copy of this remainder (26) is kept in Y.

Memory C holds the current 'squared power'. Memory D is used to store the required calculated remainder and is initialised with 1.

If the input power (stored in A) was 1 rather than 11, then there is no more work to do, so we jump to label 2 and display the result.

The main process of calculating the required remainder by repeated squaring begins after label 1. In our example X currently contains 26 (the remainder on dividing 67 by 41). We square this and then the next 'while' loop obtains the remainder (20) on division by 41 and stores it in X. C is then doubled to 4 and as this is less than 11 we jump back to label 1. We keep on repeating this squaring until C reaches 16. As 16 is greater than 11 we determine that 67 has currently been raised to the power 8 (C divided by 2). We subtract 8 from 11 and store this 'residual' power (3) in A. The calculated remainder 'so far' (18 held in X) is multiplied with D (1) and the result stored in D. We store 26 back in X and set the 'squared power' in C back to 2. As 2 is less than the residual power 3 we begin again by going back to label 1.

Eventually the 'residual power' ends up being 1 in A and we have to take the contents of D and multiply this once more by 26 to get the remainder of 26¹¹ on division by 41. Note that if the power of 67 was even rather than odd, this last step isn't required.

The required remainder is in memory D and this is displayed. There is an option to return to the start of the logic again to enter a different set of numbers.