Modular Multiplicative Inverse

We're glad you came by, but you might find what you're looking for elsewhere. TI-Basic Developer is not the site it once was. While its information on commands and other calculator features remains almost second-to-none, its forum, archives, and even hosting service, Wikidot, have been decaying for years. The calculator community would love to see what you're working on, or help you in your next coding adventure, but TI-Basic Developer is no longer the place to do it. Instead, you should head over to Cemetech (primarily American) or TI-Planet (primarily international). Both are active, well-established forums with their own archives, chatrooms, reference material, and abundant coding tools and resources. We'll see you there, we hope.

Forum Attachments

Modular Multiplicative Inverse

calccrypto 07 Dec 2008 21:59

does anyone know what in the world this is? i know the wikipedia page explains it, but im not too sure. i understand that the basic idea is gcd(A,B) has to be 1, but then what?

and for the RSA algorithm, does d also have to be prime?

---

Visit Calccrypto for info on crypto
KC2ZOF

Re: Modular Multiplicative Inverse

simplethinker 07 Dec 2008 23:41

Finding the multiplicative inverse means finding a C such that Aֿ¹ ≡ C (mod B), or AC ≡ 1 (mod B). The condition gcd(A,B) just means that that A and B have to be relatively prime and is the condition necessary for existence and uniqueness of an inverse.

Here's the multiplication table for modulo 5:

	0	1	2	3	4
0	0	0	0	0	0
1	0	1	2	3	4
2	0	2	4	1	3
3	0	3	1	4	2
4	0	4	3	2	1

As you can see (except for the 0 columns/rows) each number appears only once in each row/column, so there exists a unique multiplicative inverse for each. For example 2*C ≡ 1 (mod 5) has the unique solution C=3

For modulo 4:

	0	1	2	3
0	0	0	0	0
1	0	1	2	3
2	0	2	0	2
3	0	3	2	1

If you look at row/column 2 (the only number not relatively prime to 4), you see numbers are repeated, and some don't even appear in them. 2*C≡2 (mod 4) has two possible solutions, and 2*C≡1 (mod 4) doesn't even have one solution!

Last edited on 07 Dec 2008 23:55 by simplethinker Show more

Re: Modular Multiplicative Inverse

calccrypto 07 Dec 2008 23:55

oh… i think i sort of get it.

---

Visit Calccrypto for info on crypto
KC2ZOF

Re: Modular Multiplicative Inverse

simplethinker 08 Dec 2008 00:26

Here's another explanation why division isn't always possible for composite moduli (from "Concepts of Modern Mathematics" by Ian Stewart):

Suppose the modulus is m where m=a×b and each of a and b is smaller than m. Then neither a nor b is congruent to 0 (mod m), but their product a×b is m, which is congruent to 0.

(they can't be congruent to 0 (mod m) since neither of them is 0 because that would mean m is zero, and they're less than m)

Hope this helps :)

Re: Modular Multiplicative Inverse

calccrypto 08 Dec 2008 01:06

yeah. it does help a lot actually

---

Visit Calccrypto for info on crypto
KC2ZOF

Re: Modular Multiplicative Inverse

calccrypto 08 Dec 2008 17:14

now… how can this be applied on a program that will need to find the number and use it as a power?

{11,12,13}^B(some big number)

the 84 cant handle can it?

---

Visit Calccrypto for info on crypto
KC2ZOF

Re: Modular Multiplicative Inverse

Socks 08 Dec 2008 22:15

The 84 wouldn't be able to. I just tried that list to the 90th, and it got an overflow error.

But the math itself is fine.

---

/Socks

Re: Modular Multiplicative Inverse

calccrypto 09 Dec 2008 01:04

aww…. i got a perfectly working RSA encryption on the 84. its just too powerful for it.

now what?

---

Visit Calccrypto for info on crypto
KC2ZOF

Re: Modular Multiplicative Inverse

Socks 09 Dec 2008 01:08

Use smaller numbers, I guess. Less secure, but what can we say? Once you have it on the internet the algorithm is there for all to see.

---

/Socks

Re: Modular Multiplicative Inverse

calccrypto 09 Dec 2008 01:13

how small?

---

Visit Calccrypto for info on crypto
KC2ZOF

Re: Modular Multiplicative Inverse

simplethinker 09 Dec 2008 02:36

Remember that you're using modular exponentiation, not regular exponentiation.

Re: Modular Multiplicative Inverse

Socks 09 Dec 2008 17:22

The largest it can be withour throwing an error. Less than 90, for sure.

---

/Socks

Re: Modular Multiplicative Inverse

Edward H 21 Jan 2009 02:03

Here's a routine for modular exponentiation:

E is the exponent, B is the base, M is the modulus, and R is the answer.

1→R
While E
If fPart(.5E
BR-Mint(BR/M→R
int(.5E→E
B²-Mint(B²/M→B
End
R

I originally wrote it for a code challenge on UTI, and I got the algorithm from Wikipedia. This works for modulus and base up to 10^7, I think.

A Modular Inverse Program

thornahawk 06 Feb 2009 10:16

Ah Ed H., the good ol' Russian peasant algorithm… :D

I am rather surprised no one has put up code for the modular inverse. :P

PROGRAM:MODINV
1→V:A→D
A=1→U
not(U)→T
If T:Then
int(M/A)→U
M–AU→C
While C≠1 and T
int(D/C)→Q
D–CQ→D
V+QU→V
D≠1→T
If T:Then
int(C/D)→Q
C–DQ→C
U+QV→U
End:End
Vnot(T)+T(M–U)→U
End
U

The inverse of A modulo M is stored in U.

3→A:7→M:prgmMODINV

gives 5, as expected.

A divide-by-zero error will occur if and only if there exists no modular inverse for A for the chosen modulus M.

This is an ingenious modification of the extended Euclidean algorithm (extended GCD), adapted for computing the modular inverse. I do not have my number theory books at hand so I cannot say where I got this program.

It shouldn't take much trouble for somebody determined enough to write a mongrel program that uses both the Russian peasant algorithm and extended GCD to compute things like 3ֿ³ (mod 13) (hint: take the inverse first before powering).

thornahawk

P.S. Modular roots are an even harder problem… :)

Last edited on 06 Feb 2009 10:17 by thornahawk Show more

Re: Modular Multiplicative Inverse

Mapar007 09 Dec 2008 19:05

That book RULEZ! (Couldn't withhold myself to say it :D )

Edit: I mean Ian Stewart's "Concepts" of course.

Last edited on 09 Dec 2008 19:06 by Mapar007 Show more

Re: Modular Multiplicative Inverse

simplethinker 21 Jan 2009 02:27

I agree, it's a great book! Sometimes simple, intuitive explanations work a whole lot better than a profusion of mathematical symbols (in particular with regards to topology)

Last edited on 21 Jan 2009 02:28 by simplethinker Show more

TreeStump (guest) 07 Sep 2015 08:53

Hi.

I know I'm bumping an extremely old thread but I would like to install thornahawk's modular inverse program on my Casio classpad 330. If anyone could provide instructions or link me to an updated mod inv program that would be great.

Thanks.