A code is implemented with the following statement.  Decrypt the code.

    x^197 mod 3131  

The totient of 3131 is needed and is found below:

    3131 = 31 * 101    

    {psi} (3131) = psi(31) * psi(101) = (31-1)(101-1)=3000     because 31 and 101 are prime

Eulers Theorem a^{psi(n)} mod n =1     so:

    x^{3000m} mod (3131) = 1    Where m is an integer to give us more flexibility in generating an inverse in step XXX below.   Multiply both sides by x

    x^{3000m+1} mod (3131) = (x) mod (3131)

So if you can find a power d where:

    197d = 3000m + 1  or equivalently:

    (197d) mod(3000) = (1) mod(3000) then you can take the encrypted numbers to the power of d and out will pop the plain text original series

Now you use the Euclidean algorithm to find 1 in terms of 197 and 3000. This yields:

   1 = 533(197) - 35(3000)     Taking the mod(3000) of both sides

   (1)mod(3000) = (533)(197)  which shows d=533   is the decryption power we are looking for

This example used smaller numbers so as to make the example transparent.  However if the input character were to be X=31 or 101 I think the system breaks down.

 

 

Categories: Computingencryption

0 Comments

Leave a Reply

Avatar placeholder

Your email address will not be published. Required fields are marked *