Primitive Polynomials over GF(2) - A Cryptologic Approach

摘要

Linear Feedback Shift Registers (LFSR) are important building blocks in stream cipher systems. The connection polynomials of the LFSRs need to be primitive over GF(2). Also the polynomial should have high weight and it should not have sparse multiples of moderate degree. Here we provide results which have immediate application in synthesis of connection polynomials for stream cipher systems. We show that, given any primitive polynomial f(x) of degree d there exists 2{sup}(d-1) - 1 many distinct trinomial multiples of degree less than 2{sup}d-1. Among these trinomial multiples, it is known that a trinomial of the form x{sup}((2/3)(2{sup}d-1)) + x{sup}((1/3)(2{sup}d-1)) + 1 contains all the degree d (d even) primitive polynomials as its factors. We extend this result by showing that, if d{sub}1 (even) divides d (even) and (2{sup}d-1)/3≠0 mod (2{sup}(d{sub}1) - 1), then the trinomial x{sup}((2/3)(2{sup}d-1)) + x{sup}((1/3)(2{sup}d-1)) + 1 contains all the primitive polynomials of degree d{sub}1 as its factor. We also discuss algorithmic issues in getting trinomial multiples of low degree. Next we present some results on t-nominal multiples of primitive polynomials which help us in choosing primitive polynomials that do not have sparse multiples.