14.1.16

Finding The Order Of An Element: A Recap

There are many different algorithms for factoring integers and some of them involve finding the order of an element mod n. The order of an element a mod n is the smallest integer k for which ak = 1 mod n holds true.

The most famous factoring algorithm that involves finding the order of elements mod n is known as Shor's Algorithm, which requires a quantum computer to calculate the order of an element and a digital computer to do the rest.

I boldly claim that there is a way to find the order of an element mod n when n is the product of two distinct odd primes in only 3 calculations but so far I failed to deliver on my audacious claim. Or did I?

Meanwhile I wrote a bunch of whimsical algorithms for finding the order of 2 mod n that helped me strengthen my Javascript skills. Somewhat. Here I put them all in one blog post to remind myself of good times.

Below are the various ways of finding the order of 2 mod n (iframed) from fastest to slowest where the first 3 ways can be used for finding the order of any element a mod n:

1. Using 18-skip implementation and the fact that phi(n)/2 is a universal exponent when n is the product of two distinct odd primes; works best for large n (n that's at least 9 digits or more) and small a:


2. Using the 4-skip implementation of the algorithm described earlier with Javascript and the fact that phi(n)/2 is a universal exponent when n is the product of two distinct odd primes:




3.Using the 2-skip algorithm described in Finding The Order Of An Element Faster with Javascript and the fact that phi(n)/2 is a universal exponent when n is the product of two distinct odd primes.:



4. Using an algebraic expression and the fact that phi(n)/2 is a universal exponent when n is the product of two distinct odd primes.



5. Using simple addition and the fact that phi(n)/2 is a universal exponent when n is the product of two distinct odd primes.




6. Using the length of a cycle in a cyclic permutation