15.9.15

Finding The Order Of An Element Much Faster

In my previous post I talked about finding the order of an element mod n using what I call skips, the logic for which was first described in the last few paragraphs of Exponentiation Tables in Z sub n. I don't have to stop at 4 skips so long as I account for the overcount and keep the initial element a small and divisible by only itself and 1

The following expression aaa%cur !== 0 replaces the endless logical expressions that are needed to ensure the skipping algorithm stops after encountering the order of a mod n exactly once.

aaa = some_small_power_of_a;
cur = aaa;

do
{
cur = (aaa * cur)%n;
index = length_of_jump + index;

} while ( cur !== 1 && aaa%cur !== 0);

//account for overcounting

In order for this expression to replace the endless logical statements and work correctly, a must be a small prime, and the last power of a before the while loop must be the highest power of a such that it is smaller than n without modulo. Otherwise a different, strict divide operator must be used.

This is easy to see.

Example: let a  = 2 and n = 35
aaaaa = a*a*a*a*a  = 32
the only integers that divide aaaaa with 0 remainder are 2, 4, 8, 16, 32
therefore if the jump lands on one of these integers then the order of 2 has been reached exactly once already

The 18-skip uses this expression and here's how it stacks up to the algorithm presented earlier here and the algorithm from my previous post:

Example: n = 62303*164999 = 10279932697
The 18-skip algorithm finds the order of 2 mod n in 6 seconds; find_order_even_faster finds the order of 2 mod n in 25 seconds, and find_order_faster in 41 seconds.

18-skip implementation, which works best for large n (n that's at least 9 digits or more) and small a:


The 4-skip implementation of the algorithm described earlier in this post with Javascript:



The 2-skip algorithm described in Finding The Order Of An Element Faster with Javascript:



The various ways of finding the order of 2 mod n described here so far from slowest to fastest where the last 3 ways can be used for finding the order of any element mod n:
  1.  Using a cyclic permutation
  2.  Using an algebraic expression
  3.  Using simple addition
  4.  Using double skips
  5.  Using quadruple skips
  6.  Using 18-tuple skips