You basically have two computational options, both with drawbacks. You could use randomness and find one by guessing, but the method is inconsistent — you run the risk of generating a different prime every time. Or you could use a more reliable, deterministic algorithm, but at a heavy computational cost.
If you use a pseudorandom number generator and fix the seed, then you get a deterministic result. But I guess we can not prove that replacing random numbers with pseudorandom ones does not alter the behavior of the algorithm. So they came up with something clever where they use true random numbers to find a primes and are able to proof this while at the same time mostly canceling out the effect of the random numbers used so that the prime number they get pack is the same every time with high probability. Or am I misunderstanding the article?