[math-fun] Perm polys & factorial bases
I'm still wondering if there are simple correspondences between factorial representations and permutation polynomials. For simplicity, let's focus only on a prime # of elements. For example, over GF(p) there are p! permutations. Is there a polynomial form in which we have exactly p choices for one of the coefficients, exactly p-1 choices for the next coefficient, exactly p-2 choices for the next coefficient, and so on? What if the p basis functions are things other than monomials x, x^2, x^3, etc. ? With function composition, we can do the following: f(g(h(...(q(x))...))) can be a representation of one of these p! permutations if f(x) chooses one of p elements; g(x) chooses one of p-1 elements; h(x) chooses one of p-2 elements, and so forth. A form such as this should be relatively easy to manufacture. So it should be possible to represent any permutation in this fully-nested "standard" form. Are there forms involving multiplication instead of composition? Are there forms involving addition instead of composition?
I'd expect that if there is such a representation, the innermost function would be the one choosing one of p elements, the next one would know from f(x) which element *not* to choose, and would pick one of the p-1 remaining elements, etc. —Dan
On Mar 25, 2016, at 9:10 AM, Henry Baker <hbaker1@pipeline.com> wrote:
With function composition, we can do the following:
f(g(h(...(q(x))...))) can be a representation of one of these p! permutations if
f(x) chooses one of p elements; g(x) chooses one of p-1 elements; h(x) chooses one of p-2 elements, and so forth.
Being permutations, this representation should be closed under functional inversion, so ideally, both the "forward" and "inverse" representations should be possible. Note: if it is easy/trivial to invert such a permutation function, such a result might call into question the use of functions of this type in crypto applications. At 09:16 AM 3/25/2016, Dan Asimov wrote:
I'd expect that if there is such a representation, the innermost function would be the one choosing one of p elements, the next one would know from f(x) which element *not* to choose, and would pick one of the p-1 remaining elements, etc.
ÂDan
On Mar 25, 2016, at 9:10 AM, Henryy Baker <hbaker1@pipeline.com> wrote:
With function composition, we can do the following:
f(g(h(...(q(x))...))) can be a representation of one of these p! permutations if
f(x) chooses one of p elements; g(x) chooses one of p-1 elements; h(x) chooses one of p-2 elements, and so forth.
On the contrary: encryption under a key is a permutation that's trivially invertible by decryption under the same key. On Fri, Mar 25, 2016 at 9:46 AM, Henry Baker <hbaker1@pipeline.com> wrote:
Being permutations, this representation should be closed under functional inversion, so ideally, both the "forward" and "inverse" representations should be possible.
Note: if it is easy/trivial to invert such a permutation function, such a result might call into question the use of functions of this type in crypto applications.
At 09:16 AM 3/25/2016, Dan Asimov wrote:
I'd expect that if there is such a representation, the innermost function would be the one choosing one of p elements, the next one would know from f(x) which element *not* to choose, and would pick one of the p-1 remaining elements, etc.
—Dan
On Mar 25, 2016, at 9:10 AM, Henryy Baker <hbaker1@pipeline.com> wrote:
With function composition, we can do the following:
f(g(h(...(q(x))...))) can be a representation of one of these p! permutations if
f(x) chooses one of p elements; g(x) chooses one of p-1 elements; h(x) chooses one of p-2 elements, and so forth.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
There's a standard way of generating a random permutation of N objects, equally applicable to 1-1 mapping a factorial-base representation to permutations: You build the permutation in an array A, indexed from 0...(N-1). Initially, Ai=i. Generate your random integer in the range 0...(N!-1) and convert it to factorial base. Or, generate a sequence of random integers in the ranges [0,1],[0,2],...,[0,N-1]. Use the factorial-base digits from right-to-left (low order digit first), or the random sequence from [0,1] to [0,N-1]. With i running from 1 to N-1, process each digit as a swap instruction for Ai, that says to swap Ai with A_digit. The first instruction says to swap A1 with either A0 or A1, with the latter being a no-op. The last instruction says to swap A[N-1] with any element of A, including a 1/N chance of self-swap-noop. This is easily converted to the functional composition form in Henry's message below. I'll guess that there's no way to make an additive or multiplicative version of the permutation polynomials, but it's only a guess. Note that f(x)=x+1 is the permutation (0123...N-1). Rich ------ Quoting Henry Baker <hbaker1@pipeline.com>:
I'm still wondering if there are simple correspondences between factorial representations and permutation polynomials.
For simplicity, let's focus only on a prime # of elements.
For example, over GF(p) there are p! permutations.
Is there a polynomial form in which we have exactly p choices for one of the coefficients, exactly p-1 choices for the next coefficient, exactly p-2 choices for the next coefficient, and so on?
What if the p basis functions are things other than monomials x, x^2, x^3, etc. ?
With function composition, we can do the following:
f(g(h(...(q(x))...))) can be a representation of one of these p! permutations if
f(x) chooses one of p elements; g(x) chooses one of p-1 elements; h(x) chooses one of p-2 elements, and so forth.
A form such as this should be relatively easy to manufacture.
So it should be possible to represent any permutation in this fully-nested "standard" form.
Are there forms involving multiplication instead of composition?
Are there forms involving addition instead of composition?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I've used a simpler algorithm, basically what Wikipedia calls "Knuth shuffles". From Wikipedia: ----- unsigned uniform(unsigned m); /* Returns a random integer 0 <= uniform(m) <= m */ void initialize_and_permute(unsigned permutation[], unsigned n) { unsigned i; for (i = 0; i < n; i++) { unsigned j = uniform(i); permutation[i] = permutation[j]; /* Swap an existing element [j] to position [i] */ permutation[j] = i; /* ...and put newly-initialized element [i] in position [j] */ } } ----- —Dan
On Mar 25, 2016, at 10:59 AM, rcs@xmission.com wrote:
There's a standard way of generating a random permutation of N objects, equally applicable to 1-1 mapping a factorial-base representation to permutations:
You build the permutation in an array A, indexed from 0...(N-1). Initially, Ai=i. Generate your random integer in the range 0...(N!-1) and convert it to factorial base. Or, generate a sequence of random integers in the ranges [0,1],[0,2],...,[0,N-1]. Use the factorial-base digits from right-to-left (low order digit first), or the random sequence from [0,1] to [0,N-1].
With i running from 1 to N-1, process each digit as a swap instruction for Ai, that says to swap Ai with A_digit. The first instruction says to swap A1 with either A0 or A1, with the latter being a no-op. The last instruction says to swap A[N-1] with any element of A, including a 1/N chance of self-swap-noop.
This is easily converted to the functional composition form in Henry's message below. I'll guess that there's no way to make an additive or multiplicative version of the permutation polynomials, but it's only a guess.
Note that f(x)=x+1 is the permutation (0123...N-1).
Rich
------ Quoting Henry Baker <hbaker1@pipeline.com>:
I'm still wondering if there are simple correspondences between factorial representations and permutation polynomials.
For simplicity, let's focus only on a prime # of elements.
For example, over GF(p) there are p! permutations.
Is there a polynomial form in which we have exactly p choices for one of the coefficients, exactly p-1 choices for the next coefficient, exactly p-2 choices for the next coefficient, and so on?
What if the p basis functions are things other than monomials x, x^2, x^3, etc. ?
With function composition, we can do the following:
f(g(h(...(q(x))...))) can be a representation of one of these p! permutations if
f(x) chooses one of p elements; g(x) chooses one of p-1 elements; h(x) chooses one of p-2 elements, and so forth.
A form such as this should be relatively easy to manufacture.
So it should be possible to represent any permutation in this fully-nested "standard" form.
Are there forms involving multiplication instead of composition?
Are there forms involving addition instead of composition?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
* Dan Asimov <dasimov@earthlink.net> [Mar 25. 2016 19:37]:
I've used a simpler algorithm, basically what Wikipedia calls "Knuth shuffles". From Wikipedia:
[...]
URL: https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
participants (6)
-
Dan Asimov -
Dan Asimov -
Henry Baker -
Joerg Arndt -
Mike Stay -
rcs＠xmission.com