For $\: 1 < n \:$ and $\: n^{o(1)} < \sigma \leq n \:$, $\:$ how small can $L$ be for there to be for there to be anefficiently computable (deterministic) function $\;\; f \: : \: \{0\hspace{.01 in},\hspace{-0.03 in}1\}^L \: \to \: \{n\text{-bit primes}\} \cup \{\perp\} \;\;$  andan 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 distancebetween $\:\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 theChinese 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$.)
How short can reversible representations of the n-bit primes be?
cr.crypto security;randomness;comp number theory