Fell deep into the rabbit hole of primality testing today. The best-known algorithm is O(log(n)^6). Desperate quest to understand: why 6?!
Conversation
Replying to
The answer relies on more number theory than I can understand presently, but it’s good to have a project to learn with.
3
8
I miss hanging out with you, Andy
2
It gets worse: the algorithm is secretly O(log(n)^3) if turns out that Agrawal’s conjecture is true:
1
2
Show replies
Replying to
Interested by your tweet, searched, and now… well, en.wikipedia.org/wiki/Elliptic_ noting that worst case behavior is unknown? Even more intriguing.
1
Replying to
This was exactly my reaction to the 'probability of an infinite random walk in N space returning to the origin' thing 😭
4
