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

Lab 4: Chinese Remainder Theorem

The exercises this week have to do with applications of the Chinese Remainder Theorem.

1. Six professors begin courses of lectures on Monday, Tuesday, Wednesday, Thursday, Friday, and Saturday, and announce their intentions of lecturing at intervals of two, three, four, one, six, and five days respectively. The regulations of the university forbids Sunday lectures (so that a Sunday lecture must be omitted). When first will all six professors find themselves compelled to omit a lecture together?
2. Program a method to use the extended Euclidean algorithm for calculating the GCD of two numbers a and b. The result will be the gcd, and two values u and v such that ua + vb = gcd.
3. Given are a, b, p, and q with p and q different prime numbers, a and b any two integers. Write a small program that calulates the following values:
   
   1. Determine a solution z for qz ≡ 1 mod p
   2. Compute y ≡ (a - b)z mod p
   3. Determine x = yq + b

You may work in groups of two and submit the same report for both persons. The report is due the evening before the next lecture at 22.00!