A computational introduction to number theory and algebra by Victor Shoup

By Victor Shoup

Quantity conception and algebra play an more and more major function in computing and communications, as evidenced via the remarkable functions of those topics to such fields as cryptography and coding conception. This introductory publication emphasises algorithms and purposes, comparable to cryptography and blunder correcting codes, and is out there to a extensive viewers. The mathematical necessities are minimum: not anything past fabric in a regular undergraduate direction in calculus is presumed, except a few adventure in doing proofs - every thing else is constructed from scratch. therefore the e-book can serve numerous reasons. it may be used as a reference and for self-study via readers who are looking to examine the mathematical foundations of contemporary cryptography. it's also excellent as a textbook for introductory classes in quantity idea and algebra, specially these geared in the direction of desktop technology scholars.

Show description

Read or Download A computational introduction to number theory and algebra PDF

Similar number theory books

The Atiyah-Patodi-Singer Index Theorem

According to the lecture notes of a graduate direction given at MIT, this refined remedy ends up in quite a few present examine issues and may absolutely function a consultant to additional reports.

Zero to Lazy Eight: The Romance Numbers

Did you ever ask yourself why a sew in time saves 9 and never, say, 4, or why the quantity seven is taken into account the luckiest, or what percentage the observe googol refers to? good, the Humez brothers, besides Joseph Maguire, have replied all of those questions and extra. In "Zero to Lazy Eight", they take us on a wacky and enlightening journey up the linguistic quantity scale from 0 to 13 and again when it comes to infinity, displaying us simply what numbers can let us know approximately our culture's earlier, current, and destiny.

Additional resources for A computational introduction to number theory and algebra

Sample text

Q , where ≥ 0, as follows: +1 , r0 = a, r1 = b, r0 = r 1 q1 + r 2 .. (0 < r2 < r1 ), ri−1 = ri qi + ri+1 .. r r −2 −1 = r −1 q −1 = rq (r (0 < ri+1 < ri ), +r +1 (0 < r < r = 0). Then√r = gcd(a, b). 62, and if b = 0, then = 0. 1. The Basic Euclidean Algorithm 41 Proof. For the first statement, one sees that for 1 ≤ i ≤ , the common divisors of ri−1 and ri are the same as the common divisors of ri and ri+1 , and hence gcd(ri−1 , ri ) = gcd(ri , ri+1 ). From this, it follows that gcd(a, b) = gcd(r0 , r1 ) = gcd(r , 0) = r .

N − 1}, we can determine if [a mod n] has a multiplicative inverse in Zn , and if so, determine this inverse, in time O(len(n)2 ), as follows. We run the extended Euclidean algorithm on input (n, a) to determine integers d, s, and t, such that d = gcd(n, a) and ns + at = d. If d = 1, then [a mod n] is not invertible; otherwise, [a mod n] is invertible, and [t mod n] is its inverse. 5, we know that |t| ≤ n; we cannot have t = ±n, and so either t ∈ {0, . . , n − 1}, or t + n ∈ {0, . . , n − 1}.

For example, the product of all primes of at most 16 bits is a number that has more than 90, 000 bits. Thus, by simply pre-computing and storing such a table of small primes, we can handle input matrices with quite large entries (up to about 45, 000 bits). Let us assume that we have pre-computed appropriate small primes n1 , . . , nk . Further, we shall assume that addition and multiplication modulo any of the ni ’s can be done in constant time. This is reasonable, both from a practical and theoretical point of view, since such primes easily “fit” into a memory cell.

Download PDF sample

Rated 4.48 of 5 – based on 38 votes