It is important in cryptographic applications that the “key” used should be generated from a random seed. Thus, if the Legendre symbol sequence generated by a polynomial (as proposed by Hoffstein and Lieman) is used, that is

$$
\left\{
\left(\frac{f(1)}{p}\right),
\left(\frac{f(2)}{p}\right),
\left(\frac{f(3)}{p}\right),
\ldots,
\left(\frac{f(p)}{p}\right)
\right\},
$$

then it is important to choose the polynomial f “almost” at random.
Goubin, Mauduit, and Sárközy presented some not very restrictive conditions on the polynomial f, but these conditions may not be satisfied if we choose a “truly” random polynomial. However, how can it be guaranteed that the pseudorandom measures of the sequence should be small for almost “random” polynomials? These semi-random polynomials will be constructed with as few modifications as necessary from a truly random polynomial.