HTW Berlin Fachbereich 4 Internationaler Studiengang Internationale Medieninformatik (Bachelor) Aktuelles - Medien: Kryptographie Winter Term 2010/11

Lab 9: Prime Numbers

1. How can you tell if a number is prime? Remember the method you programmed in Informatik 2. Are there other ways? How fast are they?
2. How can you find a prime number? Let's say you need a 65-bit prime number. How can you go about finding one? Set up a little program in your favorite programming language to generate two 65-bit prime numbers, let's call them p and q!
3. How can you multiply p and q? Let's call that n. Can your favorite programming language do that? If not, maybe you need to use a different programming language! Or is there some solution other than programming the arithmetic yourself? Multiply your two numbers from exercise 2!
4. Now choose two numbers, x and y, that are less than n. Write them down in the CRT-representation - as a pair, for example (x mod p, x mod q). Now find the CRT representation for x*y.
5. (For the bored) Find the CRT representation for x^y!