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

AbstractThis 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 degf(x)>1, it is proved that if there exist a nonnegative integer S and a primitive element ξ in Z/(pq) such that xS−ξ≡0(modf(x),pq), and either (q−1) is not divisible by (p−1) or 2(p−1) divides (q−1), then a̲≡b̲(mod2) if and only if a̲=b̲. The existence of S and ξ is completely determined by p, q and degf(x). Secondly, for the case of degf(x)=1, it is proved that if gcd(p−1,q−1)=2 and (p−1)/ordp(2) is congruent to (q−1)/ordq(2) modulo 2, then a̲≡b̲(mod2) if and only if a̲=b̲