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 :)
- x → ax + (¬x), where a is a term of {a0 = 2, ai = ai-1 + 4}
- x → (¬x) + ax + bx, where |a - b| ≡ 4t, t = 0, 1, 2, 3…