Structure and Interpretation of Computer Programs by Harold Abelson and Gerald Jay Sussman with Julie Sussman Page A
Ads: Link
of
n
, then so is
n
/
d
.
But
d
and
n
/
d
cannot both be greater than √
n
.
45 Pierre de Fermat (1601-1665) is considered to be the founder ofmodern number theory. He obtained many important number-theoretic
results, but he usually announced just the results, without providing
his proofs.Fermat's Little Theorem was stated in a letter he wrote in
1640. The first published proof was given byEuler in 1736 (and anearlier, identical proof was discovered in the unpublished manuscripts
of Leibniz). The most famous of Fermat's results – known as Fermat's
Last Theorem – was jotted down in 1637 in his copy of the book
Arithmetic
(by the third-century Greek mathematicianDiophantus) with the
remark “I have discovered a truly remarkable proof, but this margin is
too small to contain it.” Finding a proof of Fermat's Last Theorem
became one of the most famous challenges in number theory. A completesolution was finally given in 1995 by Andrew Wiles of Princeton University.
46 The reduction steps in the cases where the exponent
e
is greater than 1 are based on the fact that, for any integers
x
,
y
, and
m
, we can find the remainder of
x
times
y
modulo
m
by computing separately the remainders of
x
modulo
m
and
y
modulo
m
, multiplying these, and then taking the remainder of the
result modulo
m
. For instance, in the case where
e
is even, we
compute the remainder of
b
e
/2 modulo
m
, square this, and take
the remainder modulo
m
. This technique is useful because it means
we can perform our computation without ever having to deal with
numbers much larger than
m
. (Compare
exercise 1.25 .)
47 Numbers that fool theFermat test are called
Carmichael numbers
, and little is known
about them other than that they are extremely rare. There are 255
Carmichael numbers below 100,000,000. The smallest few are 561, 1105,
1729, 2465, 2821, and 6601. In testing primality of very large
numbers chosen at random, the chance of stumbling upon a value that
fools the Fermat test is less than the chance thatcosmic radiation
will cause the computer to make an error in carrying out a “correct”
algorithm. Considering an algorithm to be inadequate for the first
reason but not for the second illustrates the difference betweenmathematics and engineering.
48 One of the most striking applications ofprobabilistic prime testing has been to the field of cryptography.
Although it is now computationally infeasible to factor an arbitrary
200-digit number, the primality of such a number can be checked in a
few seconds with the Fermat test. This fact forms the basis of a
technique for constructing “unbreakable codes” suggested byRivest,Shamir, andAdleman (1977). The resulting
RSA algorithm
has
become a widely used technique for enhancing the security of
electronic communications. Because of this and related developments,
the study ofprime numbers, once considered the epitome of a topic in
“pure” mathematics to be studied only for its own sake, now turns
out to have important practical applications to cryptography,
electronic funds transfer, and information retrieval.
1.3 Formulating Abstractions with Higher-Order Procedures
We have seen that procedures are, in effect, abstractions that describe
compound operations on numbers independent of the particular numbers.
For example, when we
(define (cube x) (* x x x))
we are not talking about the cube of a particular number, but rather
about a method for obtaining the cube of any number. Of course we
could get along without ever defining this procedure, by
always writing expressions such as
(* 3 3 3)
(* x x x)
(* y y y)
and never mentioning
cube
explicitly. This would place us at a
serious disadvantage, forcing us to work always at the level of the
particular operations that happen to be primitives in the language
(multiplication, in this case) rather than in terms of higher-level
operations. Our programs would be able to compute cubes, but our
language would lack the
n
, then so is
n
/
d
.
But
d
and
n
/
d
cannot both be greater than √
n
.
45 Pierre de Fermat (1601-1665) is considered to be the founder ofmodern number theory. He obtained many important number-theoretic
results, but he usually announced just the results, without providing
his proofs.Fermat's Little Theorem was stated in a letter he wrote in
1640. The first published proof was given byEuler in 1736 (and anearlier, identical proof was discovered in the unpublished manuscripts
of Leibniz). The most famous of Fermat's results – known as Fermat's
Last Theorem – was jotted down in 1637 in his copy of the book
Arithmetic
(by the third-century Greek mathematicianDiophantus) with the
remark “I have discovered a truly remarkable proof, but this margin is
too small to contain it.” Finding a proof of Fermat's Last Theorem
became one of the most famous challenges in number theory. A completesolution was finally given in 1995 by Andrew Wiles of Princeton University.
46 The reduction steps in the cases where the exponent
e
is greater than 1 are based on the fact that, for any integers
x
,
y
, and
m
, we can find the remainder of
x
times
y
modulo
m
by computing separately the remainders of
x
modulo
m
and
y
modulo
m
, multiplying these, and then taking the remainder of the
result modulo
m
. For instance, in the case where
e
is even, we
compute the remainder of
b
e
/2 modulo
m
, square this, and take
the remainder modulo
m
. This technique is useful because it means
we can perform our computation without ever having to deal with
numbers much larger than
m
. (Compare
exercise 1.25 .)
47 Numbers that fool theFermat test are called
Carmichael numbers
, and little is known
about them other than that they are extremely rare. There are 255
Carmichael numbers below 100,000,000. The smallest few are 561, 1105,
1729, 2465, 2821, and 6601. In testing primality of very large
numbers chosen at random, the chance of stumbling upon a value that
fools the Fermat test is less than the chance thatcosmic radiation
will cause the computer to make an error in carrying out a “correct”
algorithm. Considering an algorithm to be inadequate for the first
reason but not for the second illustrates the difference betweenmathematics and engineering.
48 One of the most striking applications ofprobabilistic prime testing has been to the field of cryptography.
Although it is now computationally infeasible to factor an arbitrary
200-digit number, the primality of such a number can be checked in a
few seconds with the Fermat test. This fact forms the basis of a
technique for constructing “unbreakable codes” suggested byRivest,Shamir, andAdleman (1977). The resulting
RSA algorithm
has
become a widely used technique for enhancing the security of
electronic communications. Because of this and related developments,
the study ofprime numbers, once considered the epitome of a topic in
“pure” mathematics to be studied only for its own sake, now turns
out to have important practical applications to cryptography,
electronic funds transfer, and information retrieval.
1.3 Formulating Abstractions with Higher-Order Procedures
We have seen that procedures are, in effect, abstractions that describe
compound operations on numbers independent of the particular numbers.
For example, when we
(define (cube x) (* x x x))
we are not talking about the cube of a particular number, but rather
about a method for obtaining the cube of any number. Of course we
could get along without ever defining this procedure, by
always writing expressions such as
(* 3 3 3)
(* x x x)
(* y y y)
and never mentioning
cube
explicitly. This would place us at a
serious disadvantage, forcing us to work always at the level of the
particular operations that happen to be primitives in the language
(multiplication, in this case) rather than in terms of higher-level
operations. Our programs would be able to compute cubes, but our
language would lack the
Similar Books
