How does Python's pycrypto library generate primes? The pycrypto library in Python can generate random n-bit prime numbers. The syntax I use is as follows:
from Crypto.Util import number
number.getPrime(2048)

The above function has a very impressive performance and returns primes with a very small delay. What is the process used to generate such large primes in such short time periods in this function?
The documentation is not directly telling the implemented algorithm. One can check from the source code. getPrime uses isPrime and that calls the Rabin-Miller Primality test. 


getPrime generates a random odd number $\texttt{N}$ and calls isPrime

number=getRandomNBitInteger(N, randfunc) | 1
     while (not isPrime(number, randfunc=randfunc)):
         number=number+2

isPrime first checks for evenness and for pre-calculated Sieve primes, that list is the first 10000 primes. It may be a prime in the Sieve or divisible by one of them. If none of the cases, then the Rabin-Miller test is performed.


The Probability: The returned value of getPrime, if a probable prime, then the probability is given by
$$ 1 - \frac{1}{4^k}$$ where $k$ is the number of iterations.

The Number of iterations: The Library defines  

false_positive_prob=1e-6


calculates the $k$ by 

k = int(math.ceil(-math.log(false_positive_prob)/math.log(4)))


and from this, the number of iteration in the library is $k=10$.

Note that In my undergraduate, we used $k=20$. That makes false positive in the worst case 1e-12 where the library has 1e-6.

The Complexity: If modular exponentiation by repeated squaring is used then the complexity is $\mathcal{O}(k \log^3 n)$ where $k$ is the number of iterations to test that determines the probability.