Question

14. Yoni decides to run the Miller-Rabin algorithm to test whether 3121 is prime (he wasn't paying attention in lectures otherwise he'd know that it is!). Laurel watches on with some amusement as Yoni tries every possible value for a (he is nothing if not persistent). Each time Yoni uses fast-exponentiation, Laurel writes down the value that d has at the end of the FOR loop for 8. When Yoni is finished, Laurel tells him that she has only written down 16 numbers. She invites Yoni to explain why she knew ahead of time that there would be (at most) 16 numbers on her list, but he is too exhausted to comprehend. Explain to him why Laurel knew what she did. Hint: 16 is the magic number here. In particular, you may find the proof of Theorem 16 useful.

Answer 1

Soluton: Cy Given inlegor n=31 al. 、 . a1.631 5-1.63 s.63 53 63 fr( a 스 1.to 31