Understand an algorithm to find a prime of bit length $k$

40 Views Asked by At

My cryptography notes gives this algorithm for finding a prime of bit-length larger than or equal to $k$.

  1. Determine an optimal bound on the set of small primes to be sieved $(2,3,...,p_t)$ and let $M=(2)(3)...p_t$.
  2. Generate a random integer $x$ whose bitlength is $k$ and locate, using the Chinese Remainder theorem, the smallest integer $x_1$ larger than $x$ which is co-prime to $M$.
  3. Perform an incremental search for primes in the set $x_1, x_1+M, x_1+2M$.

I have two questions

  1. How do you find the smallest integer $x_1>x$ using the Chinese remainder theorem that is co-prime to $M$.

  2. Why is it true that any of the integers in $(x_1, x_1+M$) are sieved. How do we know none of them are primes?

Thanks.