Introduction to Cryptography with Coding Theory, 3rd Edition

D.2 Computations for Chapter 3

To find the greatest common divisor, type the following first line and then evaluate:

gcd(119, 259)
7

To find the next prime greater than or equal to a number:

next_prime(1000)
1009

To factor an integer:

factor(2468)
2^2 * 617

Let’s solve the simultaneous congruences $x\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}5)\text{,}x\equiv 3(\mathrm{m}\mathrm{o}\mathrm{d}7)$:

crt(1,3,5,7) 
31

To solve the three simultaneous congruences $x\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}5)\text{,}x\equiv 3(\mathrm{m}\mathrm{o}\mathrm{d}7)\text{,}x\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}11)$:

a= crt(1,3,5,7) 
crt(a,0,35,11) 
66

Compute $123^456(\text{mod}789)$:

mod(123,789)456 
699

Compute $d$ so that $65d\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}987)$:

mod(65,987)(-1) 
410

Let’s check the answer:

mod(65*410, 987) 
1