<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

Published Online: Aug 10, 2023

Page range: 83 - 96

Received: Apr 14, 2023

Accepted: Apr 25, 2023

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

Keywords
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

Published Online: Aug 10, 2023

Page range: 83 - 96

Received: Apr 14, 2023

Accepted: Apr 25, 2023

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

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

Keywords
pseudorandomness, random polynomial