To derive a certificate from this theorem, we first encode M"x", M"y", A, B, and "q", then recursively encode the proof of primality for "q" < "n", continuing until we reach a known prime. This certificate has size O((log "n")2) and can be verified in O((log "n")4) time. Moreover, the algorithm that generates these certificates can be shown to be expected polynomial time for all but a small fraction of primes, and this fraction exponentially decreases with the size of the primes. Consequently, it's well-suited to generating certified large random primes, an application that is important in cryptography applications such as generating provably valid RSA keys.