Tagged Questions
3
votes
1answer
68 views
Why isn't the naive PRIMES algorithm in P?
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 ...
4
votes
2answers
176 views
Is there a function that only generates primes?
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, ...
1
vote
2answers
227 views
Approximating next prime number
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 ...
1
vote
2answers
419 views
Factoring n, where n=pq and p and q are consecutive primes
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 ...
5
votes
1answer
239 views
Can a Pratt certificate for a prime be found in polynomial time?
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. ...
