You can pick a 1024-bit prime more or less uniformly at random by flipping only 256 coins. But there's additional computational cost to it. Here's a naive algorithm that is deterministic after the initial coin flips:
- Flip 256 coins, yielding a bit string $s$.
- Compute $p_0 = \operatorname{SHAKE128-1024}(s) \mathbin| 1$ and interpret it as an integer in little-endian bit order. (The $\cdots \mathbin| 1$ forces it to be odd, saving you the wasted effort of testing a large even number for primality.)
- Compute a primality certificate for $p_0$, such as a Pratt certificate (which requires computing the prime factorization of $p_0 - 1$) or a Pocklington–Lehmer certificate (which requires computing half the prime factorization of $p_0 - 1$, up to a composite factor below $\sqrt{p_0 - 1}$) or an Atkin–Goldwasser–Kilian–Morain elliptic curve primality proof certificate (which requires a ~512-bit prime, and doing some arithmetic on an elliptic curve).
- If it turns out that $p_0$ is composite, then try again with $p_1 = p_0 \pm 2$, and so on. If you hit $2^{1024}$ or $2^{1023}$, you probably made a mistake.
Generating an RSA key.
You can use the same 256-bit seed $s$ to pick both prime factors $p$ and $q$ of an RSA modulus $n$, e.g. by splitting the output of $\operatorname{SHAKE128-2048}(s)$ into two 1024-bit integers $p_0$ and $q_0$ instead of step (2). You will also want to try again with the next candidate if you get $\gcd(e, \operatorname{lcm}(p - 1, q - 1)) \ne 1$, where $e$ is your favorite exponent, which ought to be 3 or 65537 unless you have eclectic taste in exponents.
Efficiency.
There are variations on the theme: you can use trial division to save some work, for instance, or use a fancier faster sequence of trials at small cost to uniformity of the distribution (but be careful or else you might have a billion-euro mistake on your hands).
Obviously, step (3) costs a lot more computation than generating an elliptic-curve scalar uniformly at random, even if you do the rejection sampling necessary to avoid the (negligible) modulo bias. What's the exchange rate between computation and coin flips?
You can save a lot of computation by doing a fast probabilistic primality test first, like 128 independent Rabin tests, which gives reasonably high confidence that you found a prime, but this costs a lot more coin flips.
If you believe in the extended Riemann hypothesis, you could even avoid the additional coin flips and use a deterministic variant, the Miller test (paywall-free), which is named after the person who first republished the novel result of Russian mathematician М.М. Артюхов in English. It might even perform better than finding an ECPP certificate.
Choice of prime vs. primality testing.
All this will take quite a lot of effort with the computational power of pen and paper. But you could write a computer program to do everything past the coin flips in step (1), and feed that computer program the outcomes of your coin flips. Even if it uses a probabilistic primality test, the choice of the prime will be (unless the primality test goes haywire) a deterministic function of the coin flip outcomes.
With a primality certificate, as a bonus you get a verifiable proof that it is prime, which you can independently verify in case a god with a cosmic ray gun angry at your computational arrogance decided to disrupt your faster-than-pen-and-paper computer.
(You might want to keep the certificate secret too.)
