f: S → S
Example 1: Let S = Z15 = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
A permutation f of the set above is:
because each element of S can be mapped to an element in [0, 2, 4, 6, 8, 10, 12, 14, 1, 3, 5, 7, 9, 11, 13] and vice versa.
Note: [0, 2, 4, 6, 8, 10, 12, 14, 1, 3, 5, 7, 9, 11, 13] is in fact row 2 of the multiplication table for Z15
In Faster Multiplication Tables I showed how the entire multiplication table of Zn can be generated by shifting the row that lists all elements from 0 to n-1, or row 1, which is why row 2 of the multiplication table always lists the even integers up to n-1 followed by the odd integers up to n-1. I also showed how after generating a number of permutations one can effectively factor n by hitting the first zero divisors, i.e. integers a ≠ 0 and b ≠ 0 yet a * b = 0 mod n. But that was way too much shifting.
There is a faster way of factoring n when n is the product of two distinct odd primes. It involves a single permutation and its cycles.
Definition: If S = [0, 1, 2,…,n-1] and a1, a2 ,a3 ,…, ak are elements of S where k < n then (a1 a2 a3 … ak ) denotes the permutations, for which
a1→a2 →a3→… → ak-1 →ak→a1
Such a permutation is called cyclic or a cycle
The cycles of f are:
1→2→ 4 →8→1
- Up to reordering, these cycles are unique for f
- These cycles are all that’s needed to generate the exponentiation table of Zn (there will be more on this in another post)
- The smallest of these cycles contains p, one of the primes, of which n is the product
Claim: If S = [0, 1, 2,3, …, n-1] is a set of length n, and n is the product of two distinct odd primes p and q, and f is a permutation such that it lists first the odd followed by the even integers up to n-1 (in other words f contains the second row of the multiplication table of Zn c then:
- f can be written as a product of pairwise disjoint cycles that are unique up to reordering.
- at the initial and final index of the smallest cycle of f is one of the primes that n is composed of, namely p or q
- there will always be at least one cycle that is smaller in length than the rest
- if there is more than 1 smaller cycle, then the first one encountered contains either p or q at its initial index.
1. The backbone of the claim, namely part 1, is already a theorem of its own studied in Set Theory.
2. Part 2 is easy to see especially for when (p-1) and (q-1) are composed of large primes since by construction of f in this case, each cycle represents the multiples of a prime mod n.
An interesting algorithm arises and here is a very high level pseudo code:
/* ------------------------------------------------- This content is released under the GNU License http://www.gnu.org/copyleft/gpl.html Author: Marina Ibrishimova Purpose: Factor n using cyclic permutations ---------------------------------------------------- */
- Make a list L of length n. (n is the input where n must be the product of two distinct primes greater than 2
- Shift L to make M where M lists out all even integers from L followed by all odd integers from L (M is also of length n and it is essentially row 2 of the multiplication table of Zn )
- Cycle trough the L&M 2D structure starting from index 1 while keeping track of the resulting disjoint cycles
- Return the entry p at the very first index of the first smallest cycle
- Divide n by p to get q
This algorithm can have many different implementations, and some of them are more efficient than others.