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 - qr1) % p;
s = (s0 - qs1) % 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 = (tt) % 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.