During the following week I plan to publish some interesting posts about my AKS algorithm implementation in python.
This algorithm was a really good challenge, for different reasons:
- If you want to understand how it works you have to study some algebra(actually not a lot of algebra, since it uses only basic algebra facts). I hadn't ever studied algebra at school, so this was a nice discovery
- The algorithm is of great theoretical importance(being the only polynomial-time primality-testing algorithm for general numbers), but it's actually really slow, and it's quite hard to get a decent implementation.
- Trying to optimize this algorithm I came across some really nice techniques, such as window multiplication for polynomials