On Single Cycle Functions

Oct 23, 2007 by Ilya Levin

During the last year, I have seen few submitted papers based on my note about single cycle functions published on May 19, 2006.

You can read the note here: "On Single Cycle Functions" (pdf, 95Kb)

I was puzzled by the latest of such papers that I have to review. The authors have reconstructed the missing theory quite well but at some point have surprisingly jumped to a premature and a wrong conclusion.

To make things simpler, I have sketched a small interactive online tool to test any given function for being a single cycle and invertible.

If you as much fascinated by this subject as I am, then go ahead and try the T-functions testbed.

Write a function as a JavaScript subroutine, click on Evaluate button and if all the mapping values set to '1' then the function is a single cycle and invertible. It is this simple.

Since I am already on the subject here, I would like to explain a bit more about the function
x → (a(¬x)) <<< b

Perhaps I was too harsh in dissemblance :)

Multiplication overflow bits do matter. This is easier to see when rotation replaced with
((x << b) | (x >> (2n-b)))

If x = ((a(¬x)) % 2n) then the period is 2n-1 and the function is not invertible indeed. However, it is invertible without the mod.

upd: here are couple more single cycle functions as a bonus :)

Contact Us




Regular Mail

22 Sin Ming Lane #06-76
Midview City
Singapore 573969