0
$\begingroup$

Agrawal-Kayal-Saxena use the identity $$(X+a)^n=X^n+a \pmod{n, X^r-1}$$ for some small $a$'s to determine primes. Is it possible to improve this method and use it for integer factorization? Are there any research in this way? Thanks.

[Edit] More specifically, Is it possible to find a constructive proof (rather than the original existence proof) of AKS theorem, which will reveal some information for composite numbers.

Improve this question
$\endgroup$
4
  • 9
    $\begingroup$ Probably it's not possible to turn it into an efficient factoring method. Primality testing is much easier than factoring: primes have many special properties, and if you fail to detect these properties you know you are dealing with a composite number, but this generally does not produce actual factors. I don't see anything about the AKS test that seems likely to lead to progress on factoring, and although I guess it's hard to rule it out in principle, it doesn't sound like a fruitful research direction to me. $\endgroup$
    – Henry Cohn
    Commented Apr 21, 2011 at 12:17
  • 4
    $\begingroup$ I am voting to close. My apologies, but questions of the form "can (something) be used to approach (really hard problem)?" are a little too open-ended for my taste. $\endgroup$
    – David Hansen
    Commented Apr 21, 2011 at 12:32
  • 1
    $\begingroup$ @David Hansen, if one takes the question very litterally then yes (because to say with certainty something is impossible is mostly impossible). But, I believe one can say something meaningful why this is unlikely (my first attempt is below, but I know there are various people on the site that could say something better/more definite on this). $\endgroup$
    – user9072
    Commented Apr 21, 2011 at 13:36
  • $\begingroup$ What precisely do you mean by 'AKS theorem'? $\endgroup$
    – user9072
    Commented Apr 23, 2011 at 3:22

2 Answers 2

Reset to default
3
$\begingroup$

AKS did use new and deep insights from number theory. They first created a new randomized algorithm for primality and then they were able to derandomize it. A polynomial algorithm for primality was known by Miller under GRH and AKS used a certain averaged deep result by Bombieri instead. They also used deep general techniques of derandomization.

Any such new great result may give hope for even greater new results in the same general area. But as Henry explained factoring is considerably harder than primality and there is no specific reason to believe that the AKS algorithm will be relevant for factoring.

There are some complexity-theoretic indications that derandomization is possible. Practically, randomized algorithm can be carried out rather safely by using computers methods for generating random bits. (Probably the easyness of practical derandomization and computational-theoretic indications that derandomization is possible are related. But this is an interesting question on its own.) Nevertheless there are notorious problems that derandomization is not known (like testing polynomial identities). So while AKS theorem goes in the expected direction of CC it was still a big surprise.

There are some complexity theoretic indications that factoring is hard. (Among them the fact that factoring is hard in practice.)

Anyway, the fact that primality is easy is sort of a miracle for which I dont have a good understanding.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I am the unknown giving the other answer. Not sure if I was misunderstood, but it was in no way my intention to somehow belittle the progress that AKS was (as I hoped to convey with a later sentence to that extent). On rereading the phrasing 'AKS did not use...number theory' in my asnwer I see that it is misleading and I will change this. But, what I beieve to be true and wanted to say is that the main proof in 'Primes is in P' does not use these number theoretic res. and succeeds in showing that Primes is in P essentially from 'nothing' (which to me makes the result even better); (cont.) $\endgroup$
    – user9072
    Commented Apr 22, 2011 at 0:06
  • $\begingroup$ (cont.) the paper also contains a discussion of improvements of the bounds for the exponent (which I mentioned but of which I unfortunately failed to mention that some of them were already in the AKS-paper) that do involve these results. But they are not necessary for what is I believe the main point of the paper, namely that Primes is in P. $\endgroup$
    – user9072
    Commented Apr 22, 2011 at 0:15
  • $\begingroup$ Sorry, to write a third comment. I now edited my answer to (I hope) express more clearly what I wanted to say. Finally, I would like to appologize if my original crude formulation should have been disrespectful towards AKS. This was certainly not my intention. $\endgroup$
    – user9072
    Commented Apr 22, 2011 at 2:03
3
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .