A Friendly Introduction to Number Theory is an introductory undergraduate text designed to entice non-math majors into learning some mathematics, while at the same time teaching them how to think mathematically. The exposition is informal, with a wealth of numerical examples that are analyzed for patterns and used to make conjectures. Only then are theorems proved, with the emphasis on methods of proof rather than on specific results. Starting with nothing more than basic high school algebra, the reader is gradually led to the point of producing their own conjectures and proofs, as well as getting some glimpses at the frontiers of current mathematical research.
Instructors:
To receive an evaluation copy of
A Friendly Introduction to Number Theory, send an email request to:
Evan St Cyr at Pearson.
Please include your title and full mailing address.
Click on the links for the following material.
Errata for the 4th edition. (Errata for the 3rd edition is also available.) |
Exercise 18.4
Here are two longer messages to decode if you like to use
computers.
(a) You have been sent the following message:
5272281348, 21089283929, 3117723025, 26844144908, 22890519533,
26945939925, 27395704341, 2253724391, 1481682985, 2163791130,
13583590307, 5838404872, 12165330281, 28372578777, 7536755222.
It has been encoded using
p = 187963, q = 163841, m = pq = 30796045883, and k = 48611.
Decode the message.
(b) You intercept the following message, which you know has been encoded using the modulusm = 956331992007843552652604425031376690367 and exponent k = 12398737.
Break the code and decipher the message.
821566670681253393182493050080875560504,
87074173129046399720949786958511391052,
552100909946781566365272088688468880029,
491078995197839451033115784866534122828,
172219665767314444215921020847762293421.
Exercise 18.7
Write a computer program implementing one of the factorization methods
that you studied in the previous exercise, such as
Pollard's ρ method, Pollard's p-1 method, or the
quadratic sieve. Use your program to factor the following numbers.
(a) 47386483629775753
(b) 1834729514979351371768185745442640443774091
Exercise 19.8
Program the Rabin-Miller test with multiprecision integers and use
it to investigate which of the following numbers are composite.
(a) 155196355420821961
(b) 155196355420821889
(c) 285707540662569884530199015485750433489
(d) 285707540662569884530199015485751094149
Exercise 22.7
For this exercise, use the ElGamal cryptosystem described in
Exercise 22.6.
(a)
Bob wants to use Alice's public key a = 22695 for
the prime p = 163841 and base
g = 3 to send her the message
m = 39828. He chooses to use the random number
r = 129381. Compute the encrypted message
(e_{1},e_{2}) he should send to
Alice.
(b)
Suppose that Bob sends the same message to Alice, but he chooses a
different value for r. Will the encrypted message be the same?
(c)
Alice has chosen the secret key k = 278374 for the
prime p = 380803 and the base g = 2.
She receives a message (consisting of three message blocks)
(61745, 206881), (255836, 314674), (108147, 350768)
from Bob. Decrypt the message and convert it to letters using the number-to-letter conversion table in Chapter 18.
Return to
Top of Page.
Go to
J.H. Silverman's Home Page
.