If P is prime, and A is known, what is B such that A*B = 1 mod P?
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:
7B0-31A0-1=0
Using modular arithmatic, you can create the following chain:
Code:
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:
3A1 = B1-1
A1 can be "assigned" as zero, and B1 becomes 1
Knowing B1=1, then the middle equation becomes:
7*1-3A0-1=0
or...
3A0 = 6
which results in A0 = 2
From this, the initial equation becomes:
7B0-31*2-1=0
or...
B0 = (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?
VB Code:
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:
VB Code:
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
Re: If P is prime, and A is known, what is B such that A*B = 1 mod P?
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
Re: If P is prime, and A is known, what is B such that A*B = 1 mod P?
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:
VB Code:
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.
:wave:
Re: If P is prime, and A is known, what is B such that A*B = 1 mod P?
FWIW, Here's some code I saw used by someone else in a recent contest (excuse the use of C++ rather than VB)
Code:
//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.
