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.