<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

Publié en ligne: 10 août 2023

Pages: 83 - 96

Reçu: 14 avr. 2023

Accepté: 25 avr. 2023

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

Mots clés
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

Publié en ligne: 10 août 2023

Pages: 83 - 96

Reçu: 14 avr. 2023

Accepté: 25 avr. 2023

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

Mots cléspseudorandomness, 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.

Mots clés
pseudorandomness, random polynomial