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

Re: [PrimeNumbers] Primes is in P and titanic prime searches

Expand Messages
  • 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 1 of 3 , Apr 6, 2003
      -----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 2 of 3 , Apr 6, 2003
        --- 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.