Tuesday 22 April 2014

Exponentiation mod n - the logic

In a previous post I discussed how it is possible to use modular arithmetic to obtain information about the divisibility of a large number like 6711. I showed that the problem of whether 41 divides this number can be reduced to a sequence of manageable chunks by using the method of repeated squaring modulo 41. I now give an example of the logic that can be used to solve this problem on a programmable calculator.

Label 0
Input X (67 in our example)
Input A (11 in our example)
Input B (41 in our example)
While X ≥ B
   Store X-B in X
WhileEnd
Store X in Y
Store 2 in C
Store 1 in D
If C>A then
   Store X in D
   Goto Label 2
EndIf
Label 1
Store X2 in X
While X ≥ B
   Store X-B in X
WhileEnd
Store 2C in C
If C ≤A then
  Goto Label 1
EndIf
Store C/2 in C
Store A-C in A
Store DX in D
While D ≥ B
   Store D-B in D
WhileEnd
Store Y in X
Store 2 in C
If C ≤A then
   Goto Label 1
EndIf
If A=1 then
   Store DY in D
EndIf
While D ≥ B
   Store D-B in D
WhileEnd
Label 2
Display D
Goto Label 0

No comments:

Post a Comment