Skip to main content
added clarification, and some other edits
Source Link
user9072
user9072

I am a bit hesitant to write this, as I am not really familiar with parts of what I discuss, but if I did not get something wrong I believe one can say something more or less precise, on why, as said by Henry Cohn, AKS should not be relvant for factoring.

The AKS-primality test/prove falls into the paradigm of "derandomization," more specifically derandomization of polynomial identity testing, see for example "On Derandomizing Tests for Certain Polynomial Identities" by Agrawal, where the AKS-test is mentioned right at the start.

To put it slightly differently AKS did not use much a new or deep insight on primes or number theory, but an insight on efficient and deterministic testing of identities.

[ADDED clarification: what I want to say by this is that if one now in retrospect reads the (main) proof in 'Primes is in P' then one needs neither explicitly nor implictly, in the sense of fully understanding results that are invoked, any speciliazed number theoretic knowledge to follow it in all details; e.g., no number fields, no exponential sums, no elliptic curves, no analytic number theory. So it is in a technical sense somehow an elementary argument. However, it is my understanding that (yet this is the part were, as said, I do not really know what I am talking about) it was only findable by following and carrying out the above mentioned derandomization paradigm, coming from Theoretical Computer Science. Opposed to an imaginary situation where a proof would combine in a new way all kinds of and/or improve number theoretic results used before in this context to obtain the conclusion.]

Or even more bluntly, the progress is more on the computer-science-side than on the number-theory-side.

While forto optimize the actual exponent in the algorithm various deep number-theoretic results and conjectures are relevant (as discussed in the original AKS paper, and there are also subsequent developments on this), just to get some polynomial time algorithm does essentially need no (advanced) number theory at all. [To avoid any misunderstanding, thisbut the progress is meant as a compliment not a criticismachieved by taking an approach quite distinct from earlier ones.]

ThisTo me this makes the result of AKS all the more remarkable.

Now, this derandomization technique also has other applications, but factoring does not seem to be one (see e.g. the above mentioned paper).

Finally, there are no 'fast' (for the right notion of fast) probabilistic factoring algorithms either.

I am a bit hesitant to write this, as I am not really familiar with parts of what I discuss, but if I did not get something wrong I believe one can say something more or less precise, on why, as said by Henry Cohn, AKS should not be relvant for factoring.

The AKS-primality test/prove falls into the paradigm of "derandomization," more specifically derandomization of polynomial identity testing, see for example "On Derandomizing Tests for Certain Polynomial Identities" by Agrawal, where the AKS-test is mentioned right at the start.

To put it slightly differently AKS did not use much a new or deep insight on primes or number theory, but an insight on efficient and deterministic testing of identities.

Or even more bluntly, the progress is more on the computer-science-side than on the number-theory-side.

While for the actual exponent in the algorithm number-theoretic results are relevant, just to get some polynomial time algorithm does essentially need no (advanced) number theory at all. [To avoid any misunderstanding, this is meant as a compliment not a criticism.]

This technique also has other applications, but factoring does not seem to be one (see e.g. the above mentioned paper).

Finally, there are no 'fast' (for the right notion of fast) probabilistic factoring algorithms either.

I am a bit hesitant to write this, as I am not really familiar with parts of what I discuss, but if I did not get something wrong I believe one can say something more or less precise, on why, as said by Henry Cohn, AKS should not be relvant for factoring.

The AKS-primality test/prove falls into the paradigm of "derandomization," more specifically derandomization of polynomial identity testing, see for example "On Derandomizing Tests for Certain Polynomial Identities" by Agrawal, where the AKS-test is mentioned right at the start.

To put it slightly differently AKS did not use much a new or deep insight on primes or number theory, but an insight on efficient and deterministic testing of identities.

[ADDED clarification: what I want to say by this is that if one now in retrospect reads the (main) proof in 'Primes is in P' then one needs neither explicitly nor implictly, in the sense of fully understanding results that are invoked, any speciliazed number theoretic knowledge to follow it in all details; e.g., no number fields, no exponential sums, no elliptic curves, no analytic number theory. So it is in a technical sense somehow an elementary argument. However, it is my understanding that (yet this is the part were, as said, I do not really know what I am talking about) it was only findable by following and carrying out the above mentioned derandomization paradigm, coming from Theoretical Computer Science. Opposed to an imaginary situation where a proof would combine in a new way all kinds of and/or improve number theoretic results used before in this context to obtain the conclusion.]

Or even more bluntly, the progress is more on the computer-science-side than on the number-theory-side.

While to optimize the exponent in the algorithm various deep number-theoretic results and conjectures are relevant (as discussed in the original AKS paper, and there are also subsequent developments on this), just to get some polynomial time algorithm does essentially need no (advanced) number theory at all, but the progress is achieved by taking an approach quite distinct from earlier ones.

To me this makes the result of AKS all the more remarkable.

Now, this derandomization technique also has other applications, but factoring does not seem to be one (see e.g. the above mentioned paper).

Finally, there are no 'fast' (for the right notion of fast) probabilistic factoring algorithms either.

Source Link
user9072
user9072

I am a bit hesitant to write this, as I am not really familiar with parts of what I discuss, but if I did not get something wrong I believe one can say something more or less precise, on why, as said by Henry Cohn, AKS should not be relvant for factoring.

The AKS-primality test/prove falls into the paradigm of "derandomization," more specifically derandomization of polynomial identity testing, see for example "On Derandomizing Tests for Certain Polynomial Identities" by Agrawal, where the AKS-test is mentioned right at the start.

To put it slightly differently AKS did not use much a new or deep insight on primes or number theory, but an insight on efficient and deterministic testing of identities.

Or even more bluntly, the progress is more on the computer-science-side than on the number-theory-side.

While for the actual exponent in the algorithm number-theoretic results are relevant, just to get some polynomial time algorithm does essentially need no (advanced) number theory at all. [To avoid any misunderstanding, this is meant as a compliment not a criticism.]

This technique also has other applications, but factoring does not seem to be one (see e.g. the above mentioned paper).

Finally, there are no 'fast' (for the right notion of fast) probabilistic factoring algorithms either.