Question

Suppose Algorithm RP is implemented using an imperfect random number generator, so that the statistical distance between the output distribution of the random number generator and the uniform distribution on \(\\{2, \ldots, m\\}\) is equal to \(\delta\) (e.g., Algorithm \(\mathrm{RN}^{\prime}\) in \(\S\) 9.2). Assume that \(2 \delta<\pi(m) /(m-1)\). Also, let \(\mu\) denote the expected number of iterations of the main loop of Algorithm \(\mathrm{RP}\), let \(\Delta\) denote the statistical distance between its output distribution and the uniform distribution on the primes up to \(m,\) and let \(\ell:=\operatorname{len}(m)\). (a) Assuming the primality test is deterministic, show that \(\mu=O(\ell)\) and \(\Delta=O(\delta \ell)\) (b) Assuming the primality test is probabilistic, with one-sided error \(\varepsilon,\) as in \(\S 9.4 .1,\) show that \(\mu=O(\ell)\) and \(\Delta=O((\delta+\varepsilon) \ell) .\)

Short answer

Question: Show the dependence of an algorithm RP's properties (iterations and statistical distance) on the imperfection of the random number generator (\(\delta\)) and the length of the input m (\(\ell\)). Answer: In the deterministic primality test case, the expected number of iterations \(\mu = O(\ell)\) and the statistical distance \(\Delta = O(\delta \ell)\). In the probabilistic primality test case, the expected number of iterations \(\mu = O(\ell)\) and the statistical distance \(\Delta = O((\delta + \varepsilon) \ell)\), where \(\varepsilon\) is the error from the probabilistic primality test.

Step-by-step solution

Expected number of iterations

Since \(2\delta < \frac{\pi(m)}{m-1}\), we know that Algorithm RP has a probability higher than \(\frac{1}{2}\) of choosing a prime number at each iteration. Therefore, the expected number of iterations \(\mu\) is at most \(2\ell\), as after each iteration, the algorithm determines the primality of the number in \(\ell\) time. Hence, \(\mu = O(\ell)\).

Statistical distance

The statistical distance between the output distribution of the primes and the uniform distribution on the primes up to \(m\) is bounded by the statistical distance between the output distribution of the random number generator and the uniform distribution on \(\{2, \ldots, m\}\), which is given as \(\delta\). When we choose a prime number, we do so with probability at most \(2\delta\ell\). Since the primality test is deterministic, there is no additional error in our primality test. Hence, the total statistical distance \(\Delta\) is also bounded by \(2\delta\ell\). Therefore, \(\Delta = O(\delta \ell)\). (b) Probabilistic primality test:

Expected number of iterations

Again, since \(2\delta < \frac{\pi(m)}{m-1}\), Algorithm RP has a probability higher than \(\frac{1}{2}\) of choosing a prime at each iteration. Thus, the expected number of iterations \(\mu\) remains at most \(2\ell\), even with the probabilistic primality test. Hence, \(\mu = O(\ell)\) still holds.

Statistical distance

In the case of the probabilistic primality test, there is an additional error \(\varepsilon\) due to its one-sided error nature. Therefore, the total statistical distance \(\Delta\) is now the sum of the imperfection of the random number generator (\(\delta\)) and the error from the probabilistic primality test (\(\varepsilon\)), multiplied by \(\ell\). The statistical distance between the output distribution and the uniform distribution on the primes up to \(m\) would then be bounded by \((\delta + \varepsilon)\ell\). Hence, \(\Delta = O((\delta + \varepsilon)\ell)\).

Key concepts

Statistical Distance

Statistical distance is a measure of how different two probability distributions are. In the context of algorithms, it helps us understand how closely the output from an imperfect random number generator resembles a perfect uniform distribution.

Imagine two distributions: one from an ideal random number generator and one from an imperfect generator. Statistical distance quantifies the average difference between the outcomes of these two distributions. If the statistical distance is 0, the distributions are identical. A greater statistical distance implies a greater discrepancy.

When running a probabilistic algorithm which includes generating random numbers, a lower statistical distance from the uniform distribution means that the algorithm’s outputs are more predictably close to what they should be. This is crucial because randomness impacts the success rate and efficiency of such algorithms, especially when determining results like the primality of a number.

Primality Test

A primality test is a process employed in algorithms to determine whether a number is prime or not. There are two primary types of primality tests: deterministic and probabilistic.

- **Deterministic Primality Test:** This type of test gives a definitive answer that a number is either prime or composite. It's like having a super accurate checking machine which always gives the correct answer. These tests guarantee accuracy, but they can be slower for very large numbers.

- **Probabilistic Primality Test:** This test doesn't guarantee a definitive answer. Instead, it tells us that a number is prime with a high probability. There might be a small chance of error (often called a one-sided error), making the process faster but slightly less reliable. Such tests are useful when determining primes quickly and are often used in complex algorithms where speed matters.

In the scope of the problem given, when using a deterministic primality test, the outputs are more predictable, but can be slower. When using a probabilistic approach, it's faster but introduces a statistical error, denoted as \(\varepsilon\), which impacts the statistical distance of overall results.

Random Number Generator

A random number generator (RNG) is a tool or algorithm used to produce numbers that lack any pattern, seeming random to an observer. These numbers are critical for algorithms that rely on randomness.

There are two types of random number generators:

• **True Random Number Generators (TRNG):** Use physical processes to generate randomness. They are highly unpredictable, often generated from natural activities like radioactive decay.
• **Pseudo-random Number Generators (PRNG):** Use mathematical formulas or algorithms to produce sequences of numbers that only appear random. While faster, they aren't truly random and can have imperfections.

An imperfect RNG, as referred to in the problem, might produce a sequence with noticeable patterns, causing deviation in statistical distance from a perfect uniform distribution. This imperfection can affect the performance of algorithms, influencing aspects like the unpredictability needed when selecting numbers for functions like a primality test. Hence, understanding the quality and behavior of the RNG employed in any algorithm is crucial for predicting its outcomes accurately.