Linear Equivalence and Involutions



First, a couple of clarifying definitions so we are on the same page:

An involution is a function, f, such that for all x in the domain of
the function, f(f(x))=x.

Two permutations (e.g. s-boxes), A and B, where A, B : F(n)^m -->
F(n)^m, are linearly equivalent if there are bijective linear
mappings, P and Q, and constants, p and q, such that A(x)= Q(B(P(x)+p))
+q.

OK, so I have a couple of questions:

1) If a permutation that is not itself an involution, but that is
linearly equivalent to its own inverse (i.e. S(x)^-1=Q(S(P(x)+p))+q),
then does that mean there is some permutation T that is linearly
equivalent to S but that _is_ an involution (i.e. T(T(x)=x)?

2) If so, is there some way of finding T, or of constructing it from
S, that is better than a brute force search of prospective affine
functions?

I would be grateful for any answers or pointers to papers that might
give an answer.
.



Relevant Pages

  • Re: Inverse of a function is itself
    ... Am 10.07.2007 01:36 schrieb MoeBlee: ... I realized that and scratched the part about permutation in a ... followup. ... So 'involution' seems to be the word, and, if I'm not mistaken, f is ...
    (sci.math)
  • Re: Inverse of a function is itself
    ... 'involution' turns out to be the word. ... But, now, what is the word for a permutation that has no fixed point? ... a shuffle of a deck of card so that no card is the nth ...
    (sci.math)
  • Re: Inverse of a function is itself
    ... I realized that and scratched the part about permutation in a ... followup. ... So 'involution' seems to be the word, and, if I'm not mistaken, f is ... an involution iff f is a symmetric function. ...
    (sci.math)