multiplicative inverse?!?!?

Question

Hi, 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 (cuz 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???

Answer 1

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.

Answer 2

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.

Answer 3

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...