HTW Berlin Fachbereich 4 Internationaler Studiengang Internationale Medieninformatik (Bachelor) Aktuelle Themen: Cryptography Winter Term 2024/25

Lab 9: Rabin-Miller Programming

1. Given natural numbers a and n, show that n can not be pseudoprime with respect to a if gcd(a, n) ≠ 1.
2. Find a counterexample for the converse of Fermat´s Theorem: Find natural numbers a and n with 1 < a < n-1, such that a^n-1 ≣ 1mod n where n ist not prime.
3. Implement the Rabin-Miller-Algorithm; you can find pseudocode in Moodle. Test by comparing your implementation with Java´s isProbablePrime. How many numbers less then 1.000.000 will your implementation test as prime? Try several parameters for k.
4. Find a composite 32-bit-number that will be tested as prime in one (k=1) round of the Rabin-Miller-Test.
5. Find a random 512-bit-pseudoprime with your implementation of the Rabin-Miller-Algorithm. How many numbers did you have to test?

Your report is due by 22:00 the night before your next lab!