We have seen that, if p is an odd prime number, then exactly half of the numbers 1,2,3,...,p-1 are quadratic residues modulo p. Many questions in number theory, including issues related to the running time of primality testing algorithms, relate to how exactly the quadratic residues distribute themselves among these p-1 numbers.
Of particular interest in many contexts is the value of the least nonresidue, which is the smallest positive number that is not a quadratic residues modulo p. The conventional wisdom is that the first nonresidue tends to be very small (with order of magnitude close to the number of digits of p). This should be plausible: if half of the numbers from 1 to p-1 are nonresidues, then it shouldn't take long to encounter one. However, the question of exactly how long you might have to wait to find a nonresidue remains elusive, and is related to several topics of modern research.
The goal of this task is to write a program to gather experimental data about this question. Your program will receive an interval (a range of numbers), and find the largest possible value for the least nonresidue for all primes in this interval.
The first line gives the number of test cases, T. T test cases follow. Each case consists of a single line with two integers p_min p_max, which gives the upper and lower bounds for the interval of numbers in question.
For each test case, output one line of the form "Case #X: L P". X is the case number (starting from 1). L is the largest possible value of the least nonresidue modulo a prime chosen between p_min and p_max, inclusive. P is the prime number from the interval that achieves this maximum. If there is a tie, i.e. multiple prime numbers in the interval have least nonresidue L, then P should be the smallest one.
Small dataset:
p_max ≤ 106
p_max ≤ p_min+100
Large dataset:
p_max ≤ 1018
p_max ≤ p_min+104
| Input | Output |
|
4 3 7 97 97 3 100 10000 20000 |
Case #1: 3 7 Case #2: 5 97 Case #3: 7 71 Case #4: 29 18191 |
Note in particular that the ends of the interval are inclusive. For example, in case 2, 97 is the only number in the interval (and it is prime).
For the small input, you can write a program which first identifies primes (for example, by checking for divisors up to the square root of each number), and then explicitly lists the quadratic residues of each prime in the specified interval.
To complete the large input, you'll need two ingredients: an efficient way to detect primes (such as the Miller-Rabin test), and an efficient way to compute the Legendre symbol (I suggest making using of quadratic reciprocity).