If P is prime, and A is known, what is B such that A*B = 1 mod P?

[NotLKH]

I wanted a function that would return such a result.
After playing around a bit, I dredged up some old contemplations, and was able to code it to work as I expected.

Lets say you wanted to find some number B, such that 7B = 31A+1

That equation can be zeroed to the following:

7B₀-31A₀-1=0

Using modular arithmatic, you can create the following chain:

7B0-31A0-1=0      'Mod this from the 7multiplier, except for 7 itself
7B1-3A0-1=0        'Mod this from the 3multiplier, except for 3 itself
1B1-3A1-1=0        'Since one of the |mults| is now 1, we can now solve for the unknowns

Since the last equation now ends up, unzeroed as:
3A₁ = B₁-1
A₁ can be "assigned" as zero, and B₁ becomes 1

Knowing B₁=1, then the middle equation becomes:
7*1-3A₀-1=0
or...
3A₀ = 6

which results in A₀ = 2

From this, the initial equation becomes:
7B₀-31*2-1=0
or...
B₀ = (63/7) = 9

which, when all is said and done,
9 is the uniary compliment of 7 modular 31
or:
7*9 mod 31 = 1

Now, the following is the VBNet function that achieves this chaining down and back up.

But, I wonder, is there a better way?

Public Function GET_MULT_TO_ONE(ByVal mA As Integer, ByVal mPrime As Integer) As Integer
        Dim mD As Integer
        If Iterate_Mod_To_One(mA, -1 * mPrime, -1, mD, 0) = True Then
            mD = (mD + mPrime) Mod mPrime
            Return mD
        End If
        Return -1
    End Function
    Public Function Iterate_Mod_To_One(ByVal mA As Integer, ByVal mB As Integer, ByVal mC As Integer, ByRef mD As Integer, ByVal mLev As Integer) As Boolean
        mLev = mLev Mod 2
        If mA = 0 Or mB = 0 Or mC = 0 Then
            mD = -1
            Return False
        End If
        'assume user knows what they are doing, ie..
        'initial |mB| is prime,
        'initial |mC| is 1
        'ma will always be positive, mb and mc will always be negative
        'such that X*ma + Y*mb + mc = 0
        If mA = 1 Then
            mD = -1 * mC
            Return True
        End If
        If mB = -1 Then
            mD = mC
            Return True
        End If
 
 
        Dim mA2 As Integer
        Dim mB2 As Integer
        Dim mD2 As Integer
 
        mA2 = mA
        mB2 = mB
 
        Select Case mLev
            Case 0
                mB2 = mB Mod mA
            Case 1
                mA2 = mA Mod mB
        End Select
        If Iterate_Mod_To_One(mA2, mB2, mC, mD, mLev + 1) = True Then
            Select Case mLev
                Case 0
                    mD = -1 * (mB * mD + mC) / mA
                Case 1
                    mD = -1 * (mA * mD + mC) / mB
            End Select
            Return True
        End If
    End Function

And the following is some code illustrating how its used, and that it seems to actually work:

Private Sub MenuItem28_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MenuItem28.Click
        'lets just see if it works for the first 19 primes
 
        Dim MyPrimes() As Integer
        Dim mOutArr() As Integer
        Dim MyI As Integer
        ReDim MyPrimes(19)
        MyPrimes(0) = 2
        MyPrimes(1) = 3
        MyPrimes(2) = 5
        MyPrimes(3) = 7
        MyPrimes(4) = 11
        MyPrimes(5) = 13
        MyPrimes(6) = 17
        MyPrimes(7) = 19
        MyPrimes(8) = 23
        MyPrimes(9) = 29
        MyPrimes(10) = 31
        MyPrimes(11) = 37
        MyPrimes(12) = 41
        MyPrimes(13) = 43
        MyPrimes(14) = 47
        MyPrimes(15) = 53
        MyPrimes(16) = 59
        MyPrimes(17) = 61
        MyPrimes(18) = 67
        MyPrimes(19) = 71
        For MyI = 0 To 19
            Call BUILD_MULT_TO_ONE_FROM_PRIME2(MyPrimes(MyI), mOutArr)
        Next
    End Sub
    Public Sub BUILD_MULT_TO_ONE_FROM_PRIME2(ByVal mPrime As Integer, ByRef mOutArr() As Integer)
        ReDim mOutArr(mPrime - 1)
        Dim MyOutStr As String
        Dim MySeed As Integer
        For MySeed = 0 To mPrime - 1
            mOutArr(MySeed) = -1
        Next
        'so, if good, then
        'MySeed * mOutArr(MySeed) = K => K mod mP = 1
        For MySeed = 0 To mPrime - 1
            mOutArr(MySeed) = GET_MULT_TO_ONE(MySeed, mPrime)
        Next
 
        'now, lets illustrate the results
        MyOutStr = "Prime " & mPrime & ":" & vbTab & "A*B = 1 (mod " & mPrime & " )" & vbCrLf
        For MySeed = 0 To mPrime - 1
            MyOutStr += vbTab & MySeed & "*" & mOutArr(MySeed) & "=" & ((MySeed * mOutArr(MySeed)) Mod mPrime) & vbCrLf
        Next
        MessageBox.Show(MyOutStr)
    End Sub

