25.3.15

Cyclic Permutations

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 = 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 Zcan 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, a,a3 ,…, aare elements of S where k < n then (a1 aa3 … a) denotes the permutations, for which

a1→a→a3→… → ak-1 →ak→a1

Such a permutation is called cyclic or a cycle


Example 2:  Take the set S and its permutation f from Example 1 above:






The cycles of f are:

1→2→ 4 →8→1
3→6→12→9→3
5→10→5
7→14→13→11→7

Note: 
  1. Up to reordering, these cycles are unique for f
  2. These cycles are all that’s needed to generate the exponentiation table of  Z(there will be more on this in another post)
  3. 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  Zc then:
  1. f can be written as a product of pairwise disjoint cycles that are unique up to reordering.
  2. 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
  3. there will always be at least one cycle that is smaller in length than the rest
  4. 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 
---------------------------------------------------- */   
  1. Make a list L of length n. (n is the input where n must be the product of two distinct primes greater than 2
  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)
  3. Cycle trough the L&M 2D structure starting from index 1 while keeping track of the resulting disjoint cycles 
  4. Return the entry p at the very first index of the first smallest cycle
  5. Divide n by p to get q
This algorithm can have many different implementations, and some of them are more efficient than others.