*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: