Inform6: Routine for Modular Multiplicative Inverse

Does anyone have a code snippet to demonstrate the coding to calculate the Modular Multiplicative Inverse?
I’m not too particular about the method used, but speed is always a nice thing to have :smiley:

Haven’t tested it at all (not much time today - sorry!), but this should do. The first one (extended GCD) is faster, I believe, though you might not see much difference for small inputs.

[code]! Call : InvMod(a,p)
[ InvMod a p r0 s0 t0 r1 s1 t1 q r s t
r0 = p; s0 = 1; t0 = 0;
r1 = a % p; s1 = 0; t1 = 1;

! Extended GCD
! Loop invariant : s a + t p = r
! when the while is false, you get s0a+t0p = 1
while (r1 ~=0) {
q = r0 / r1 ;
r = (r0 - qr1) % p;
s = (s0 - q
s1) % p;
t = (t0 - q*t1) % p;

r0 = r1; s0 = s1; t0 = t1;
r1 = r; s1 = s; t1 = t;

return s0;

! If p is prime, you can also use this
[ InvMod a p res exp t
! Uses a^{-1} = a^{p-2}
res = 1;
exp = p - 2;
t = a % p;
while (exp ~= 0) {
if (exp % 2 == 1) { res = (rest) % p;}
exp = exp / 2;
t = (t
t) % p;
return res;

What is it for? I’m curious :slight_smile:
EDIT: from other messages, I see my intuition was right: you’re doing RSA-style stuff for a crypto-related game? That’s awesome :smiley: Feel free to send me an email if you have questions or if you want a beta-test, since crypto’s actually my job… :wink:

THANK YOU SO MUCH for the code. I was considering writing myself, but I’ve got a lot on my plate with other aspects of the adventure.

Actually; it is for a crypto-related adventure. That was a good guess. I’m doing real-time “layered” enciphering that is keyed to the player, such that players can’t collaborate to solve it. Everyone gets quite different cipher-text. I love writing these sort of puzzles and throwing in a few very devious twists for fun (and I do have a very special twist in mind for this one :smiling_imp: ). It gets people thinking for themselves and not relying on online decryption programs …

I’ll be sure to keep you in mind for testing, but it will take a bit before the adventure is fully written. It’s being done in Vorple with some Java and some Inform6 extensions. AND … I’m “pulling out all the stops” to show that adventures are now much more than just Go N, E, W and S. :smiley:

No problem! Let me know if it worked! (Use (InvMod(a,p) * a) % p == 1 :wink:)

Your project sounds cool! Don’t hesitate to keep me in the loop or ask for testing; my email is on my website below.


Will check out your website.
I can see by your response that you also read minds!
Will contact you soon.

I appreciate the previous examples and thought that I’d try to see if I could write my own version in Inform6 based on a paper by Knuth [KNU298, Vol 2 Algorithm X p 342].

Here is my version of a routine to calculate the Modular Multiplicative Inverse. It seems to work well enough. Please jump in if there’s a better way to do it.

[code]“Modular Multiplicative Inverse” by Gary

The Crypto Crypt is a room.

Par1 is a number that varies.
Par2 is a number that varies.
MMI is a Number that varies.

[Create a new command to ‘Test’ the MMI.]
Testing the MMI is an action out of world.

Understand “MMI” as Testing the MMI.

Carry out Testing the MMI (this is the Carry out Testing the MMI rule):
say “[line break]This is a quick test of calculating the Modular Multiplicative Inverse.[line break]”;
Check invalid relative primes;
Check valid relative primes.

When play begins:
now the command prompt is "Type ‘MMI’ to test calculating the ‘Modular Multiplicative Inverse’. > ".

To check invalid relative primes:
[The following parameters are not relatively prime.]
Now Par1 is 24;
Now Par2 is 138;
Now MMI is Modular Multiplicative Inverse of Par1 and Par2;
Say the Modular Multiplicative Inverse of Par1 and Par2 is MMI;

To check valid relative primes:
[The following parameters are relatively prime.]
Now Par1 is 37;
Now Par2 is 216;
Now MMI is Modular Multiplicative Inverse of Par1 and Par2;
Say the Modular Multiplicative Inverse of Par1 and Par2 is MMI.

To say the Modular Multiplicative Inverse of (u - a number) and (v - a number) is (inv - a number):
if inv is zero:
say “[line break][bold type]ERROR: The parameters of GCD([u], [v]) are not relatively prime.[roman type][line break]”;
say “Please try different parameters.[paragraph break]”;
say “The ‘Modular Multiplicative Inverse’ of GCD([u], [v]) is [inv].[paragraph break]”.

To decide which number is Modular Multiplicative Inverse of (u - a number) and (v - a number):
(- (ModMultInv({u},{v})) -).

Include (-
[ModMultInv u v inv u1 u3 v1 v3 t1 t3 q iter;
! Computing the modular inverse from “

! This code is an adaptation of the extended Euclidean algorithm from Knuth [KNU298, Vol 2 Algorithm X p 342] avoiding negative integers. It computes the multiplicative inverse of u modulo v, u-1 (mod v), and returns either the inverse as a positive integer less than v, or zero if no inverse exists.

! Step 1: Initialise
u1 = 1;
u3 = u;
v1 = 0;
v3 = v;

! Remember odd/even iterations
iter = 1;

! Step 2: Loop while v3 != 0
while (v3 ~= 0) {
! Step 3: Divide and “Subtract”
q = u3 / v3;
t3 = u3 % v3;
t1 = u1 + q * v1;
! Swap
u1 = v1; v1 = t1; u3 = v3; v3 = t3;
iter = -iter;

! Make sure u3 = gcd(u,v) == 1
if (u3 ~= 1) { return 0; } ! Error: No inverse exists

! Ensure a positive result */
if (iter < 0) { inv = v - u1; } else { inv = u1; }

! Return the Multiplicative Inverse
return inv;

Yup, that will work too - that’s basically a variant of the first algorithm I used, modified to only get the “s” variable (the one we want). I reckon it’s faster than my code. Knuth’s book has all sorts of great algorithms :slight_smile:

Is there a good source for purchasing Knuth’s book?
I love finding books of computer algorithms. They are usually money well-spent.
I have a couple I use for engineering programs and they never seem to go out of date.