Page 331 - Discrete Mathematics and Its Applications

310 4 / Number Theory and Cryptography

Computations and Explorations

Use a computational program or programs you have written to do these exercises.

p
1. Determine whether 2 − 1 is prime for each of the primes 6. Find 10 different primes each with 100 digits.
not exceeding 100. 7. How many primes are there less than 1,000,000, less than
p
2. Test a range of large Mersenne numbers 2 − 1tode- 10,000,000, and less than 100,000,000? Can you propose
termine whether they are prime. (You may want to use an estimate for the number of primes less than x where x
software from the GIMPS project.) is a positive integer?
3. Determine whether Q n = p 1 p 2 ··· p n + 1 is prime 8. Find a prime factor of each of 10 different 20-digit odd
where p 1 , p 2 ,...,p n are the n smallest primes, for as integers, selected at random. Keep track of how long it
many positive integer n as possible. takes to find a factor of each of these integers. Do the
4. Look for polynomials in one variables whose values at same thing for 10 different 30-digit odd integers, 10 dif-
long runs of consecutive integers are all primes. ferent 40-digit odd integers, and so on, continuing as long
2
5. Find as many primes of the form n + 1 where n is a pos- as possible.
itive integer as you can. It is not known whether there are 9. Find all pseudoprimes to the base 2 that do not exceed
infinitely many such primes. 10,000.

Writing Projects

Respond to these with essays using outside sources.

1. Describe the Lucas–Lehmer test for determining whether 8. Explain how a check digit is found for an International
a Mersenne number is prime. Discuss the progress of the Bank Account Number (IBAN) and discuss the types of
GIMPS project in finding Mersenne primes using this test. errors that can be found using this check digit.
2. Explain how probabilistic primality tests are used in prac- 9. Describe the Luhn algorithm for finding the check digit
tice to produce extremely large numbers that are almost of a credit card number and discuss the types of errors
certainly prime. Do such tests have any potential draw- that can found using this check digit.
backs? 10. Show how a congruence can be used to tell the day of the
3. The question of whether there are infinitely many week for any given date.
Carmichael numbers was solved recently after being open 11. Describe how public key cryptography is being applied.
for more than 75 years. Describe the ingredients that went Are the ways it is applied secure given the status of fac-
into the proof that there are infinitely many such numbers. toring algorithms? Will information kept secure using
4. Summarize the current status of factoring algorithms in public key cryptography become insecure in the future?
terms of their complexity and the size of numbers that can 12. Describe how public key cryptography can be used to
currently be factored. When do you think that it will be produce signed secret messages so that the recipient is
feasible to factor 200-digit numbers? relatively sure the message was sent by the person ex-
5. Describe the algorithms that are actually used by modern pected to have sent it.
computers to add, subtract, multiply, and divide positive 13. Describe the Rabin public key cryptosystem, explaining
integers. how to encrypt and how to decrypt messages and why it
6. Describe the history of the Chinese remainder theorem. is suitable for use as a public key cryptosystem.
Describe some of the relevant problems posed in Chi- ∗ 14. Explain why it would not be suitable to use p, where
nese and Hindu writings and how the Chinese remainder p is a large prime, as the modulus for encryption in the
theorem applies to them. RSA cryptosystem. That is, explain how someone could,
7. When are the numbers of a sequence truly random num- without excessive computation, find a private key from
bers, and not pseudorandom? What shortcomings have the corresponding public key if the modulus were a large
been observed in simulations and experiments in which prime, rather than the product of two large primes.
pseudorandom numbers have been used? What are the 15. Explain what is meant by a cryptographic hash function?
properties that pseudorandom numbers can have that ran- What are the important properties such a function must
dom numbers should not have? have?