Theoretical Model
 

[FONT=Calibri][SIZE=3]It seems the problem of finding larger and larger primes is that computer power is the limiting factor. Is it not possible to develop a theoretical model to find and verify larger and larger primes without extensive computation?[/SIZE][/FONT]

For any theoretical model you care to create (and we'd love to have new ones), the problem is that the amount of computation involved is going to be enormous, because the numbers themselves are enormous. And, even if you did find a model that caused the work to get 10 or 100 times as small, we computational number theorists would simply go out and find larger numbers to work on....

Now, if you want to talk about what that theory might be, I'd point out that the LL test is pretty straightforward. MPQS isn't too bad, but there's only a few here that understand SNFS or GNFS. But I will warn you that you need to do some serious studying, and be smart, even to understand the existing tools. I think some may be game, but I found helping the programming effort to be a lot easier, and even that is slow work for me.

Another problem for anyone trying to improve the theory is that they decide to present their theory on Mersenne Forum first, which is likely to illicit flames from some of the better educated/unrefined users. I happen to keep in touch with someone who's actively trying to improve the art of number theory in general, and while he might search the forum for help in various things he's working on, he hasn't actually signed in in a very long time.

As it's been said before, while a lesser man may make a lot of mistakes, a greater man will make even more mistakes simply because he continues to try.

[QUOTE=aymanmikhail;269630]It seems the problem of finding larger and larger primes is that computer power is the limiting factor.[/QUOTE]Do you have a true understanding of the size of the numbers we are talking about? They have no real connection to the numbers found in the physical universe. 13,000,000 digits long. The physical universe typically needs less than 100 digits to describe it.

[QUOTE=jasong;269666]Another problem for anyone trying to improve the theory is that they decide to present their theory on Mersenne Forum first, which is likely to illicit flames from some of the better educated/unrefined users. I happen to keep in touch with someone who's actively trying to improve the art of number theory in general, and while he might search the forum for help in various things he's working on, he hasn't actually signed in in a very long time.

As it's been said before, while a lesser man may make a lot of mistakes, a greater man will make even more mistakes simply because he continues to try.[/QUOTE]

Indeed, it's time to remind that certain flamer to tell us why he said a certain paper, after corrections, was still unpublishable....remind me to get in touch when I start studying number theory again.

[url]http://mersenneforum.org/showthread.php?t=13600[/url]

Don't let him get to you.

[QUOTE=aymanmikhail;269630][FONT=Calibri][SIZE=3]Is it not possible to develop a theoretical model to find and verify larger and larger primes without extensive computation?[/SIZE][/FONT][/QUOTE]We'd welcome such a model!!

No one has yet come up with one that's more streamlined (asymptotically faster) than Lucas-Lehmer, but there's no proof that a better digital algorithm is impossible. (There is wide skepticism that one is possible, yes, but not proof of impossibility.)

Of course, many think that quantum computing should eventually be able to find and verify large primes faster than digital computing can.

[QUOTE=cheesehead;269700]
Of course, many think that quantum computing should eventually be able to find and verify large primes faster than digital computing can.[/QUOTE]

If by "many" you mean UncWilly and Chalsall, I will endorse that

But then again, as Feynman, Bohr, Einstein, Born, Borg...
have said before:
If you think you understand QM, you don't.

Or was that the 60s?
I've forgotten.

David

No; I do not have such a model. I apologize for the implication by stating the obvious.


Yes; we are dealing with infinity. I would argue that these numbers do exist in the physical universe just as gravitational singularity at the center of a black hole exists.


Within the current state of human knowledge/technology, the persons with the most computing power will find the next largest prime. The human mind is slow but it possesses imagination/creativity and the ability to think about the infinite.

[QUOTE=davieddy;269710]If by "many" you mean UncWilly and Chalsall, I will endorse that:smile:[/QUOTE]
The fun thing about quantum computing is that they're managing to add a qubit to what's already working about once every year or 2. So, basically, qubits are advancing at about the rate of Moore's Law, which means they'll be pretty much useless for another 30 years or so. Of course, things might begin to speed up. But, for the moment they're like the science of fusion, it's a future technology, and will be a future technology for a long time.

[QUOTE=aymanmikhail;269712]Yes; we are dealing with infinity. I would argue that these numbers do exist in the physical universe just as gravitational singularity at the center of a black hole exists.[/QUOTE]Now that is an interesting statement.

Could you give us some pointers to any literature which contains any experimental or observational evidence to support your claim about the existence of singularities please?


Paul

[QUOTE=xilman;269783]Now that is an interesting statement.

Could you give us some pointers to any literature which contains any experimental or observational evidence to support your claim about the existence of singularities please?

Paul[/QUOTE]

[COLOR=black][FONT=Verdana]Mathematics is a natural science of which infinity is not a part of?[/FONT][/COLOR]
[COLOR=black][FONT=Verdana][/FONT][/COLOR]
[COLOR=black][FONT=Verdana]The [B]Penrose–Hawking singularity theorems[/B] are a set of results in [URL="http://en.wikipedia.org/wiki/General_relativity"][COLOR=windowtext]general relativity[/COLOR][/URL] which attempt to answer the question of when gravitation produces [URL="http://en.wikipedia.org/wiki/Gravitational_singularity"][COLOR=windowtext]singularities[/COLOR][/URL].[/FONT][/COLOR][COLOR=black][FONT=Times New Roman][/FONT][/COLOR]
[URL]http://www.ias.ac.in/jarch/jaa/17/213-231.pdf[/URL]

[QUOTE=aymanmikhail;269801][COLOR=black][FONT=Verdana]Mathematics is a natural science of which infinity is not a part of?[/FONT][/COLOR]
[COLOR=black][FONT=Verdana][/FONT][/COLOR]
[COLOR=black][FONT=Verdana]The [B]Penrose–Hawking singularity theorems[/B] are a set of results in [URL="http://en.wikipedia.org/wiki/General_relativity"][COLOR=windowtext]general relativity[/COLOR][/URL] which attempt to answer the question of when gravitation produces [URL="http://en.wikipedia.org/wiki/Gravitational_singularity"][COLOR=windowtext]singularities[/COLOR][/URL].[/FONT][/COLOR][COLOR=black][FONT=Times New Roman][/FONT][/COLOR]
[URL]http://www.ias.ac.in/jarch/jaa/17/213-231.pdf[/URL][/QUOTE]I asked for experimental or observational evidence, not theoretical predictions.

Paul

[QUOTE=xilman;269808]I asked for experimental or observational evidence, not theoretical predictions.
Paul[/QUOTE]

I was wrong and you are correct. :smile:

Does evidence for the Big Bang count?

[QUOTE=Flatlander;269825]Does evidence for the Big Bang count?[/QUOTE]Not obviously so. There are Big Bang models in which the the bang is the second half of a bounce and where the size of the bouncing object is of the order of the Planck length. In these models gravity becomes repulsive at a short enough distances.

Another model, Penrose's CCC, identifies the singularity with the infinitely dilute preceding cosmos via conformal mapping. Admittedly the simple view is that a singularity exists from our view of the cosmos but the "end" of the preceding cosmos is infinitely large, as will be the end of ours, yet the two are identically the same --- infinite in space and time, and of zero extent together.


Paul

[QUOTE=xilman;269832]Another model, Penrose's CCC, identifies the singularity with the infinitely dilute preceding cosmos via conformal mapping. Admittedly the simple view is that a singularity exists from our view of the cosmos but the "end" of the preceding cosmos is infinitely large, as will be the end of ours, yet the two are identically the same --- infinite in space and time, and of zero extent together.Paul[/QUOTE]

Wonderful. Now that we can get past my poor analogy .. back to my original point. The competition to find the next largest prime runs parallel to the quest to build the most powerful supercomputer or network of computers. The next great advance in number theory will require creative thinking.

Case in point: A quote (and link) about the AKS algorithm.

[URL]http://www.hindu.com/fline/fl1917/19171290.htm[/URL]
"Given the trend in the field during the 1980s, the general belief in the community was there should exist a polynomial time algorithm for proving primality, but finding it was going to be involved and difficult. The greatness of the Agrawal-Kayal-Saxena (AKS) algorithm is that it is relatively simple, not requiring fancy mathematics of elliptic curves and the like. It is deterministic and relies on no unproven assumptions. The reason for the AKS algorithm's success is simple. Unlike others who believed that the elliptic curve method was the only viable approach to the problem and, as in any other field, the newer algorithms were basically incremental advances over the Goldwasser and Kilian approach, AKS chose to abandon the well-treaded approach altogether and explored new lines of attack on the problem using simple concepts of algebra."

More about AKS...
[URL]http://primes.utm.edu/prove/prove4_3.html[/URL]

[FONT=Calibri][QUOTE]
The key to AKS' result is another simple version of [URL="http://primes.utm.edu/prove/prove2_2.html#FLittleT"][COLOR=#0066cc]Fermat's Little Theorem[/COLOR][/URL]:[INDENT][B]Theorem:[/B] Suppose that [I]a[/I] and [I]p[/I] are relatively prime integers with [I]p[/I] > 1. [I]p[/I] is prime if and only if
([I]x[/I]-[I]a[/I])[I][SIZE=2]^p[/SIZE][/I] = ([I]x[SIZE=2]^p[/SIZE][/I]-[I]a[/I]) (mod [I]p[/I]) [/INDENT][INDENT][B]Proof.[/B] If [I]p[/I] is prime, then [I]p[/I] divides the binomial coefficients [I][SIZE=2]p[/SIZE][/I]C[I][SIZE=2]r[/SIZE][/I] for [I]r[/I] = 1, 2, ... [I]p[/I]-1. This shows that ([I]x[/I]-[I]a[/I])[I][SIZE=2]^p[/SIZE][/I] = ([I]x[SIZE=2]^p[/SIZE][/I]-[I]a[SIZE=2]^p[/SIZE][/I]) (mod [I]p[/I]), and the equation above follows via Fermat's Little Theorem. On the other hand, if [I]p[/I] > 1 is composite, then it has a prime divisor [I]q[/I]. Let [I]q[SIZE=2]^k[/SIZE][/I] be the greatest power of [I]q[/I] that divides [I]p[/I]. Then [I]q[SIZE=2]^k[/SIZE][/I] does not divide [I][SIZE=2]p[/SIZE][/I]C[I][SIZE=2]q[/SIZE][/I] and is relatively prime to [I]a[SIZE=2]p-q[/SIZE][/I], so the coefficient of the term [I]x[SIZE=2]^q[/SIZE][/I] on the left of the equation in the theorem is not zero, but it is on the right.[/QUOTE]

Agrawal, Kayal and Saxena managed to reformulate this into the following algorithm which they proved would run in at most O((log [I]n[/I])[SIZE=2]^12[/SIZE][I]f[/I](log log [I]n[/I])) time where [I]f[/I] is a polynomial. (This means the time it takes to run the algorithm is at most a constant times the number of digits to the twelfth power times a polynomial evaluated at the log of the number of digits.)

[CODE]Input: Integer [I]n[/I] > 1

if ([I]n[/I] is has the form [I]a[SIZE=2]b[/SIZE][/I] with [I]b[/I] > 1) then output COMPOSITE

[I]r[/I] := 2
while ([I]r[/I] < [I]n[/I]) {
if (gcd([I]n[/I],[I]r[/I]) is not 1) then output COMPOSITE
if ([I]r[/I] is prime greater than 2) then {
let [I]q[/I] be the largest factor of [I]r[/I]-1
if ([I]q[/I] > 4sqrt([I]r[/I])log [I]n[/I]) and ([I]n[/I][SIZE=2]([I]r[/I]-1)/[I]q[/I][/SIZE] is not 1 (mod [I]r[/I])) then break
}[I]
r[/I] := [I]r[/I]+1
}

for [I]a[/I] = 1 to 2sqrt([I]r[/I])log [I]n[/I] {
if ( ([I]x[/I]-[I]a[/I])[I][SIZE=2]n[/SIZE][/I] is not ([I]x[/I][I][SIZE=2]n[/SIZE][/I]-[I]a[/I]) (mod [I]x[/I][I][SIZE=2]r[/SIZE][/I]-1,[I]n[/I]) ) then output COMPOSITE
}

output PRIME; [/CODE][/FONT]
[/INDENT]