Number Theory for Computing,9783540430728

Number Theory for Computing

by ;
Edition: 2nd
ISBN13: 9783540430728
ISBN10: 3540430725
Format: Hardcover
Pub. Date: 2002-07-01
Publisher(s): Springer-Nature New York Inc
  • Free Shipping Icon

    Free Shipping On Orders Over $59

    Free standard shipping on order over $59 to your home address. Marketplace purchases through third-party sellers are excluded from free shipping promotions.

List Price: $90.05

Rent Textbook

Select for Price
Add to Cart
There was a problem. Please try again later.

Digital

Rent Digital Options
Online:30 Days access
Downloadable:30 Days
$23.40
Online:60 Days access
Downloadable:60 Days
$31.20
Online:90 Days access
Downloadable:90 Days
$39.00
Online:120 Days access
Downloadable:120 Days
$46.80
Online:180 Days access
Downloadable:180 Days
$50.70
Online:1825 Days access
Downloadable:Lifetime Access
$77.99
*To support the delivery of the digital material to you, a non-refundable digital delivery fee of $3.99 will be charged on each digital item.
$50.70*
Add to Cart

New Textbook

We're Sorry
Sold Out

Used Textbook

We're Sorry
Sold Out

Buy from our Marketplace starting at $38.95

How Marketplace Works:

  • This item is offered by an independent seller and not shipped from our warehouse
  • Item details like edition and cover design may differ from our description; see seller's comments before ordering.
  • Sellers much confirm and ship within two business days; otherwise, the order will be cancelled and refunded.
  • Marketplace purchases cannot be returned to eCampus.com. Contact the seller directly for inquiries; if no response within two days, contact customer service.
  • Additional shipping costs apply to Marketplace purchases. Review shipping costs at checkout.

Summary

There are many surprising connections between the theory of numbers, which is one of the oldest branches of mathematics, and computing and information theory. Number theory has important applications in computer organization and security, coding and cryptography, random number generation, hash functions, and graphics. Conversely, number theorists use computers in factoring large integers, determining primes, testing conjectures, and solving other problems. This book takes the reader from elementary number theory, via algorithmic number theory, to applied number theory in computer science. It introduces basic concepts, results, and methods, and discusses their applications in the design of hardware and software, cryptography, and security. It is aimed at undergraduates in computing and information technology, but will also be valuable to mathematics students interested in applications. In this 2nd edition full proofs of many theorems are added and some corrections are made.

Table of Contents

