**Definition:**Let S be a finite set of length n, say S = [0, 1, 2,…,n-1]. A permutation of a set S is a bijective mapping:

f: S → S

**Example 1:**Let S = Z

_{15}= [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 Z

_{15}

In Faster Multiplication Tables I showed how the entire multiplication table of Z

_{n }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 a

_{1}, a

_{2 },a

_{3},…, a

_{k }are elements of S where k < n then (a

_{1}a

_{2 }a

_{3}… a

_{k }) denotes the permutations, for which

a

_{1}→a_{2 }→a_{3}→… → a_{k-1 }→a_{k}→a_{1}
Such a permutation is called cyclic or a

__cycle__
The cycles of f are:

1→2→ 4 →8→1

3→6→12→9→3

5→10→5

7→14→13→11→7

**Note:**

- Up to reordering, these cycles are unique for f
- These cycles are all that’s needed to generate the exponentiation table of Z
_{n }(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 Z

_{n }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.

Proof:

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 Z
_{n })- 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.