Re: Prime Number Question

Joachim Schipper <jdNoOtSPAMschipper@xxxxxxxxxx> wrote:
dave <daf@xxxxxxxxxxxxxxx> wrote:
What would be the security impact to encryption technology if there
were discovered a simply algorithm for generating all prime numbers
directly (no sieve required), in batches, with each batch being used
to generate the next batch?

(A little background: I currently study abstract algebra and number
theory at the universities of Utrecht, and, increasingly, Leiden. I
don't really do crypto, but I do have some idea what I'm talking about.)

Such a method would most likely be rather inefficient; keep in mind that
the current best factoring method, the number field sieve, only becomes
the 'best' (i.e. fastest) at about 10^100 [1]. Anything that works in
batches will need quite a while to get to numbers that big.

See the website http://calculateprimes.com for information about the
new book documenting the algorithm which uses only addition and
subtraction to generate primes directly with essentially no filtering
required. The author, James McCanney, has masters degrees in physics
and math and taught many college levelmath courses at Cornell University.
Ignore McCanney's spelling errors. One of my brothers had a PhD in
algebraic topology and his spelling was atrocious. It didn't affect his
math except when he was writing papers for publication.

Also, almost all theory I am aware of - which is admittedly a tiny
subset of all theory - for efficient factoring exploits some
characteristic of primes (most likely, prime ideals) in some field.
Without going into details, such theory does not lead to algorithms of
the sort you describe.

I wish I could give more details of McCanney's algorithm, but I don't
yet have a copy of the book.

Finally, it's not clear how such a method would be considerably more
efficient than the classical prime sieve (Eratosthenes' sieve), which is
not very efficient at all.

McCanney's algorithm purportedly generates the values of primes directly.
There is no filtering required. The primes are generated in batches. Each
batch of primes is used to generate the next batch.

Given the above, whoever develops the theory necessary for such an
algorithm to work is extremely likely to be awarded the Fields Medal and
his [2] position of choice at his university of choice. (Also see:
Andrew Wiles.)

McCanney has an impressive track record in Astronomy, but his work has
been ignored by the scientific establishment. Ditto for Immanuel Velikovsky,
in whose footsteps McCanney treads.

However, given efficient prime factorisation, yes, quite a few crypto
algorithms would fall flat. We do have alternatives [3], though, so
unless the discovery is very sudden, we'll have time to switch.

The algorithm is here now, as far as I can tell from what McCanney has
said on the radio (Thursday nights 5.070 MHz at 1900 -5 UMT)
McCanney says the algorithm is simple enough for 3rd graders to
calculate.

Dave

Joachim

[1] Number from Wikipedia, and may or may not be accurate. The exponent
is of the right order, though, and I don't feel like cracking open my
books to check.

[2] Let's face it, almost certainly his. Notwithstanding the very
intelligent and pleasant women I study with daily.

[3] Although I wouldn't necessarily recommend those; most of them are
based on newer areas of mathematics, which have received considerably
less attention than prime factorisation.
.

Relevant Pages

  • Re: APL and (very) large arrays
    ... Sort is at best O) depending on the sorting algorithm used, ... As to the OP's question about primes, there are advanced efforts to compute pifor very large values of n, but the only elementary method is to find all primes <= n and count them. ... By representing only the odd values the sieve would require 62.5MB. ...
    (comp.lang.apl)
  • Re: Prime Number Question
    ... were discovered a simply algorithm for generating all prime numbers ... directly, in batches, with each batch being used ... the current best factoring method, the number field sieve, only becomes ... characteristic of primes ...
    (comp.unix.bsd.openbsd.misc)
  • Re: simple algorithm for finding primes
    ... Well it includes the Sieve of Eratosthenes within the source. ... Your algorithm is a fine, simplistic algorithm, however it really only works ... because you determine the entire sequence of primes one after another. ... for longer and longer sequence of primes it will get slower and slower and ...
    (comp.lang.c)
  • Re: Prime Number Question
    ... were discovered a simply algorithm for generating all prime numbers ... directly, in batches, with each batch being used ... the current best factoring method, the number field sieve, only becomes ... characteristic of primes ...
    (comp.unix.bsd.openbsd.misc)
  • Re: Math errors in book Secret Life of Numbers
    ... his students have proven that primes can be found in polynomial time. ... For practical purposes the algorithm is, admittedly, still too ... that in practice, it always was solved in polynomial time using the ... the simplex method is not a polynomial-time algorithm. ...
    (sci.math.research)