3 ms·
Miller-Rabin isn't that hard to implement - it just needs some reasonable maths skills related to modular arithmetic, and a copy of Knuth for fast versions of s
by elemeno 15y ago
Miller-Rabin isn't that hard to implement - it just needs some reasonable maths skills related to modular arithmetic, and a copy of Knuth for fast versions of some algorithms helps a lot as well.
I've stuck a very simple version (in C#) here - https://github.com/elemeno/SimpleMillerRabin/blob/master/SimpleMillerRabin/MillerRabin.cs https://github.com/elemeno/SimpleMillerRabin/blob/master/Sim...
- nhaehnle 15y agoI agree. Implementing the Miller-Rabin algorithm is one of the homework assignments in the Computer Algebra course we give here. In fact, once you've got the necessary concepts from group theory and modular arithmetic down, the algorithm itself is actually quite simple (it's the correctness proof that has a subtle and clever idea). When the author was talking about the "Project Triangle" in the context of primality testing, I thought he was going to bring up AKS!