Elementary Number Theory
1(173)
Introduction
1(20)
What is Number Theory?
1(12)
Applications of Number Theory
13(1)
Algebraic Preliminaries
14(7)
Theory of Divisibility
21(31)
Basic Concepts and Properties of Divisibility
21(6)
Fundamental Theorem of Arithmetic
27(6)
Mersenne Primes and Fermat Numbers
33(7)
Euclid's Algorithm
40(4)
Continued Fractions
44(8)
Diophantine Equations
52(11)
Basic Concepts of Diophantine Equations
52(2)
Linear Diophantine Equations
54(3)
Pell's Equations
57(6)
Arithmetic Functions
63(22)
Multiplicative Functions
63(3)
Functions τ(n), σ(n) and s(n)
66(5)
Perfect, Amicable and Sociable Numbers
71(8)
Functions φ(n), λ(n) and μ(n)
79(6)
Distribution of Prime Numbers
85(26)
Prime Distribution Function π(x)
85(2)
Approximations of π(x) by x/ln x
87(7)
Approximations of π(x) by Li(x)
94(1)
The Riemann ξ-Function ξ(s)
95(9)
The nth Prime
104(2)
Distribution of Twin Primes
106(4)
The Arithmetic Progression of Primes
110(1)
Theory of Congruences
111(49)
Basic Concepts and Properties of Congruences
111(7)
Modular Arithmetic
118(5)
Linear Congruences
123(7)
The Chinese Remainder Theorem
130(3)
High-Order Congruences
133(6)
Legendre and Jacobi Symbols
139(11)
Orders and Primitive Roots
150(5)
Indices and kth Power Residues
155(5)
Arithmetic of Elliptic Curves
160(11)
Basic Concepts of Elliptic Curves
160(3)
Geometric Composition Laws of Elliptic Curves
163(1)
Algebraic Computation Laws for Elliptic Curves
164(4)
Group Laws on Elliptic Curves
168(1)
Number of Points on Elliptic Curves
169(2)
Bibliographic Notes and Further Reading
171(2)
Computational/Algorithmic Number Theory
173(130)
Introduction
173(29)
What is Computational/Algorithmic Number Theory?
174(3)
Effective Computability
177(4)
Computational Complexity
181(7)
Complexity of Number-Theoretic Algorithms
188(6)
Fast Modular Exponentiations
194(4)
Fast Group Operations on Elliptic Curves
198(4)
Algorithms for Primality Testing
202(26)
Deterministic and Rigorous Primality Tests
202(4)
Fermat's Pseudoprimality Test
206(2)
Strong Pseudoprimality Test
208(7)
Lucas Pseudoprimality Test
215(7)
Elliptic Curve Test
222(3)
Historical Notes on Primality Testing
225(3)
Algorithms for Integer Factorization
228(26)
Complexity of Integer Factorization
228(4)
Trial Division and Fermat Method
232(2)
Legendre's Congruence
234(3)
Continued FRACtion Method (CFRAC)
237(3)
Quadratic and Number Field Sieves (QS/NFS)
240(4)
Polland's ``rho'' and ``p - 1'' Methods
244(7)
Lenstra's Elliptic Curve Method (ECM)
251(3)
Algorithms for Discrete Logarithms
254(19)
Shanks' Baby-Step Giant-Step Algorithm
255(3)
Silver-Pohlig-Hellman Algorithm
258(4)
Index Calculus for Discrete Logarithms
262(4)
Algorithms for Elliptic Curve Discrete Logarithms
266(4)
Algorithm for Root Finding Problem
270(3)
Quantum Number-Theoretic Algorithms
273(14)
Quantum Information and Computation
273(5)
Quantum Computability and Complexity
278(1)
Quantum Algorithm for Integer Factorization
279(6)
Quantum Algorithms for Discrete Logarithms
285(2)
Miscellaneous Algorithms in Number Theory
287(13)
Algorithms for Computing π(x)
287(5)
Algorithms for Generating Amicable Pairs
292(3)
Algorithms for Verifying Goldbach's Conjecture
295(4)
Algorithm for Finding Odd Perfect Numbers
299(1)
Bibliographic Notes and Further Reading
300(3)
Applied Number Theory in Computing/Cryptography
303(112)
Why Applied Number Theory?
303(2)
Computer Systems Design
305(27)
Representing Numbers in Residue Number Systems
305(3)
Fast Computations in Residue Number Systems
308(4)
Residue Computers
312(3)
Complementary Arithmetic
315(2)
Hash Functions
317(4)
Error Detection and Correction Methods
321(5)
Random Number Generation
326(6)
Cryptography and Information Security
332(79)
Introduction
332(1)
Secret-Key Cryptography
333(11)
Data/Advanced Encryption Standard (DES/AES)
344(4)
Public-Key Cryptography
348(6)
Discrete Logarithm Based Cryptosystems
354(4)
RSA Public-Key Cryptosystem
358(15)
Quadratic Residuosity Cryptosystems
373(6)
Elliptic Curve Public-Key Cryptosystems
379(6)
Digital Signatures
385(7)
Digital Signature Standard (DSS)
392(3)
Database Security
395(4)
Secret Sharing
399(4)
Internet/Web Security and Electronic Commerce
403(6)
Steganography
409(1)
Quantum Cryptography
410(1)
Bibliographic Notes and Further Reading
411(4)
Bibliography 415(14)
Index 429

An electronic version of this book is available through VitalSource.

This book is viewable on PC, Mac, iPhone, iPad, iPod Touch, and most smartphones.

By purchasing, you will be able to view this book online, as well as download it, for the chosen number of days.

Digital License

You are licensing a digital product for a set duration. Durations are set forth in the product description, with "Lifetime" typically meaning five (5) years of online access and permanent download to a supported device. All licenses are non-transferable.

More details can be found here.

A downloadable version of this book is available through the eCampus Reader or compatible Adobe readers.

Applications are available on iOS, Android, PC, Mac, and Windows Mobile platforms.

Please view the compatibility matrix prior to purchase.