On the distinctness of maximal length sequences over Z/(pq) modulo 2

This paper studies the distinctness problem of the reductions modulo 2 of maximal length sequences over Z/(pq), where p and q are two different odd primes with p < q. A polynomial f (x) over Z/(pq) is called primitive if f (x) modulo p and f (x) modulo q are primitive over Z/(p) and Z/(q), respectively. A primitive element in Z/(pq) is defined analogously. Let a and b be two maximal length sequences generated by a primitive polynomial f (x) over Z/(pq). Firstly, for the case of deg f (x) > 1, it is proved that if there exist a nonnegative integer S and a primitive element xi in Z/(pq) such that x(S) - xi equivalent to 0 (mod f(x), pq), and either (q - 1) is not divisible by (p - 1) or 2(p - 1) divides (q - 1), then a equivalent to b (mod 2) if and only if a = b. The existence of S and is completely determined by p, q and deg f(x). Secondly, for the case of deg f (x) = 1, it is proved that if gcd(p - 1, q - 1) = 2 and (p - 1)/ord(p)(2) is congruent to (q - 1)/ord(q)(2) modulo 2, then a - b (mod 2) if and only if a = b. (c) 2008 Elsevier Inc. All rights reserved.