Re: Prime Number Question

dave <daf@xxxxxxxxxxxxxxx> wrote:
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?

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.

The first paragraph gives a strong idea that this person is an
sensationalist and idiot, and further reading and Wikipedia confirm
that.

Nevermind the fact that someone with a MSc in Physics (he does not even
claim a title in Mathematics, though he has taught introductionary
Mathematics for a while - but that's analysis, not algebra) is not
qualified to comment on advanced number theory, any more than I would be
qualified to comment on string theory (which is mostly analysis, not
algebra). The simple fact is that anything that can be presented to the
general public in three hours can usually be found by any somewhat
competent mathematication in, at most, three days. This is a problem
that thousands of very smart, very talented people have spend lifetimes
researching.

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.

I wouldn't plan on getting one. There are plenty of good books that will
be of more value to you, and I'd be happy to recommend some
(alternately, consult some local university). Also, Wikipedia has a
section on prime tests and factorisation methods.

For a mathematical book of a more formal-logic bent, I can highly
recommend 'Godel, Escher, Bach - an eternal golden braid', a classic
available at most quality book stores. You get a basic course in AI and
music theory for free, and it manages to present ideas well without
having to introduce lots of 'scaffolding'.

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.

Whatever he says...

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.

Wikipedia suggests that he is a well-known idiot, yes.

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.

As is the Eratosthenes sieve. Don't get me wrong: it's quite possible to
invent an algorithm that will generate all primes (Eratosthenes' sieve
can be discovered by a smart, mathematically-inclined high school kid).
Giving all primes is a problem that has been essentially forever. The
trick is in being both quick and accurate (current prime tests tend to
be at most one of those).

Joachim
.

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)