Loading ...
Sorry, an error occurred while loading the content.

Primes is in P and titanic prime searches

Expand Messages
  • Jose Ramón Brox
    Does the discovery of primes being in P bring an specific algorithm in polynomial time? If so, how does it affect to the searches of big primes? Would it be
    Message 1 of 3 , Apr 6, 2003
    • 0 Attachment
      Does the discovery of primes being in P bring an specific algorithm in polynomial time?

      If so, how does it affect to the searches of big primes? Would it be more efficient than Lucas-Lehmer in GIMPS, for example?


      [Non-text portions of this message have been removed]
    • Décio Luiz Gazzoni Filho
      ... Hash: SHA1 ... Yes, the algorithm known as AKS. It s described in the paper where the discovery was announced (simply titled ``PRIMES is in P ). ... Not
      Message 2 of 3 , Apr 6, 2003
      • 0 Attachment
        -----BEGIN PGP SIGNED MESSAGE-----
        Hash: SHA1

        On Sunday 06 April 2003 16:42, Jose Ramón Brox wrote:
        > Does the discovery of primes being in P bring an specific algorithm in
        > polynomial time?

        Yes, the algorithm known as AKS. It's described in the paper where the
        discovery was announced (simply titled ``PRIMES is in P'').

        > If so, how does it affect to the searches of big primes? Would it be more
        > efficient than Lucas-Lehmer in GIMPS, for example?

        Not much. The Lucas-Lehmer test is polynomial time already, and very efficient
        as a matter of fact. For a Mersenne M_p = 2^p - 1, it involves O(p)
        iterations of the Lucas sequence v_{k+1} = {v_k}^2 - 2 -- a squaring modulo
        M_p and a subtraction (not single-precision but as fast as one in practice).
        This is as cheap as a Fermat pseudoprimality test, one of the cheapest tests
        known, and yet it proves the primality of the number.

        But the Lucas-Lehmer test doesn't apply for primes of general form, of course.
        However, there are many probabilistic primality tests with polynomial
        expected running time, and deterministic polynomial-time primality tests
        conditional on the Riemann Hypothesis. The theoretical breakthrough of the
        AKS algorithm was showing the existence of an unconditionally valid
        deterministic polynomial-time primality test.

        Unfortunately, it's not as efficient as the tests already known and being used
        in practice, so AKS is mostly of theoretical interest. However, many great
        minds have worked on improving this algorithm and it's in a much better state
        now than when it was first released.

        Décio
        -----BEGIN PGP SIGNATURE-----
        Version: GnuPG v1.2.1 (GNU/Linux)

        iD8DBQE+kJkGce3VljctsGsRAvo4AJ93gAEH/bw5j+oSXJEdO7QrjFr6lwCZAeJi
        L5lIYgItK3Ff1kGqJU2TJeA=
        =k4uH
        -----END PGP SIGNATURE-----
      • andrew_j_walker
        ... algorithm in ... the ... be more ... very efficient ... squaring modulo ... practice). ... cheapest tests ... of course. ... polynomial ... tests ... of
        Message 3 of 3 , Apr 6, 2003
        • 0 Attachment
          --- In primenumbers@yahoogroups.com, Décio Luiz Gazzoni Filho
          <decio@r...> wrote:
          > -----BEGIN PGP SIGNED MESSAGE-----
          > Hash: SHA1
          >
          > On Sunday 06 April 2003 16:42, Jose Ramón Brox wrote:
          > > Does the discovery of primes being in P bring an specific
          algorithm in
          > > polynomial time?
          >
          > Yes, the algorithm known as AKS. It's described in the paper where
          the
          > discovery was announced (simply titled ``PRIMES is in P'').
          >
          > > If so, how does it affect to the searches of big primes? Would it
          be more
          > > efficient than Lucas-Lehmer in GIMPS, for example?
          >
          > Not much. The Lucas-Lehmer test is polynomial time already, and
          very efficient
          > as a matter of fact. For a Mersenne M_p = 2^p - 1, it involves O(p)
          > iterations of the Lucas sequence v_{k+1} = {v_k}^2 - 2 -- a
          squaring modulo
          > M_p and a subtraction (not single-precision but as fast as one in
          practice).
          > This is as cheap as a Fermat pseudoprimality test, one of the
          cheapest tests
          > known, and yet it proves the primality of the number.
          >
          > But the Lucas-Lehmer test doesn't apply for primes of general form,
          of course.
          > However, there are many probabilistic primality tests with
          polynomial
          > expected running time, and deterministic polynomial-time primality
          tests
          > conditional on the Riemann Hypothesis. The theoretical breakthrough
          of the
          > AKS algorithm was showing the existence of an unconditionally valid
          > deterministic polynomial-time primality test.
          >
          > Unfortunately, it's not as efficient as the tests already known and
          being used
          > in practice, so AKS is mostly of theoretical interest. However,
          many great
          > minds have worked on improving this algorithm and it's in a much
          better state
          > now than when it was first released.
          >
          > Décio

          And if a certain conjecture 4 (I can't access a certain site to
          check this) is proved, it will be quite fast!

          Andrew

          (PS Please, everyone, lets keep this group focused on prime issues
          rather than war discussions. And if you do decide to discuss the
          war, try and keep things balanced by stating how many Iraqis have
          been murdured by their own leaders).
        Your message has been successfully submitted and would be delivered to recipients shortly.