Period of the power generator and small values of Carmichael’s function

Consider the pseudorandom number generator<disp-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="u Subscript n Baseline identical-to u Subscript n minus 1 Superscript e Baseline left-parenthesis mod m right-parenthesis comma 0 less-than-or-equal-to u Subscript n Baseline less-than-or-equal-to m minus 1 comma n equals 1 comma 2 comma ellipsis comma"><mml:semantics><mml:mrow><mml:msub><mml:mi>u</mml:mi><mml:mi>n</mml:mi></mml:msub><mml:mo>≡</mml:mo><mml:msubsup><mml:mi>u</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi>n</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow><mml:mi>e</mml:mi></mml:msubsup><mml:mspace width="0.667em"/><mml:mo stretchy="false">(</mml:mo><mml:mi>mod</mml:mi><mml:mspace width="0.333em"/><mml:mi>m</mml:mi><mml:mo stretchy="false">)</mml:mo><mml:mo>,</mml:mo><mml:mspace width="1em"/><mml:mn>0</mml:mn><mml:mo>≤</mml:mo><mml:msub><mml:mi>u</mml:mi><mml:mi>n</mml:mi></mml:msub><mml:mo>≤</mml:mo><mml:mi>m</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn><mml:mo>,</mml:mo><mml:mspace width="1em"/><mml:mi>n</mml:mi><mml:mo>=</mml:mo><mml:mn>1</mml:mn><mml:mo>,</mml:mo><mml:mn>2</mml:mn><mml:mo>,</mml:mo><mml:mo>…</mml:mo><mml:mo>,</mml:mo></mml:mrow><mml:annotation encoding="application/x-tex">\begin{equation*} u_n\equiv u_{n-1}^e\pmod {m},\quad 0\le u_n\le m-1,\quad n=1,2,\ldots , \end{equation*}</mml:annotation></mml:semantics></mml:math></disp-formula>where we are given the modulus<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="m"><mml:semantics><mml:mi>m</mml:mi><mml:annotation encoding="application/x-tex">m</mml:annotation></mml:semantics></mml:math></inline-formula>, the initial value<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="u 0 equals theta"><mml:semantics><mml:mrow><mml:msub><mml:mi>u</mml:mi><mml:mn>0</mml:mn></mml:msub><mml:mo>=</mml:mo><mml:mi>ϑ</mml:mi></mml:mrow><mml:annotation encoding="application/x-tex">u_0=\vartheta</mml:annotation></mml:semantics></mml:math></inline-formula>and the exponent<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="e"><mml:semantics><mml:mi>e</mml:mi><mml:annotation encoding="application/x-tex">e</mml:annotation></mml:semantics></mml:math></inline-formula>. One case of particular interest is when the modulus<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="m"><mml:semantics><mml:mi>m</mml:mi><mml:annotation encoding="application/x-tex">m</mml:annotation></mml:semantics></mml:math></inline-formula>is of the form<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="p l"><mml:semantics><mml:mrow><mml:mi>p</mml:mi><mml:mi>l</mml:mi></mml:mrow><mml:annotation encoding="application/x-tex">pl</mml:annotation></mml:semantics></mml:math></inline-formula>, where<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="p comma l"><mml:semantics><mml:mrow><mml:mi>p</mml:mi><mml:mo>,</mml:mo><mml:mi>l</mml:mi></mml:mrow><mml:annotation encoding="application/x-tex">p,l</mml:annotation></mml:semantics></mml:math></inline-formula>are different primes of the same magnitude. It is known from work of the first and third authors that for moduli<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="m equals p l"><mml:semantics><mml:mrow><mml:mi>m</mml:mi><mml:mo>=</mml:mo><mml:mi>p</mml:mi><mml:mi>l</mml:mi></mml:mrow><mml:annotation encoding="application/x-tex">m=pl</mml:annotation></mml:semantics></mml:math></inline-formula>, if the period of the sequence<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="left-parenthesis u Subscript n Baseline right-parenthesis"><mml:semantics><mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mi>u</mml:mi><mml:mi>n</mml:mi></mml:msub><mml:mo stretchy="false">)</mml:mo></mml:mrow><mml:annotation encoding="application/x-tex">(u_n)</mml:annotation></mml:semantics></mml:math></inline-formula>exceeds<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="m Superscript 3 slash 4 plus epsilon"><mml:semantics><mml:msup><mml:mi>m</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mn>3</mml:mn><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>/</mml:mo></mml:mrow><mml:mn>4</mml:mn><mml:mo>+</mml:mo><mml:mi>ε</mml:mi></mml:mrow></mml:msup><mml:annotation encoding="application/x-tex">m^{3/4+\varepsilon }</mml:annotation></mml:semantics></mml:math></inline-formula>, then the sequence is uniformly distributed. We show rigorously that for almost all choices of<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="p comma l"><mml:semantics><mml:mrow><mml:mi>p</mml:mi><mml:mo>,</mml:mo><mml:mi>l</mml:mi></mml:mrow><mml:annotation encoding="application/x-tex">p,l</mml:annotation></mml:semantics></mml:math></inline-formula>it is the case that for almost all choices of<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="theta comma e"><mml:semantics><mml:mrow><mml:mi>ϑ</mml:mi><mml:mo>,</mml:mo><mml:mi>e</mml:mi></mml:mrow><mml:annotation encoding="application/x-tex">\vartheta ,e</mml:annotation></mml:semantics></mml:math></inline-formula>, the period of the power generator exceeds<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="left-parenthesis p l right-parenthesis Superscript 1 minus epsilon"><mml:semantics><mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:mi>p</mml:mi><mml:mi>l</mml:mi><mml:msup><mml:mo stretchy="false">)</mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:mn>1</mml:mn><mml:mo>−</mml:mo><mml:mi>ε</mml:mi></mml:mrow></mml:msup></mml:mrow><mml:annotation encoding="application/x-tex">(pl)^{1-\varepsilon }</mml:annotation></mml:semantics></mml:math></inline-formula>. And so, in this case, the power generator is uniformly distributed. We also give some other cryptographic applications, namely, to ruling-out the cycling attack on the RSA cryptosystem and to so-called time-release crypto. The principal tool is an estimate related to the Carmichael function<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="lamda left-parenthesis m right-parenthesis"><mml:semantics><mml:mrow><mml:mi>λ</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>m</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:mrow><mml:annotation encoding="application/x-tex">\lambda (m)</mml:annotation></mml:semantics></mml:math></inline-formula>, the size of the largest cyclic subgroup of the multiplicative group of residues modulo<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="m"><mml:semantics><mml:mi>m</mml:mi><mml:annotation encoding="application/x-tex">m</mml:annotation></mml:semantics></mml:math></inline-formula>. In particular, we show that for any<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="normal upper Delta greater-than-or-equal-to left-parenthesis log log upper N right-parenthesis cubed"><mml:semantics><mml:mrow><mml:mi mathvariant="normal">Δ</mml:mi><mml:mo>≥</mml:mo><mml:mo stretchy="false">(</mml:mo><mml:mi>log</mml:mi><mml:mo>⁡</mml:mo><mml:mi>log</mml:mi><mml:mo>⁡</mml:mo><mml:mi>N</mml:mi><mml:msup><mml:mo stretchy="false">)</mml:mo><mml:mn>3</mml:mn></mml:msup></mml:mrow><mml:annotation encoding="application/x-tex">\Delta \ge (\log \log N)^3</mml:annotation></mml:semantics></mml:math></inline-formula>, we have<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="lamda left-parenthesis m right-parenthesis greater-than-or-equal-to upper N exp left-parenthesis negative normal upper Delta right-parenthesis"><mml:semantics><mml:mrow><mml:mi>λ</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>m</mml:mi><mml:mo stretchy="false">)</mml:mo><mml:mo>≥</mml:mo><mml:mi>N</mml:mi><mml:mi>exp</mml:mi><mml:mo>⁡</mml:mo><mml:mo stretchy="false">(</mml:mo><mml:mo>−</mml:mo><mml:mi mathvariant="normal">Δ</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:mrow><mml:annotation encoding="application/x-tex">\lambda (m)\ge N\exp (-\Delta )</mml:annotation></mml:semantics></mml:math></inline-formula>for all integers<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="m"><mml:semantics><mml:mi>m</mml:mi><mml:annotation encoding="application/x-tex">m</mml:annotation></mml:semantics></mml:math></inline-formula>with<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="1 less-than-or-equal-to m less-than-or-equal-to upper N"><mml:semantics><mml:mrow><mml:mn>1</mml:mn><mml:mo>≤</mml:mo><mml:mi>m</mml:mi><mml:mo>≤</mml:mo><mml:mi>N</mml:mi></mml:mrow><mml:annotation encoding="application/x-tex">1\le m\le N</mml:annotation></mml:semantics></mml:math></inline-formula>, apart from at most<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper N exp left-parenthesis minus 0.69 left-parenthesis normal upper Delta log normal upper Delta right-parenthesis Superscript 1 slash 3 Baseline right-parenthesis"><mml:semantics><mml:mrow><mml:mi>N</mml:mi><mml:mi>exp</mml:mi><mml:mo>⁡</mml:mo><mml:mrow><mml:mo>(</mml:mo><mml:mo>−</mml:mo><mml:mn>0.69</mml:mn><mml:msup><mml:mrow><mml:mo>(</mml:mo><mml:mi mathvariant="normal">Δ</mml:mi><mml:mi>log</mml:mi><mml:mo>⁡</mml:mo><mml:mi mathvariant="normal">Δ</mml:mi><mml:mo>)</mml:mo></mml:mrow><mml:mrow class="MJX-TeXAtom-ORD"><mml:mn>1</mml:mn><mml:

Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.