networking

Solution/Answers.pdf
Questions
Q1 How to find big primes p and q?
1. prime number is a positive integer, greater than 1, that has only
two positive divisors: 1 and itself.
2. Here are the first prime numbers:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, ..
There is an infinity of prime numbers ! But as we are going to see,
big prime numbers are hard to find.
3. But big primes numbers are useful for some applications, like
cryptography.
4. The security of several public-key cryptography algorithms is
based on the fact that big prime numbers are hard to find.
A well known example is the RSA algorithm. During the key
generation step, you have to choose 2 primes, p and q, and
calculate their product, n = p*q. The security of RSA is based on
the fact that it’s very hard to find p and q given n.
5. Of course, the bigger p and q are, the harder it is to find them
given n.

Q2 How to compute gcd?
A simple solution is to find all prime factors of both numbers, then
find intersection of all factors present in both numbers. Finally return
product of elements in the intersection.
https://www.geeksforgeeks.org/print-all-prime-factors-of-a-given-number/
An efficient solution is to use Euclidean algorithm which is the main
algorithm used for this purpose. The idea is, GCD of two numbers
doesn’t change if smaller number is subtracted from a bigger number.
Q3 How to find mod inverse?
A naive method of finding a modular inverse for A (mod C) is:
step 1. Calculate A * B mod C for B values 0 through C-1
step 2. The modular inverse of A mod C is the B value that makes A *
B mod C = 1
Note that the...