Re: Prime Number Question

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.

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.

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.

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.)

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.

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: 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: 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: 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: 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: 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)