9
$\begingroup$

What would be the immediate implications for Math (or sciences as a general) if someone developed a formula capable of generating every prime number progressively and perfectly, also able to prove (or disprove) the primality of every N-th number. I know this is a very large and subjective answer, however, I would like to know some of these implications - like the breaking of many security systems based on the primes. Moreover, there are examples of practical Math's implication, not just theoretical, of a possible prime number formula discovery? There is for example in Physics, Chemistry, Geography or Astronomy any field which would be very improved with a so great and dreamed Eureka?

$\endgroup$
  • $\begingroup$ There is a polynomial-time algorithm for deciding the primality of every number. See en.wikipedia.org/wiki/AKS_primality_test. $\endgroup$ – lhf May 15 '13 at 13:23
  • 6
    $\begingroup$ I would guess that the time it takes to generate very large prime numbers is more important than the ability to generate them. $\endgroup$ – user714630 May 15 '13 at 13:23
  • 2
    $\begingroup$ We know how to generate the $n$th prime, we just don't know how to do so quickly. :) $\endgroup$ – Thomas Andrews May 15 '13 at 13:24
  • 6
    $\begingroup$ We already have everything you ask for in your first sentence, so the immediate implications would be nil. $\endgroup$ – Gerry Myerson May 15 '13 at 14:00
  • $\begingroup$ @ThomasAndrews: We can do it in time $O(n^{1/2+\varepsilon})$ using bisection of Lagarias-Odlyzko. It would be nice to improve this, I admit! $\endgroup$ – Charles May 15 '13 at 19:28
12
$\begingroup$

There are in fact many 'formula's which always generate prime numbers. Among the simplest ones listed by Wikipedia are:

  • There is some real number $A$ such that $\left\lfloor A^{3^n}\right\rfloor$ is always prime.
  • There is some real number $\alpha$ such that $\left\lfloor 2^{2^{\cdots^{\alpha}}} \right\rfloor$ is always prime.
  • The formula $2 + [2(n!) \bmod (n+1)]$ always gives a prime, where here '$\bmod$' (nonstandardly) denotes the remainder.

The third in particular generates every prime.

These formulas are mathematically valid, fun to prove, and highly interesting. However, they are actually completely useless, and not just because we don't know the values of $A$ and $\alpha$. So (as some have suggested in the comments) a better question is how fast one can generate primes.

The ability (or inability) to generate or check for primes in a certain amount of time is fundamentally important to cryptographic systems such as RSA. However, the "practical" applications of prime numbers (to fields like physics, chemistry, etc.) are, as far as I understand, very few -- cryptography is the major application.

$\endgroup$
  • 3
    $\begingroup$ Of course you couldn't generate the primes up to $n$ in time $O(\log n)$ since you wouldn't have time to write them down. (In decimal, this takes time $\Theta(n)$; writing out just their differences should take $\Theta(n\log\log n/\log n)$ if I'm not mistaken.) Just 'touching' each prime would take time $\Theta(n/\log n)$. $\endgroup$ – Charles May 15 '13 at 14:52
  • 1
    $\begingroup$ @MphLee well, there is a difference in saying that such a bijection exists and being able to compute it. As you have defined it, $p: \mathbb{N} \to \mathbb{P}$ is just a function and not an algorithm. But yes, we do have algorithmic definitions for $p$ - they just take too long, as you say. (Does this make sense?) $\endgroup$ – 6005 May 15 '13 at 15:19
  • 1
    $\begingroup$ @Goos: Right -- you could write it in $\Theta(\log n)$ like "the primes up to 1000000", or in $\Theta(\log\log n)$ like "the primes up to 10^6" (when you're lucky enough to have a number expressible as a power of, say, 10). But this calls into question the meaning of "generate"! $\endgroup$ – Charles May 15 '13 at 19:20
  • 1
    $\begingroup$ How exactly does the ability to generate the $n$th prime in $O(\log n)$ time (assuming it was possible) lead to a break of RSA? $\endgroup$ – Thomas Mar 23 '15 at 9:51
  • 1
    $\begingroup$ @Devdalus That notation looks right--it is $\left(\underbrace{2^{2^{\cdots^2}}}_{n \text{ twos}}\right)^\alpha$. I couldn't find a reference for the formula, though I'm sure I read it on wikipedia or somewhere, a few years back. Anyway, you can prove it with Bertrand's postulate. $\endgroup$ – 6005 Nov 24 '15 at 5:28
7
$\begingroup$

As others have mentioned there are many formulas for primes.

I can't pass up the opportunity to mention my favorite:

$$p_n=1+\sum^{2^n}_{m=1}\left\lfloor \sqrt[n]n \left( \sum^{m}_{x=1}\left\lfloor \cos^2\left( \pi \frac{(x-1)!+1}{x}\right) \right\rfloor \right)^{-1/n} \right\rfloor$$

Maybe it's just my favorite because it's so complicated and unwieldy!

I first found the formula in Hacker's Delight by Warren. The formula is cited as "Willan's Formula". The formula can be derived from the fact that $(x-1)!\equiv -1 (\mod x)$ iff x is 1 or prime. So if $((x-1)!+1)/x$ is an integer, $x$ is prime (or 1), so the cosine of this times $\pi$ will be -1 or 1 iff $x$ is prime or 1. $\cos^2$ gets rid of the negative, floor keeps only the values for which the $\cos^2$ is 1.

This formula appears to be described on the mathworld page for prime formulas.

$\endgroup$
5
$\begingroup$

There are dozens, probably hundreds, of formulas for prime numbers. It's a very well-studied problem. Guy's Unsolved Problems in Number Theory has a section devoted to this, and Ribenboim's books cover this in some depth. Many formulas have been published in mathematical journals, and I've seen at least one survey paper in a journal dedicated to giving an overview of the various types of formulas for primes.

Finding a new formula for the primes might be interesting enough to be published, but not in a first-rate journal unless there's something special about it.

As for security concerns, what would be much more important would be a way to solve integer factorization quickly -- say, in polynomial time. (At the risk of verbosity, this means the time needed to factor $n$ is less than $(\log n)^k$ for some fixed $k$.) Proving that a number is prime can already be done in polynomial time, see the famous AKS algorithm (or the more practical ECPP).

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.