9
$\begingroup$

Despite a number of question on AKS algorithm here, there does not seems to anything related to the idea behind it (for those who don't know, AKS primality testing is found in PRIMES is in P).

I read through the paper, check all the step for correctness (and also fix a few small errors). Yet I still can't understand it at all, in the sense that I still can't see the big picture here. From my perspective, it looks like a bunch of unintuitive flashes of insight that just get thrown together until they work.

So can someone explain the big idea behind it please?

I would appreciate if someone can explain it fully, but here are a few specific questions to get you started:

-How does the concept of "introspective" come up?

-Why is it make sense to look at the group $G$ and $\mathcal{G}$?

-How much "wiggle room" is there for the bound $o_{r}(n)>(\log_{2}n)^{2}$ (specifically the RHS)?

-How could one have come up with the proof of an upper bound for $|\mathcal{G}|$?

-How much "wiggle room" is there for $\lfloor\sqrt{\phi(r)}\log_{2}n\rfloor$?

Thank you for your help.

|cite|improve this question
$\endgroup$
  • $\begingroup$ I recommend this: ams.org/journals/bull/2005-42-01/S0273-0979-04-01037-7 by Granville $\endgroup$ – Will Jagy Dec 21 '13 at 2:13
  • $\begingroup$ @WillJagy: thank you for the article, I have read half way through it (in fact, to the proof of the AKS). It give me some insight about it in a wider context. However, my problem remained: it still seems completely unintuitive to me, because stuff such as the 2 groups does not seems to be done by any related work preceding AKS. $\endgroup$ – Gina Dec 21 '13 at 15:54
  • $\begingroup$ Well, the overall comment on AKS is that number theory experts did not look into this type of algorithm because they knew nothing similar would work. So it required someone without such expertise; also, it thereby seemed to come out of the blue. $\endgroup$ – Will Jagy Dec 21 '13 at 18:13
3
$\begingroup$

There is an expository article by Granville titled"It is easy to determine whether a given integer is prime," which answers exactly the question you are asking. The article is worth the read, and it won the 2008 Chauvenet prize for its exposition.

Edit: This article was also referenced by Will Jagy in the comments.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ It's actually the same one linked in the comment above. $\endgroup$ – Gina Dec 23 '13 at 20:20
  • $\begingroup$ It does not seems like any answers to the question are going to come, so I am just going to go ahead and accept this one since it has a good link. $\endgroup$ – Gina Dec 28 '13 at 18:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.