没有合适的资源?快使用搜索试试~ 我知道了~
首页Elementary Number Theory and its Applications - Rosen - 1984
资源详情
资源评论
资源推荐
Elementary
Number
Theory
and
lts
Applications
Kenneth
H. Rosen
AT&T
Informotion
Systems
Laboratories
(formerly part
of
Bell Laborotories)
A
YY
ADDISON-WESLEY
PUBLISHING
COMPANY
Read
ing, Massachusetts
Menlo Park,
California
London Amsterdam
Don Mills,
Ontario
Sydney
Cover:
The iteration
of the
transformation
T(n)
:
is
depicted.
The
Collatz
conjecture
asserts
that with
any
starting
point,
the
iteration
of ?"eventually
reaches
the
integer
one.
(See
Problem
33
of
Section
l.2of
the
text.)
Library
of Congress
Cataloging
in Publication
Data
Rosen,
Kenneth
H.
Elementary
number
theory
and its
applications.
Bibliography: p.
Includes
index.
l. Numbers,
Theory
of.
I. Title.
QA24l.R67
1984
rsBN
0-201-06561-4
512',.72
83-l 1804
Reprinted with
corrections,
June
| 986
Copyright
O
1984
by Bell
Telephone
Laboratories
and
Kenneth
H. Rosen.
All
rights
reserved.
No
part
of this
publication
may
be
reproduced,
stored
in
a
retrieval
system, or
transmitted,
in
any form
or by
any means,
electronic,
mechanical,
photocopying,
recording,
or otherwise,
without
prior
written
permission
of the
publisher.
printed
in
the United
States of
America.
Published
simultaneously
in Canada.
DEFGHIJ_MA_8987
\
n/2
if n
is
even
l Qn
+ l)/2
if
n
is
odd
Preface
Number
theory
has long
been a favorite subject
for
students and teachers of
mathematics. It is a classical
subject and has a reputation for being
the
"purest" part
of
mathematics,
yet
recent
developments
in
cryptology and
computer science are based on elementary number
theory.
This
book
is
the
first text to
integrate
these important
applications of elementary
number
theory
with
the traditional topics covered in an introductory number
theory
course.
This book is suitable
as a text in
an undergraduate number theory
course at
any
level.
There are no
formal
prerequisites
needed
for most of
the
material
covered,
so that even a bright high-school
student could
use this book.
Also,
this book is designed
to be a useful
supplementary book for computer
science
courses, and as a number
theory
primer
for computer
scientists interested in
learning
about the new
developments in
cryptography.
Some of the important
topics that will interest
both
mathematics
and computer science students
are
recursion,
algorithms and their
computationai
complexity, computer
arithmetic
with
large integers,
binary
and hexadecimal
representations
of integers,
primality
testing,
pseudoprimality,
pseudo-random
numbers,
hashing functions,
and cryptology, including
the recently-invented
area of
public-key
cryptography.
Throughout
the book various
algorithms
and
their
computational
complexities
are discussed.
A
wide
variety
of
primality
tests
are
developed
in the
text.
Use
of the Book
The
core material
for
a course
in number
theory is
presented
in
Chapters 1,
2,
and 5,
and in Sections
3.1-3.3
and
6.1. Section
3.4 contains
some linear
algebra;
this section
is
necessary
background
for
Section 7.2;
these
two
sections
can be
omitted
if desired.
Sections 4.1, 4.2,
and 4.3
present
traditional
applications
of number
theory
and Section 4.4 presents
an
application
to computer
science;
the instructor
can decide which
of
these
sections
to cover.
Sections
6.2
and 6.3
discuss
arithmetic
functions.
Mersenne
primes,
and
perfect
numbers;
some
of this material
is used
in
Chapter
8.
Chapter 7
covers
the applications
of number
theory to cryptology.
Sections
7.1, 7.3,
and 7.4, which
contain
discussions
of classical
and
public-key
vt
Preface
cryptography,
should
be included
in
all courses.
Chapter
8 deals with
primitive
roots;
Sections
8.1-8.4
should
be covered
if
possible.
Most
instructors
will
want
to include
Section
8.7 which
deals with
pseudo-random
numbers.
Sections
9.1
and
9.2
are
about
quadratic
residues
and reciprocity,
a
fundamental
topic
which
should
be covered
if
possible;
Sections
9.3 and
9.4
deal with
Jacobi
symbols
and
Euler
pseudoprimes
and
should
interest
most
readers.
Section 10.1,
which
covers rational
numbers
and decimal
fractions.
and
Sections
I 1.1
and
I 1.2 which
discuss Pythagorean
triples
and Fermat's
last
theorem
are
covered
in most
number
theory courses.
Sections
10.2-10.4
and I
1.3 involve
continued
fractions;
these sections
are optional.
The
Contents
The reader
can
determine which
chapters
to study
based on
the following
description
of their
contents.
Chapter
I introduces
two importants
tools
in
establishing results
about the
integers,
the well-ordering property
and
the
principle
of mathematical
induction.
Recursive
definitions
and
the binomial
theorem
are also developed.
The
concept
of divisibility
of integers
is introduced.
Representations
of
integers
to different
bases are
described,
as are algorithms for
arithmetic
operations with
integers
and
their computational
complexity
(using
big-O
notation).
Finally,
prime
numbers,
their distribution,
and conjectures
about
primes
are discussed.
Chapter 2 introduces
the
greatest
common divisor of
a set of integers. The
Euclidean
algorithm,
used to find
greatest
common divisors,
and its
computational
complexity,
are discussed,
as are algorithms
to express
the
greatest
common
divisor
as a linear
combination of the integers involved.
The
Fibonacci
numbers
are introduced.
Prime-factorizations,
the fundamental
theorem
of arithmetic,
and factorization
techniques are
covered. Finally,
linear
diophantine
equations are discussed.
Chapter 3 introduces
congruences
and develops
their
fundamental
properties.
Linear
congruences in
one unknown are discussed,
as are systems
of linear congruences in
one or more
unknown.
The
Chinese remainder
theorem is developed,
and its
application to computer arithmetic with
large
integers is described.
Chapter 4 develops
applications
of.congruences. In
particular,
divisibility
tests, the
perpetual
calendar which
provides
the
day of
the
week
of any date,
round-robin
tournaments,
and computer hashing
functions for data
storage
are
discussed.
Preface
Chapter 5
develops Fermat's little
theorem and
Euler's theorem
which
give
some important
congruences
involving
powers
of
integers. Also,
Wilson's
theorem
which
gives
a congruence for factorials is
discussed. Primality
and
probabilistic primality
tests based on
these results are developed.
Pseudoprimes,
strong
pseudoprimes,
and Carmichael
numbers
which
masquarade
as
primes
are
introduced.
Chapter 6 is
concerned
with
multiplicative
functions and
their
properties.
Special emphasis
is
devoted
to
the Euler
phi-function,
the
sum
of the divisors
function,
and
the
number
of divisors
function and explicit formulae
are
developed
for
these
functions.
Mersenne
primes
and
perfect
numbers
are
discussed.
Chapter 7
gives
a thorough discussion
of applications of number
theory
to
cryptology,
starting with
classical
cryptology.
Character ciphers
based
on
modular
arithmetic
are described,
as is
cryptanalysis
of these
ciphers. Block
ciphers
based
on modular
arithmetic
are also discussed.
Exponentiation
ciphers
and their
applications
are
described,
including
an application
to
electronic
poker.
The
concept
of a
public-key
cipher system
is introduced
and
the RSA
cipher is described
in
detail.
Knapsack
ciphers
are discussed,
as are
applications
of cryptography
to
computer
science.
Chapter
8 includes
discussions
of the
order
of an integer
and
of
primitive
roots.
Indices, which
are similar
to logarithms,
are introduced.
Primality
testing
based
on
primitive
roots
is
described.
The
minimal
universal
exponent
is studied.
Pseudo-random
numbers
and means
for
generating
them
are
discussed.
An
application
to
the splicing
of telephone
cables is
also
given.
Chapter
9
covers
quadratic
residues
and the famous
law
of
quadratic
reciprocity.
The
Legendre
and
Jacobi
symbols
are introduced
and algorithms
for
evaluating
them
are developed.
Euler
pseudoprimes
and
a
probabilistic
primality
test
are
covered.
An algorithm
for
electronically
flipping
coins is
developed.
Chapter
l0
covers
rational
and irrational
numbers,
decimal
representations
of real
numbers,
and finite
simple
continued
fractions
of rational
and irrational
numbers.
Special
attention
is
paid
to
the continued
fractions
of
the
square
roots
of
po"itive
integers.
Chapter
1l
treats
some
nonlinear
diophantine
equations.
Pythagorean
triples
are described.
Fermat's
last
theorem
is discussed.
Finallv.
Pell's
equation
is
covered.
vtl
剩余461页未读,继续阅读
osakaanarg
- 粉丝: 30
- 资源: 474
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
- SPC统计方法基础知识.pptx
- MW全能培训汽轮机调节保安系统PPT教学课件.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论1