Algorithm correctness

[text] B o o T e R Al R Most Lisp implementations include a primitive called runtime whm integer that specifies the amount of time the system has been s g for example in microseconds. The following timedprime tesumt punroc 3 called with an integer n prints n and checks to see if n is prime. If n is the procedure prints three asterisks followed by the number of microseco in performing the test. define timedprimetest n define starttime runtime define foundprime prime n 41 In testing primality of very large numbers chosen at random the chance of upon a value that fools the Fermat test is less than the chance that cosmic radia cause the computer to make an error in carrying out a correct algorithm. Cons an algorithm to be inadequate for the first reason but not for the second illustrat difference between mathematice and engineering. 49 One of the most striking applications of probabilistic prime testing has the field of cryptography. Although it is now computationally infeasible to fz arbitrary 200digit number the primality of such a number can be checked i seconds with the Fermat test. This fact forms the basis of a technique for cons unbreakable codes suggested by Rivest Shamir and Adelman 1977. Be and related developments the study of prime numbers once considered the a topic in pure mathematics to be studied only for its own sake now important practical applications to cryptography electronic fu ion retrieval.