Introduction to Cryptography with Coding Theory, 3rd Edition

C.3 Examples for Chapter 3

Example 5

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

>> gcd(23456,987654)

ans =
   2

If larger integers are used, they should be expressed in symbolic mode; otherwise, only the first 16 digits of the entries are used accurately. The present calculation could have been done as

>> gcd(sym(’23456’),sym(’987654’))

ans =
   2

Example 6

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

>> [a,b,c]=gcd(23456,987654)

a =
   2

b =
   -3158

c =
   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)$.

>> mod(234*456,789)

ans =
   189

Example 8

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

>> powermod(sym(’234567’),sym(’876543’),sym(’565656565’))

ans =
   5334

Example 9

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