Random polynomials in Legendre sequences

Gyarmati, Katalin and Müllner, Károly (2022) Random polynomials in Legendre sequences. Acta Arithmetica. ISSN 0065-1036 (print), 1730-6264 (online) (Submitted)

Preview

Text ottis.pdf Download (166kB) | Preview

Abstract

It is crucial in pseudorandomness cryptographic applications that the smaller key used as a seed can be generated at random. Thus, if the Legendre sequence based on a polynomial (as proposed by Hoffstein and Lieman) is used, then it is important to choose the polynomial $f$ at random in the construction. Goubin, Mauduit, and Sárközy presented some non-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 ensured that the sequence's pseudorandom measures are always low for nearly "random" polynomials? These semirandom polynomials will be constructed with as few modifications as necessary from a truly random polynomial.

Actions (login required)

Edit Item