Cryptography/Python: Derive the secret using Quadratic Residue knowledge

This is straightforward assignment to derive secret using Quadratic Residue knowledge. Formula: c = (s ^ r) mod p - s is the secret (an integer) to be encrypted using above formula - r is a random 500-bit number - p is a random 500-bit prime number - c is the ciphertext computed using this formula Above design is vulnerable, because attacker can calculate the value of s if he/she got enough pairs of <c, p> values. There are 3 tasks: Part 1: Later, I will provide a text file of 30 groups of <c, p> values. We only know s is an integer in the interval of [2410, 2459], but do not know which value is it. The mission is to write a Python program to derive the value of s, using those 30 groups of <c, p> values as inputs. Remarks: 1. Hint: you MUST use the knowledge of Quadratic residue. I can provide some reference to explain Quadratic residue if you need. 2. I can provide a short and simple Python code that how c, r, and p are generated. 3. This is not a brute force mission. You cannot simply compute the values from 2410 to 2459 and compare the outputs. 4. After last, write a concise and clear summary of algorithm at comment or in a separate file. Part 2: In part 1, the 30 random r’s were chosen so that s can be identified. Actually, if the 30 r’s are chosen uniformly and randomly, then there is a chance that we cannot uniquely identify s using 30 tuples. The probability of successful identification increases with large number of <c, p> tuples. Based on part 1, the mission is to give the least number of tuples required in order to achieve 99% of success, and explain it. You can write down the answer analytically without writing a new code. Part 3: Same as part 2, but the interval size of s increases into 10^6. The mission is still to write down the answer analytically.