Introduction to Cryptography with Open-Source Software

28 Cryptography with Open-Source Software

tested only by all prime numbers up to 38; they are 2, 3, 5, 7, 11, 13, 17, 19,

23, 29, 31 , 37. Since none of these are a divisor of 1487, it follows that 1487

is indeed prime.

This method will work for any number n, no matter how large. However,

it becomes very clumsy and inefficient in n is very lar ge. Since most useful

prime numbers (from a cryptographic perspective) are in the region of several

hundred digits long, better and fa ster methods are required. The creation of

algorithms for efficient prima lity testing of large integers is thus a major area

of mathematical research. Two methods will be discussed in Section 2.4.

Calculating the greatest common divisor

One very popular a nd fast algo rithm for calculating ...