The naive algorithm tries dividing $n$ by $2 \dots n-1$ to see if it divides without a remainder. Each division can be done in $O(n)$-time and there are $O(n)$ divisions to be made. What's wrong with ...
The title sums it up: does there exist a "nice" injective function $f(n)$ such that $f(n)\in\mathbb P$ for all $n\in\mathbb N$? I'm having difficulty specifying exactly what I want "nice" to mean, ...
Suppose that there is a prime number. Now I want to approximate the next prime number. (It does not have to be exact.) What would be the time-efficient way to do this? Edit: what happens if we limit ...
So in RSA, there is a modulus n which is the product of two primes. My question is regarding when p and q are consecutive primes, what would the time complexity be? So, n=pq and p and q are ...
Can a Pratt certificate for a prime be found in polynomial time? I guess this is the same as asking whether the AKS primality test provides extra information that allows $p-1$ to be factored quickly. ...