- 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] - -----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----- - --- In primenumbers@yahoogroups.com, Décio Luiz Gazzoni Filho

<decio@r...> wrote:> -----BEGIN PGP SIGNED MESSAGE-----

algorithm in

> 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

> > polynomial time?

the

>

> Yes, the algorithm known as AKS. It's described in the paper where

> discovery was announced (simply titled ``PRIMES is in P'').

be more

>

> > If so, how does it affect to the searches of big primes? Would it

> > efficient than Lucas-Lehmer in GIMPS, for example?

very efficient

>

> Not much. The Lucas-Lehmer test is polynomial time already, and

> as a matter of fact. For a Mersenne M_p = 2^p - 1, it involves O(p)

squaring modulo

> iterations of the Lucas sequence v_{k+1} = {v_k}^2 - 2 -- a

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

of course.

>

> But the Lucas-Lehmer test doesn't apply for primes of general form,

> 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

being used

> deterministic polynomial-time primality test.

>

> Unfortunately, it's not as efficient as the tests already known and

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

And if a certain conjecture 4 (I can't access a certain site to

>

> Décio

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