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

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 - q*r1) % 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 = (res*t) % p;}
exp = exp / 2;
t = (t*t) % p;

}

return res;

];[/code]

What is it for? I’m curious

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

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 ). 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.

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

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

Thanks.

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]”;

otherwise:

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 “http://www.di-mgt.com.au/euclidean.html”

! 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;

];

-).

[/code]

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

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.