For $\: 1 < n \:$ and $\: n^{o(1)} < \sigma \leq n \:$, $\:$ how small can $L$ be for there to be for there to be an
efficiently computable (deterministic) function $\;\; f \: : \: \{0\hspace{.01 in},\hspace{-0.03 in}1\}^L \: \to \: \{n\text{-bit primes}\} \cup \{\perp\} \;\;$ and
an efficiently computable randomized algorithm $g$ from $\: \{n\text{-bit primes}\} \:$ to $\: \{0\hspace{.01 in},\hspace{-0.03 in}1\}^L \:$ such that,
for $\: U\in \{0\hspace{.01 in},\hspace{-0.03 in}1\}^L \:$ and $\: p\in \{n\text{-bit primes}\} \:$ uniformly distributed, the statistical distance
between $\:\langle U\hspace{-0.02 in},\hspace{.01 in}f(\hspace{.005 in}U\hspace{.01 in})\rangle\:$ and $\:\langle \hspace{.005 in}g(\hspace{.03 in}p)\hspace{.01 in},p\rangle\:$ is less than $\hspace{.03 in}2^{-\sigma}$ ? $\;$ (Everything is parametrized by $n$.)

This is relevant to cryptography, when using a common random string to specify a prime.

The best I can come up with is, have $p$ be the largest prime such that $\: $$p\hspace{.01 in}\#$$\:< 2^n \:$, use the
Chinese Remainder Theorem and a greedy algorithm to sample from the numbers in $\: \left[2^{n-1},2^n\right) \:$
all of whose non-$1$ factors are larger than $p$, and then test them for primality.
(When one finds a prime, output it. $\:$ If one runs out of randomness instead, then output $\perp$.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy