multiplicative inverse? [closed]
-
19-09-2019 - |
Question
I know that an affine cipher substitutes BD with SG. I need to find the encryption formula, in the form y = a x + b
, where a and b are coefficients.
From the information above I end up having to equations:
a+b=18
and
3a+b=6
So I am working like this:
a+b=18 and 3a + b = 6-> 3a+18-a=6-> 2a= 6-18 -> 2a=14 (as it is mod 26)
b=18-a
2a=?
So, O want to multiply by the multiplicative inverse of 2 mod 26
I can't find a multiplicative inverse of number 2 with 26 (y = ax + b mod 26
)
Can anyone please help me find a and b?
Solution
That's because 2 doesn't have a multiplicative inverse mod 26: since 13*2=0, there does not exist K such that K * a = 1. Your modulus must be prime. Try looking up the Chinese Remainder Theorem for more information.
To be more specific, integers mod 26 is not a field (a mathematical set where every element, except 0, has a multiplicative inverse). Any ring in which a * b = 0, for some a!=0 and b!=0, is not a field.
In fact, a field will always have p^n elements, where p is a prime number and n is a positive integer. The simplest fields are just integers mod a prime number, but for prime powers you need to construct a more elaborate system. So, in short, use a different modulus like 29.
OTHER TIPS
Does a = 7 work? 2*7 = 14. Thus, b = 11.
Let's check the 2 equations to see if that works:
- 7+11 = 18 (check for the first equation).
- 3*7+11=21+11 = 32 = 6.
What is wrong with the above?
EDIT: Ok, now I see what could go wrong with trying to do a division by 2 in a non-prime modulus as it is similar to a division by 0. You could take ribond's suggestion of using the Chinese Remainder Theorem and split the equations into another pair of pairs:
mod 13: a+b=5, 3a+b=6. (2a = 1 = 14 => a=7. b = 18-7 = 11.)
mod 2: a+b=0. 3a+b=0 (Note this is the same equation and has a pair of possible solutions where a and b are either 0 or 1.)
Thus there is the unique solution for your problem I think.
Other posters are right in that there is no inverse of 2 modulo 26, so you can't solve 2a=14 mod 26 by multiplying through by the inverse of 2. But that doesn't mean that 2a=14 mod 26 isn't solvable.
Consider the general equation cx = d mod n (c=2,d=14,n=26 in your case). Let g = gcd(c,n). The equation cx=d has a solution if an only if g divides d. If g divides d, then there are in fact multiple solutions (g of them). The equation (c/g)x = d/g mod n/g has a unique solution (call it x_0) because c/g is relatively prime to n/g and therefore has an inverse. The solutions to the original equation are x_0, x_0 + n/g, ..., x_0 + (g-1)n/g.
In your case c=2,d=14,n=26, and g=2. g divides d, so first solve the equation (2/2)x = (14/2) mod (26/2) which gives 7. So both 7 and 7+13=20 solve your original equation.
Note that this means you haven't uniquely determined your affine transformation, two possibilities still exist. You need another data point...