<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

Data publikacji: 10 sie 2023

Zakres stron: 83 - 96

Otrzymano: 14 kwi 2023

Przyjęty: 25 kwi 2023

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

Słowa kluczowe
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

Data publikacji: 10 sie 2023

Zakres stron: 83 - 96

Otrzymano: 14 kwi 2023

Przyjęty: 25 kwi 2023

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

Słowa kluczowepseudorandomness, 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.

Słowa kluczowe
pseudorandomness, random polynomial