Prev: Is encrypting twice much more secure?
Next: Basics of encrypting
From: Mok-Kong Shen on 12 Jan 2010 17:45

In [1] there is the following theorem:

Let P(x) = a_0 + a_1 x + ... + a_d x^d be a polynomial with integer
coefficients. Then P(x) is a permutation polynomial modulo n=2^w,
w>=2, if and only if a_1 is odd, (a_2 +a_4 +a_6 + ...) is even, and
(a_3 + a_5 + a_7 + ...) is even.

In [2] there is the following theorem due to Hull and Dobell (where
'linear congruential sequence' denotes X_(n+1)=(a X_n + c) mod m ):

The linear congruential sequence defined by m, a, c, and X_0 has
period length m if and only if
i) c is relatively prime to m;
ii) b = a - 1 is a multiple of p, for every prime p dividing m;
iii) b is a multiple of 4, if m is a multiple of 4.

Now let's consider in the notation of [1] the following polynomial:

P(x) = a_0 + a_1 x mod 2^w w>=2

For P(x) to be a permutation polynomial (which is equivalent here
to the sequence having period length 2^w), [1] requires only that
a_1 is odd, while [2] requires a_1 = 1 mod 4, which is a stronger
requirement.

Apparently there is a discrepancy between the two theorems. Could
someone kindly tell which of the two requirements is correct, and why?

Thanks.

M. K. Shen

---------------------------------------------------------------
[1] R. L. Rivest, Permutaion Polynomials Modulo 2^w, Finite Fields
and Their Applications 7, 2001, p.289.

[2] D. E. Knuth, The Art of Computer Programming, Vol. 2, 3rd ed. p.17.
From: Mok-Kong Shen on 12 Jan 2010 18:37
Mok-Kong Shen wrote:

> P(x) = a_0 + a_1 x mod 2^w w>=2
>
> For P(x) to be a permutation polynomial (which is equivalent here
> to the sequence having period length 2^w), [1] requires only that
> a_1 is odd, while [2] requires a_1 = 1 mod 4, which is a stronger
> requirement.

[Addendum]

[2] requires in addition that a_0 is odd.

M. K. Shen
From: Maaartin on 13 Jan 2010 04:55
On Jan 12, 11:45 pm, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote:
> In [1] there is the following theorem:
>
>    Let P(x) = a_0 + a_1 x + ... + a_d x^d be a polynomial with integer
>    coefficients. Then P(x) is a permutation polynomial modulo n=2^w,
>    w>=2, if and only if a_1 is odd, (a_2 +a_4 +a_6 + ...) is even, and
>    (a_3 + a_5 + a_7 + ...) is even.
>
> In [2] there is the following theorem due to Hull and Dobell (where
> 'linear congruential sequence' denotes X_(n+1)=(a X_n + c) mod m ):
>
>    The linear congruential sequence defined by m, a, c, and X_0 has
>    period length m if and only if
>      i) c is relatively prime to m;
>     ii) b = a - 1 is a multiple of p, for every prime p dividing m;
>    iii) b is a multiple of 4, if m is a multiple of 4.
>
> Now let's consider in the notation of [1] the following polynomial:
>
>    P(x) = a_0 + a_1 x  mod 2^w  w>=2
>
> For P(x) to be a permutation polynomial (which is equivalent here
> to the sequence having period length 2^w), [1] requires only that
> a_1 is odd, while [2] requires a_1 = 1 mod 4, which is a stronger
> requirement.
>
> Apparently there is a discrepancy between the two theorems. Could
> someone kindly tell which of the two requirements is correct, and why?
>
> Thanks.
>
> M. K. Shen
>
> ---------------------------------------------------------------
> [1] R. L. Rivest, Permutaion Polynomials Modulo 2^w, Finite Fields
> and Their Applications 7, 2001, p.289.
>
> [2] D. E. Knuth, The Art of Computer Programming, Vol. 2, 3rd ed. p.17.

Most probably both of them. First of all, the conclusions are very
different, [1] states that the polynomial is invertible, [2] states
that it generates a sequence of maximum length. The identity function
is invertible, but generates a sequence of length 1. Moreover, the
requirements are not contradictory. One of them could be stronger than
the other, but even that doesn't hold. There're just different.
From: Mok-Kong Shen on 13 Jan 2010 06:12
Mok-Kong Shen wrote:
>
[snip]
> Apparently there is a discrepancy between the two theorems. Could
> someone kindly tell which of the two requirements is correct, and why?

I have figured out my misunderstanding. With [2], computing
x_(i+1)=P(x_i) recursively gives a permutation of [0,2^w-1] that is
not decomposable into cycles, while with [1], input of [0,2^w-1]
to P(x) gives a permutation but may or may not be decomposable into
cycles, i.e. the recursive computation may under circumstances not
function.

To generate a permutation that is not decomposable into cycles, i.e.
as with [2] but for polynomials of higher degrees, one has to use
the work [3], with criteria that can stated as follows [4]:

a_3 + a_5 + a_7 + ... = 2*a_2 mod 4

a_4 + a_6 + a_8 + ... = a_1 + a_2 - 1 mod 4

a_1 = 1 mod 2

a_0 = 1 mod 2

It may be mentioned that [3] was known in discussions in our group in
Feb. 1998 and that computation of the inverse of P(x)=y may be done
for P(x) satisfying either set of criteria with w evaluations of P(x).

M. K. Shen

-----------------------------------------------------------------------
[3] V.S.Anashin, "Uniformly distrbuted sequences of p-adic integers",
Mathematical Notes, Vol. 55, No. 2, 1994, pp. 109 - 133.

[4] V. Anashin, A. Khrennikov, Applied Algebraic Dynamics, Berlin,
2009, p.283.


From: wizzi fig on 14 Jan 2010 13:21
On Jan 13, 6:12 am, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote:
> To generate a permutation that is not decomposable into cycles ...

If P is a permutation, the sequence P(0), P(1), ... , P(2^w-1)
produces each value 0..2^w-1 exactly once. The function H that maps P
(i) to P(i+1) is thus "a permutation that is not decomposable into
cycles". H(x) = P(P'(x)+1), where P'(x) is the inverse of P. P' is
also a polynomial (because if g=GCD(periods of cycles of P), P
composed with itself g-1 times is P'). Thus H is also a polynomial.
In the general case H has high degree (even after powers are reduced
for equivalences modulo 2^w).

Bob H (via a send-only email address)

 |  Next  |  Last
Pages: 1 2 3 4 5 6 7
Prev: Is encrypting twice much more secure?
Next: Basics of encrypting