Introduction to Cryptography with Coding Theory, 3rd Edition

A.4 Examples for Chapter 3

Example 5

Find $gcd(23456\text{,}987654)$.

In[1]:= GCD[23456, 987654]

Out[1]= 2

Example 6

Solve $23456x+987654y=2$ in integers $x\text{,}y$.

In[2]:= ExtendedGCD[23456, 987654]

Out[2]= {2, {-3158, 75}}

This means that 2 is the gcd and $23456\cdot (-3158)+987654\cdot 75=2$.

Example 7

Compute $234\cdot 456(\text{mod}789)$.

In[3]:= Mod[234*456, 789]

Out[3]= 189

Example 8

Compute ${234567}^{876543}(\text{mod}565656565)$.

In[4]:= PowerMod[234567, 876543, 565656565]

Out[4]= 473011223

Example 9

Find the multiplicative inverse of $87878787(\text{mod}9191919191)$.

In[5]:= PowerMod[87878787, -1, 9191919191]

Out[5]= 7079995354

Example 10

Solve $7654x\equiv 2389(\text{mod}65537)$.

SOLUTION

Here is one way. It corresponds to the method in Section 3.3. We calculate ${7654}^{-1}$ and then ...