文档介绍：Algorithms plexity
Herbert S. Wilf
University of Pennsylvania
Philadelphia, PA 19104-6395
Copyright Notice
Copyright 1994 by Herbert S. Wilf. This material may be reproduced for any educational purpose, multiple
copies may be made for classes, etc. Charges, if any, for reproduced copies must be just enough to recover
reasonable costs of reproduction. Reproduction mercial purposes is prohibited. This cover page must
be included in all distributed copies.
Edition, Summer, 1994
This edition of Algorithms plexity is the
le “pub/wilf/” at the anonymous ftp site
“”. It may be taken at no charge by all interested persons. Comments and corrections
are e, and should be sent to ******@
Preliminaries
Chapter 4: Algorithms in the Theory of Numbers
Number theory is the study of the properties of the positive integers. It is one of the oldest branches of
mathematics, and one of the purest, so to speak. It has immense vitality, however, and we will see in this
chapter and the next that parts of number theory are extremely relevant to current research in algorithms.
Part of the reason for this is that number theory enters into the analysis of algorithms, but that isn’t
the whole story.
Part of the reason is that many famous problems of number theory, when viewed from an algorithmic
viewpoint (like, how do you decide whether or not a positive integer n is prime?) present extremely deep
and attractive unsolved algorithmic problems. At least, they are unsolved if we regard the question as not
just how to do these putationally, but how to do them as rapidly as possible.
But that’s not the whole story either.
There are close connections between algorithmic problems in the theory of numbers, and problems
in other
elds, seemingly far removed from number theory. There is a unity between these seemingly
diverse problems that enhances the already considerable beauty of any one of them. At least some of the