Home › Forums › Get Help › How do I ...? with Maple

How do I find the Inverse of a mod?

Posted on 2007-12-29 17:54 By Chris Roung (Maple Rating 2 111)
Categories:

How do I find the inverse of a mod? eg. the inverse of 7mod27 is 4. How do I get maple to find that? Is there a simple function?

‹ Separable ODE substituting new functions ›
roman_pearce's picture

1/7 mod 27;

Comment on 2007-12-29 18:26 from roman_pearce (Maple Rating 4 508) 
1/7 mod 27;

Great! What about inverse mod in excel?

Comment on 2007-12-30 20:36 from Chris Roung (Maple Rating 2 111)

Well I didn't think it was that simple. Thanks!

I'm trying to do the inverse MOD in excel, anyone know how to do that?

Robert Israel's picture

In excel

Comment on 2007-12-31 03:44 from Robert Israel (Maple Rating 4 1555)

To find the inverse of x mod y, where x is in cell A1 and y in A2:

=Maple("1/&1 mod &2",A1,A2)

Doesn't work

Comment on 2007-12-31 21:20 from Chris Roung (Maple Rating 2 111)

Are you calling on Maple to perform the inverse mod function from excel? That's what it looks like. That formula doesn't work for me, at all. How do you get excel to call on Maple?

I want excel to perform an inverse mod all by itself. Can it be done?

Robert Israel's picture

Maple from Excel

Comment on 2007-12-31 22:32 from Robert Israel (Maple Rating 4 1555)

I don't know how to get Excel to do it by itself: MaplePrimes is a site for Maple, not for Excel. For instructions on how to use Maple as an add-in to Excel, allowing Excel to access Maple commands, see the (Maple) help page ?Excel.

maple / excel

Comment on 2008-01-01 11:46 from Chris Roung (Maple Rating 2 111)

Yes I got maple to work from excel by using the maple add-in. Thanks

I realize this is a maple forum, but I thought maybe everyone here having used excel at one time or another, and being mathematically inclined, might have found a way to get the inverse mod in excel without using the maple kernel.

Not everyone has maple and excel is pretty much installed on every computer. Is there a way to do it?

roman_pearce's picture

Implement EEA

Comment on 2008-01-02 01:41 from roman_pearce (Maple Rating 4 508)

Implement the extended Euclidean algorithm. Here is a version in C:

/* inverse of A mod p */
long modinv(long A, long p)
{
        long a, b, q, t, x, y;
        a = p;
        b = A;
        x = 1;
        y = 0;
        while (b != 0) {
                t = b;
                q = a/t;
                b = a - q*t;
                a = t;
                t = x;
                x = y - q*t;
                y = t;
        }
        return (y < 0) ? y+p : y;
}

Note that long is typically a 32 bit signed integer, division (q = a/t) is truncating, and the last line returns y if y is greater than or equal to zero or y+p otherwise. The result is the inverse of A mod p. I don't know anything about Excel, so you're on your own from here.

Thanks - formula found!

Comment on 2008-01-02 08:12 from Chris Roung (Maple Rating 2 111)

Thanks for everyone's input. I recieved a reply on the excel forums and thought I would share it with everyone here.

In Excel if you want the inverse of MOD(7,23) and if A1 contains 23 and B1 7 then use this formula in C1 to get the inverse

=MATCH(1,INDEX(MOD(ROW(INDIRECT("1:"&A1))*B1,A1),0 ),0)

gives #N/A if there is no inverse

roman_pearce's picture

brute force search

Comment on 2008-01-02 18:55 from roman_pearce (Maple Rating 4 508)

This nifty construction does a brute force search, which is exponential time in the length of the modulus. That is not a very good way to do arithmetic. Imagine subtracting two numbers by searching for the possible result.

Well, somewhat

Comment on 2008-01-03 08:08 from Chris Roung (Maple Rating 2 111)

It does somewhat.

In my example Mod(7,23) =MATCH(1,INDEX(MOD(ROW(INDIRECT("1:"&A1))*B1,A1),0 ),0) calculates the modulus of all the numbers from (1 to 23) multiplied by 7 and returns the values. It then matches the remainder that has a value of one and returns the value that gave that remainder. Very ingenious indeed.

Help me explain

Comment on 2008-02-21 19:26 from jevans95 (1)

 

=MATCH(1,INDEX(MOD(ROW(INDIRECT("1:"&A1))*B1,A1),0),0))

I used this command for a project that required me to program the Chinese Remainder Theorem into Excel. My professor then asked me how this works. Of course, I was not exactly sure. Could you please give me an explanation of the commands and how the function works?

Sure - I'll give it a shot

Comment on 2008-03-21 11:16 from Chris Roung (Maple Rating 2 111)

Okay it's been a while since I was here and worked on that command.  It took me a while to figure it out but basically, internally it lays everything out in a matrix and calculates the mod and matches the number to one which then cross references it with the value that gave it one and displays that value.  That's it, quickly in a nutshell. 

If you take an hour of your time and look up each command in the help file (match, index, mod, row, indirect etc... ) and disect the formula you should eventually be able to figure out how it works.  It's definitely confusing at first but quite ingenious, I say that because it took me quite some time to actually figure it out.  Right now as I write I have somewhat forgotten exactly how it works but with a little time it wouldn't take long.  It was basically for a cryptography project I was working on which I have since forgotten about.  Anyways, by the date of the post I'm sure you've already figured it out.

Axel Vogt's picture

VBA code

Comment on 2008-03-21 16:41 from Axel Vogt (Maple Rating 4 994) 
Have not used VBA for a longer time ... First correct a 'feature' in Excel's
modulo function and then translate the EGCD given by Roman Pearce. The code
has just to be copied into a module of an Excel VBA project.


Function myMod(a As Long, p As Long) As Long
' check that for a=-20, p=7: Excel would return -6, we want positive numbers
myMod = (a) Mod p
If a < 0 Then
  myMod = myMod + Abs(p)
End If
End Function


Function invMod(m As Long, p As Long)
' returns invers modulo p using the extended GCD algorithm (Knuth?)
Dim a As Long, b As Long, q As Long, t As Long, x As Long, y As Long

a = p
b = m
x = 1
y = 0
While Not (b = 0)
  t = b
  q = Application.WorksheetFunction.Floor(CDbl(a / t), 1)
  ' CodeGeneration[VisualBasic] is not aware of that VBA, it uses VB
  b = a - q * t
  a = t
  t = x
  x = y - q * t
  y = t
Wend
If (y < 0) Then
  y = y + p
End If
invMod = y
End Function


Sub tst_invMod()
' test, to be displayed in the debug window
Dim a As Long, p As Long, b As Long, ab As Long, j As Long

p = 23 ' prime
For j = 1 To p - 1
  a = j
  b = invMod(a, p)
  ab = myMod(a * b, p)
  Debug.Print a & "^(-1) mod(" & p; ") = " & b, _
    "a*b mod(" & p & ") = " & myMod(a * b, p)
Next j
End Sub


The largest (signed) integer of type long is 2^31 in VBA. Taking
p = prevprime(2^31) = 2147483647, a = prevprime(p) = 2147483629
one immediately gets a^(-1) = 119304647, which equals Maple's answer.

The ugly worksheet & search method is limited to p < 65536 and
should be quite slow.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.
}