Introduction to Cryptography with Open-Source Software

Basic num ber theory 33

Then

x mod m = atn mod m = a,

x mod n = bsm mod m = b.

For example, consider the two congruence s above: x = 4 (mod 5) and x = 3

(mod 7). Since n = 5 and m = 7 are relatively prime, the extended Euclidean

algorithm can be used to obtain the table:

i q r u v

−1 7 1 0

0 5 0 1

1 1 2 1 −1

2 2 1 −2 3

3 2 0 5 −7

Thus s = −2 and t = 3, and it can be re adily checked that (−2)7 + (3)5 = 1.

With a = 3 and b = 4, then

x = bsm + atn

= (4)(−2)(7) + (3)(3)(5)

= −11

= 24 (mod 35).

In Sage the congruences

x = a (mod m)

x = b (mod n)

can be computed using the command crt(a,b,m,n). For example, with the

values above

sage: crt(4,3,5,7)

-11

Note tha t the result ...