I am looking for ways to construct a prime without resorting to primality test. That can be an algorithm which would generate a prime from an arbitrary number or some defined set of inputs. For example I believe the following to be a valid answer: inputs:     p: prime > 3    q: prime &lt; p    L: list of odd primes up to p (inclusive) output: prime > p, or 1 algorithm:    prod = product of all numbers in L    c = p*q-2    while(gcd(prod,c)!=1)       c = c/gcd(prod,c)    return c   p*q-2 maybe prime or composite. If it is prime, it is greater than p and gcd(prod,c)=1, we have our result right away.  If it is composite, either it has a factor greater than p or it is a power of a prime &lt; p. In the latter case the algorithm returns 1, which is kind of failing to answer the question however this could be fixed by changing q for another prime from L. (although I have no proof that such a variant would find a new prime for any value of p)  This example is hardly useful in practice, I am wondering what other methods exists. Note that in this example the result is a "larger" prime: the result is larger than all primes given as inputs. This is not a requirement and I would be interested to get reference for algorithm constructing a "different" prime, no matter if it is smaller or larger than whatever is the input.
70464
Is the below formula for the $n^{th}$ prime number in elementary functions useful somehow?  $$p(n)=\sum _{a=2}^{2^n} \sin \left(\pi  2^{\left(n-\sum _{b=2}^a \frac{\sin ^2\left(\frac{\pi }{b}((b-1)!)^2\right)}{\sin ^2\left(\frac{\pi }{b}\right)}\right)^2-1}\right)\frac{a \sin ^2\left(\frac{\pi }{a} ((a-1)!)^2\right) }{\sin ^2\left(\frac{\pi }{a}\right)}.$$
59037
I am a bit of a newbie to RSA encryption, so please be patient.  I understand that for a 4096 bit RSA, the numbers p and q should be prime. And to have the best security, the p and q should both be about 2048 bits long.  However, we don't have a way of generating and verifying a 2048 bit prime number with 100% accuracy. The implementation for prime generation that gpg uses goes through 64 rounds of miller-rabin which is enough to give a prime probability of $1 - 2^{-128}$.  Given that these primes are only probabalistically prime, what happens if we selected composite values for p or q?  Does the RSA algo run into any sort of problem?  My guess is that there will be no problem and RSA continues to function normally (encryption and decryption both) because, if there was a problem, we could use that problem as a way to detect that the numbers are not prime. This would give us a really fast way to verify extremely large prime numbers. I am guessing this is not the case.  So, my conclusion is that RSA works with prime or composite p, q... but using composite p, q makes it easy to break the encryption (because its easier to derive p, q from n).  Is this conclusion correct?
13882
It is possible to find an efficient algorithm for constructing a provably hard to factor number $N$, together with a witness that shows that it is indeed hard to factor. EDIT, since it was not clear: I also want to be sure that even the person that constructed the number cannot factor it.  Of course, a random large enough integer is going to be hard to factor with high probability, but we might be unlucky.  There are also multi-party protocols for shared generation of RSA moduli (such as ), but I would like a non interactive technique.  Motivation: This was suggested by Poncho's answer to
68102
I have thought a lot but am failing to arrive at anything encouraging.   First try: If this is to be proved by contradiction, then I start with the assumption that let $n$ be a number which is a sum of two numbers, of which at least one is prime. This gives $n = p + c$, where $p$ is the prime number and $c$ is the composite number. Also, any composite number can be written as a product of primes. So I can say, $n = p + p_1^{e_1}.p_2^{e_2}...p_k^{e_k}$. From this, I get $n - p = p_1^{e_1}.p_2^{e_2}...p_k^{e_k}$, but I have no clue what to do next.  Second try: For an instant let me forget about contradiction. Since $n &gt; 11$, I can say that $n \geq 12$. This means that either $p \geq 6$ or $c \geq 6$. Again I'm not sure what to do next.  Finally, consider that the number 20 can be expressed in three different ways: $17+3$ (both prime), $16+4$ (both composite), and $18+2$ (one prime and one composite). This makes me wonder what we are trying to prove.  The textbook contains a hint, "Can all three of $n-4$, $n-6$, $n-8$ be prime?", but I'm sure what's so special about $4, 6, 8$ here.
66345
Prove that $\forall n \in \mathbb{N}^*, P_n \lt 4^n$ where $P_n$ is the $n$th prime number. I'm searching for a proof that doesn't use induction and uses only the elementary concepts of number theory.  This theorem appears in an old french book on Arithmetics destined to high school level students (lycée). It is introduced right after the concept of decomposition into prime factors. The book includes a proof that I didn't understand. You can see below a screenshot taken from the book and a translation attempt.   Theorem For all integers $n \gt0,$ the $nth$ prime number $q$ verifies the inequality $q \lt 4^n$.   Demonstration The $[1,q]$ interval is included in the set of integers $k$ that can be written, (after grouping all the squares that can be formed with the $n$ prime numbers $p_i  \le q $ in a decomposition of $k$), as $k = m^2p_1^{e_1}p_2^{e_2}...p_n^{e_n}$ with $e_i \in {0,1}$. (Here, $p_i$ is the i-th prime number, and $p_n = q$.). There are no more than $\sqrt{q}$ integers like m, and at most $2^n$ choices for the exponents $e_i$, what shows that $q$, cardinal of this set, is strictly lower than the product $2^n\sqrt{q}$, then the result.
89223
Given the prime factorization of $N$, is there a known method for computing the prime factorization of $N-1$ or $N+1$, which is more efficient than the best known method for doing that without it?  I assume that the factors of $N$ can be "skipped" while searching for the factors of $N-1$ or $N+1$, but I don't see how it can improve the general case performance (i.e., for any given value of $N$).  UPDATE:  This question can also be stated as follows: is there a known method for computing the prime factorization of $N$, given the prime factorization of either one of its neighbors (which is more efficient than the best known method for doing that without it)?
106565
I'm refreshing some algebra and in the beginning chapters of my book I'm presented with the following simple looking problem that I got stuck on:      Prove or disprove: If $n$ is a positive integer, then $n=p+a^2$, where $a$ is an integer and $p$ is prime or $p=1$.   At first I thought $n=13$ would give a nice counterexample, but then I noticed my book defines primes to include the negative primes. Now $13=-3+4^2$ is a solution.   I am allowed to use the fundamental theorem of arithmetic and the division and euclidean algorithms. I tried to express $n$ and $a$ by their prime factorizations, but I didn't get anywhere from there. I would like a hint which direction to take. Am I just missing something silly?
112393
Prove that if $p$ is a prime of the form $3n+1$, $p$ is also of the form $6m+1$.  I guess one could use the division algorithm for this; but, what's the best method?
30523
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 consecutive primes is the only information to work off of. Also would Fermat's factorization be an efficient way to factor such an n?  edit: I'n not actually trying to factor n or find p and q. I just want to know if Fermat's factorization method would be efficient given this information.
4565
I'm trying to figure out how to prove that if $p$ and $p^2+2$ are prime numbers then $p^3+2$ is a prime number too. Can someone help me please?
119648
I know the definition of prime number when dealing with integers, but I can't understand why the following definition also works:     A prime is a quantity $p$ such that whenever $p$ is a factor of some product $a\cdot b$, then either $p$ is a factor of $a$ or $p$ is a factor of $b$.   For example, take $4$ (which clearly is not a prime): it is a factor of $16=8\cdot 2$, so I should check that either $4\mid 8$ or $4\mid 2$. But $4\mid 8$ is true. So $4$ is a prime, which is absurd.  Please note that English is not my first language, so I may have easily misunderstood the above definition.  Edit: Let me try formalize the definition as I understood it: $p$ is prime if and only if $\exists a\exists b(p\mid a\cdot b)\rightarrow p\mid a\lor p\mid b$.
80099
How would you find a primitive root of a prime number such as 761? How do you pick the primitive roots to test? Randomly?  Thanks
100126
I am going through the problems from Project Euler and I notice a strong insistence on Primes and efficient algorithms to compute large primes efficiently.   The problems are interesting per se, but I am still wondering what the real-world applications of primes would be.   What real tasks require the use of prime numbers?    Edit: A bit more context to the question: I am trying to improve myself as a programmer, and having learned a few good algorithms for calculating primes, I am trying to figure out where I could apply them.   The explanations concerning cryptography are great, but is there nothing else that primes can be used for?
80634
I'm asked to find all integers $n$ such that $\phi(n)+\sigma(n)=2n.$ I know that when $n$ is a prime, $\phi(n)+\sigma(n)=(n-1)+(n+1)=2n.$ My guess is that $n$ can be primes only, and I want to derive a contradiction when $n$ is a composite number. But I can only show that when $n=pq$ ($p$, $q$ distinct primes), $\phi(n)+\sigma(n)=2pq+2=2n+2.$ How do I generalize from here?
6868
Show that if the smallest prime factor $p$ of the positive integer $n$ exceeds $\sqrt[3]{n}$, then $\frac{n}{p}$ must be prime or 1.  I'm stuck trying to prove this. I tried this using contradiction, but I haven't been able to prove it.  My approach:  Let $p$ be the smallest prime factor of the positive integer $n$.  Let $p &gt; \sqrt[3]{n}$  Then we must show that $\frac{n}{p}$ is either a prime number or 1.  We know that $n = pe$ for some $e \in \mathbb{Z}$.  Thus, $\frac{n}{p} = e$  We also know that $p$ > $\sqrt[3]{n}$, so $p^3 &gt; n$, and $p^2 &gt; \frac{n}{p}$  So, assume $\frac{n}{p} = e$ is not prime nor 1, meaning it's a composite number. Let's try to get a contradiction.  If $\frac{n}{p}$ is composite, then $\exists a,b \neq 1: \frac{n}{p} = ab $  Now, here's where I get stuck. What can I do with this info? $\frac{n}{p} = ab $ and $p^2 &gt; \frac{n}{p}$.
75474
In Euclid's proof that there are infinitely many primes, the number  $p_1 p_2 ... p_n + 1$ is constructed and proved to be either a prime, or a product of primes greater than $p_n$.  Trivially, we could also use the number $R_n=p_1 p_2 ... p_n - 1$ to prove the theorem, for n>2.  Intuitively, as $n$ grows, the probability that $R_n$ is prime gets smaller. Is there a proof that $R_n$ is not prime for any $n$ greater than some integer $M$ ? Or conversely, that there is an infinite number of prime $R_n$ numbers?  A possibly equivalent question: Is there a prime number greater than $p_n$ and smaller than $R_n$ for any $n$ greater than some integer $M$ ?
84012
I need help with this question: There are infinitely many prime numbers $p$ for which $p + 2$ and $p + 4$ are also primes.  Where should I start? what proof techniques will be useful?  Any input will be very useful to me.