文档介绍：putational Introduction to Number Theory
and Algebra
(Version 1)
Victor Shoup
This PDF document contains hyperlinks, and one may navigate through it
by clicking on theorem, definition, lemma, equation, and page numbers, as
well as URLs, and chapter and section titles in the table of contents; most
PDF viewers should also display a list of “bookmarks” that allow direct
access to chapters and sections.
TEAM LinG
Copyright c 2005 by Victor Shoup <victor@>
All rights reserved. The right to publish or distribute this work in print form
belongs exclusively to Cambridge University Press; however, this electronic
version is distributed under the terms and conditions of a mons
license (Attribution-mercial-NoDerivs ):
You are free to copy, distribute, and display this electronic
version under the following conditions:
Attribution. You must give the original author credit.
mercial. You may not use this electronic version for
commercial purposes.
No Derivative Works. You may not alter, transform, or
build upon this electronic version.
For any reuse or distribution, you must make clear to others
the license terms of this work.
Any of these conditions can be waived if you get permission
from the author.
For more information about the license, visit
/licenses/by-nd-nc/.
TEAM LinG
Contents
Preface page x
Preliminaries xiv
1 Basic properties of the integers 1
Divisibility and primality 1
Ideals and mon divisors 4
Some consequences of unique factorization 8
2 Congruences 13
Definitions and basic properties 13
Solving linear congruences 15
Residue classes 20
Euler’s phi function 24
Fermat’s little theorem 25
Arithmetic functions and M¨obius inversion 28
puting with large integers 33
Asymptotic notation 33
Machine models plexity theory 36
Basic integer arithmetic 39
in Zn 48
(∗)51
Notes 52
4 Euclid’s algorithm 55