1. ## mod arithmetic

This an example in my notes...

Encipering transformation: f(x) = 9x + 3(mod 100)

Finding the deciphering transformation:

Alice now wishes to find a number t such that 9t = 1 mod 100. She finds that 9 x 89 = 1 mod 100. She finds by trial and error (until she improves her arithmetic!) that 9 x 89 = 1 mod 100.

I was just wondering is there another quicker way that alice can find this t, rather than trial and error?

2. Hello,

Originally Posted by hunkydory19
This an example in my notes...

Encipering transformation: f(x) = 9x + 3(mod 100)

Finding the deciphering transformation:

Alice now wishes to find a number t such that 9t = 1 mod 100. She finds that 9 x 89 = 1 mod 100. She finds by trial and error (until she improves her arithmetic!) that 9 x 89 = 1 mod 100.

I was just wondering is there another quicker way that alice can find this t, rather than trial and error?

Bézout's identity let us say that if a and b are coprime, there exist u and v such that au+bv=1 -> au=1 mod b.
We'll find u and v by the Euclidian algorithm

a=9, b=100

100=9x11+1
-> 1=100-9x11 (u=-11 and v=1)

9x(-11) = 1 mod 100

-11=89 mod 100

Hence t=89