Multiple Choice Question
1. Using fast modular exponentiation, how many operations (squaring and mod count as one
operation) does it take to compute 112580 mod 19?
d. 2500 e. 112580
Free Response Questions
2. True or false? If the statement is true, give an explanation. If it is false, give a
"Iffi(x) is of order g(x), and f2(x) is of order g(x), then f1(x) + f2(x) is of order
3. Compute 3 1048576 mod 7 using fast modular exponentiation. Hint: 1048576=2
Show all your steps.
4. Find the prime factorization of 216 - 1. (A mere calculator solution based on
evaluation of 216 - 1 is unacceptable. Hint: factor the expression.)
5. Prove: if n is a natural number, then 22n - 1 must be divisible by
6. Given the base-k expansion of a natural number n, how can we tell whether n is
k? You must prove your answer, based on the definition of base-k expansion.
7. In the lectures, we discussed an algorithm for primality testing. For testing whether a
natural number n is prime, the number of trial divisions needed for this algorithm is
of order n° for some real number p. Determine pand explain your answer. You do
not need to give an exact inequality- based proof based on the definition of order.
Using reasonable approximations is enough.
This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.