Chapter 8 Number Theory224
k-bit pieces, using the hardware to perform the additions and multiplications on
the pieces, and then reassembling thek-bit results into ann-bit answer after each
operation. SupposeNwas a product ofmrelatively primek-bit numbers.
Explain how the General Chinese Remainder Theorem offers a far more efficient
approach to performing the required operations.
Exam Problems
Problem 8.20.
Find the remainder of 261818181 divided by 297 .Hint: 1818181 D.18010101/C
1 ; Euler’s theorem
Problem 8.21.
Find an integerk > 1such thatnandnkagree in their last three digits whenevern
is divisible by neither 2 nor 5.Hint:Euler’s theorem.
Problems for Section 8.9
Class Problems
Problem 8.22.
Let’s try out RSA!
(a)As a team, go through thebeforehandsteps.Choose primespandqto be relatively small, say in the range 10-40. In
practice,pandqmight contain several hundred digits, but small numbers are
easier to handle with pencil and paper.
TryeD3;5;7;:::until you find something that works. Use Euclid’s algo-
rithm to compute the gcd.
Findd(using the Pulverizer or Euler’s Theorem).When you’re done, put your public key on the board. This lets another team send
you a message.
(b)Now send an encrypted message to another team using their public key. Select
your messagemfrom the codebook below:
2 = Greetings and salutations!
3 = Yo, wassup?
4 = You guys are slow!