Short cycles in repeated exponentiation modulo a prime (Q977189): Difference between revisions

From MaRDI portal
Importer (talk | contribs)
Created a new Item
 
Import241208061232 (talk | contribs)
Normalize DOI.
 
(7 intermediate revisions by 6 users not shown)
Property / DOI
 
Property / DOI: 10.1007/s10623-009-9339-2 / rank
Normal rank
 
Property / author
 
Property / author: L. Yu. Glebskiĭ / rank
Normal rank
 
Property / author
 
Property / author: L. Yu. Glebskiĭ / rank
 
Normal rank
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W2082462116 / rank
 
Normal rank
Property / arXiv ID
 
Property / arXiv ID: 0908.3920 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Product Sets of Rationals, Multiplicative Translates of Subgroups in Residue Rings, and Fixed Points of the Discrete Logarithm / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4541859 / rank
 
Normal rank
Property / cites work
 
Property / cites work: On polynomial approximation of the discrete logarithm and the Diffie-Hellman mapping. / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the security of modular exponentiation with application to the construction of pseudorandom generators / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4737502 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4664850 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Some heuristics and results for small cycles of the discrete logarithm / rank
 
Normal rank
Property / cites work
 
Property / cites work: Interpolation of the Double Discrete Logarithm / rank
 
Normal rank
Property / cites work
 
Property / cites work: Intervals Contained in Arithmetic Combinations of Sets / rank
 
Normal rank
Property / DOI
 
Property / DOI: 10.1007/S10623-009-9339-2 / rank
 
Normal rank
links / mardi / namelinks / mardi / name
 

Latest revision as of 10:55, 10 December 2024

scientific article
Language Label Description Also known as
English
Short cycles in repeated exponentiation modulo a prime
scientific article

    Statements

    Short cycles in repeated exponentiation modulo a prime (English)
    0 references
    0 references
    0 references
    21 June 2010
    0 references
    Given a prime \(p\) and an integer \(g\) with gcd\((g, p) = 1\) one can consider the dynamical system generated by consecutive exponentiations modulo \(p\) where \(g\) serves as the base. More precisely, one can define the map \(f_g(u)\) by the conditions \(f_g(u) \equiv g^u\) (mod \(p\)) and \(0 \leq f_g(u) \leq p - 1\), and for some initial value \(u_0\) consider sequences of consecutive iteration \(u_n = f_g(u_{n-1}), n = 1, 2, \cdots\). This map is in particular used in a number of constructions of cryptographically secure pseudorandom generators. For an integer \(k\) one denotes by \(N_g(k)\) the number of \(u_0 \in {1,\cdots , p-1}\) such that for the above sequence we have \(u_k = u_0\). The authors obtained nontrivial upper bounds on the number of fixed points and short cycles in the above dynamical system, they proved, among other things, the following: Theorem. Let \(p\) be a prime. Then \(N_g(3) \leq \frac{3}{4}p + (\frac{g^{2g+1}+g+1}{4})\).
    0 references
    discrete logarithm
    0 references
    cycle
    0 references
    dynamical system
    0 references

    Identifiers