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