[sql_lall]

From the title of your post, and the equations you're looking at, it seems like you're looking at how to compute the modular inverse of a number in a given base.
note that this also allows you to solve Ax + By = k when GCD(x, y) is a factor of k, because you then divide by GCD(x, y) and you can morph into Ax' + By' = 1, where GCD(x', y') = 1.
Taking this mod x', you get By' = 1, so B is the modular inverse of y' mod A.
Similarly, A is the modular inverse of x' mod B.

What you've posted is roughly the general accepted way of doing it - basically the Euclidean Algorithm in reverse. A nice explanation can be found here:
http://www.antilles.k12.vi.us/math/c..._algorithm.htm

[NotLKH]

Thanks!
I'd rep you, but I can't just yet.

Anyways, from that site, I've developed the following code, a little neater than what I had before:

Public Sub CALC_MOD_INVERSE( _
                                ByVal MY_PRIME As Integer, _
                                ByVal P_0 As Integer, _
                                ByVal P_1 As Integer, _
                                ByRef INV_P_1 As Integer, _
                                Optional ByVal X_0 As Integer = 0, _
                                Optional ByVal X_1 As Integer = 1, _
                                Optional ByVal mLev As Integer = 0)
        Dim P_2 As Integer
        Dim Q_0 As Integer
        Dim X_2 As Integer
 
        If mLev = 0 Then
            If P_1 = 0 Then
                INV_P_1 = -1
                Exit Sub
            End If
            If P_1 = 1 Then
                INV_P_1 = 1
                Exit Sub
            End If
        End If
 
        P_2 = P_0 Mod P_1
        Q_0 = P_0 \ P_1
        If P_2 <> 0 Then
            INV_P_1 = (X_0 - X_1 * Q_0) Mod MY_PRIME
            X_2 = INV_P_1
            Call CALC_MOD_INVERSE(MY_PRIME, P_1, P_2, INV_P_1, X_1, X_2, 1)
        End If
        If mLev = 0 Then
            INV_P_1 = (INV_P_1 + MY_PRIME) Mod MY_PRIME
        End If
        'when mLev = 0,
        'If you are trying to find B, where B is the "inverse" of A,
        'Such That (A*B) Mod SomeNum = 1,
        'Then the initial values are:
        'MY_PRIME = SomeNum
        'P_0 = SomeNum
        'P_1 = A
        'INV_P_1 will be the returned inverse of A
 
        'I don't really need X_2, since it is being passed ByVal to the next level.
        'I could just pass INV_P_1 a second time,
 
        'But I think it keeps things clearer, in relation to the formula:
        'x[sub]i[/sub] = (x[sub]i-2[/sub] - [x[sub]i[/sub]-1*q[sub]i-2[/sub]]) (mod b)  
    End Sub

Nice and tidy way to build conversion matrices to change multiplands of variables to 1 when solving modular simultaneous equations.

[sql_lall]

FWIW, Here's some code I saw used by someone else in a recent contest (excuse the use of C++ rather than VB)

//returns x, such that a*x = b mod c
int axbmodc(int a,int b,int c){
  if(a==0)return 0;
  return (axbmodc(c % a, (a - b % a) % a, a) * c + b) / a;
}

Now, don't ask me how this works :S - but it seems similar to what you're doing.