<abstract xmlns="http://www.w3.org/1999/xhtml">

<p>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
<disp-formula>
<alternatives>
<graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/j_udt-2023-0006_eq_001.png"></graphic>
<math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="block"><mrow><mrow><mo>{</mo> <mrow><mrow><mo>(</mo><mrow><mfrac><mrow><mi>f</mi><mrow><mo>(</mo><mn>1</mn><mo>)</mo></mrow></mrow><mi>p</mi></mfrac></mrow><mo>)</mo></mrow><mo>,</mo><mrow><mo>(</mo><mrow><mfrac><mrow><mi>f</mi><mrow><mo>(</mo><mn>2</mn><mo>)</mo></mrow></mrow><mi>p</mi></mfrac></mrow><mo>)</mo></mrow><mo>,</mo><mrow><mo>(</mo><mrow><mfrac><mrow><mi>f</mi><mrow><mo>(</mo><mn>3</mn><mo>)</mo></mrow></mrow><mi>p</mi></mfrac></mrow><mo>)</mo></mrow><mo>,</mo><mo>⋯</mo><mo>,</mo><mrow><mo>(</mo><mrow><mfrac><mrow><mi>f</mi><mrow><mo>(</mo><mi>p</mi><mo>)</mo></mrow></mrow><mi>p</mi></mfrac></mrow><mo>)</mo></mrow></mrow> <mo>}</mo></mrow><mo>,</mo></mrow></math>
<tex-math>\left\{ {\left( {{{f\left( 1 \right)} \over p}} \right),\left( {{{f\left( 2 \right)} \over p}} \right),\left( {{{f\left( 3 \right)} \over p}} \right), \cdots ,\left( {{{f\left( p \right)} \over p}} \right)} \right\},</tex-math>
</alternatives>
</disp-formula>
then it is important to choose the polynomial <italic>f</italic> “almost” at random. Goubin, Mauduit, and Sárközy presented some not very restrictive conditions on the polynomial <italic>f</italic>, 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 semirandom polynomials will be constructed with as few modifications as necessary from a truly random polynomial.</p>
</abstract>

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



{ (f(1)p),(f(2)p),(f(3)p),⋯,(f(p)p) },
\left\{ {\left( {{{f\left( 1 \right)} \over p}} \right),\left( {{{f\left( 2 \right)} \over p}} \right),\left( {{{f\left( 3 \right)} \over p}} \right), \cdots ,\left( {{{f\left( p \right)} \over 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 semirandom polynomials will be constructed with as few modifications as necessary from a truly random polynomial.

Random Polynomials in Legendre Symbol Sequences

Uniform distribution theory

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

{"article-title":"Random Polynomials in Legendre Symbol Sequences"}

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...

Random Polynomials in Legendre Symbol Sequences

Publicado en línea: 10 ago 2023

Páginas: 83 - 96

Recibido: 14 abr 2023

Aceptado: 25 abr 2023

DOI: https://doi.org/10.2478/udt-2023-0006

Palabras clave
pseudorandomness, random polynomial

© 2023 Katalin Gyarmati et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Random Polynomials in Legendre Symbol Sequences

Publicado en línea: 10 ago 2023

Páginas: 83 - 96

Recibido: 14 abr 2023

Aceptado: 25 abr 2023

DOI: https://doi.org/10.2478/udt-2023-0006

Palabras clavepseudorandomness, random polynomial

© 2023 Katalin Gyarmati et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Palabras clave
pseudorandomness, random polynomial