I have an assignment in CS class to create an affine cipher where the equation for encrypting a character is ax+b. I have created the encryption function. However, I am not sure how to create a decryption function because the inverse of the affine transform ((y-b)/x) won't work because there is division involved. I have seen the wikipedia page on affine encryption/decryption however I do not understand the decryption section. Could someone explain this to me and perhaps give a little pseudo-code to show me how i might go about creating a decryption function?

Thanks

Check out the modular multiplicative inverse. This is the equivalent of division modulo some number. Implementing it using the EEA can be tricky, though there is a shortcut.

Also, as Frob says, you have the wrong decryption function. You're trying to get "x" back, not "a". Look through it again.

Also, for bonus points, implement a message decryption function without using "a" nor "b".

There are multiple inverses of elements mod 256 though.

Modulo arithmetic mod p only forms a field (i.e. all non-zero elements have unique inverses with respect to multiplication) if and only if p is prime...

There are multiple inverses of elements mod 256 though.

Modulo arithmetic mod p only forms a field (i.e. all non-zero elements have unique inverses with respect to multiplication) if and only if p is prime...

"a" is always chosen to be invertible modulo 26 (or 256, depending on the alphabet). Otherwise, decryption is indeed not possible.

I guess so ;)

Then the rule is

a (mod n) has a unique inverse if and only if a and n are coprime (i.e. their greatest common divisor is 1). So that works if a is odd with n = 256 since n is a power of 2 hence coprime to any odd number.