Kasyanov Alexandr Vladimirovich (Postgraduate student
Saint Petersburg Electrotechnical University «LETI»;
Researcher at the Cryptographic Analysis Department
Special Technology Center (STC LLC), Saint Petersburg, Russia
)
| |
In the context of exponential growth in cyber threats, the task of developing and analyzing pseudorandom number generators is becoming increasingly important. As of today, the relevance of the issue concerning finiteness of the period of generated sequences remains, due to the deterministic nature of the algorithms implemented on computing machines. Purpose of the study – to demonstrate the fundamental impossibility of constructing a generator with an infinite period based on a finite automaton, which is a mathematical model of a computing machine. The research is based on formal methods of finite automata theory, including the application of Kleene’s theorem to establish equivalence between pseudo-random number generator algorithms and finite automata, and the theorem on the impossibility of recognizing non-periodic sequences, which justifies the finiteness of the period. The analysis performed in the framework of automata theory demonstrates that pseudorandom number generation algorithms can be implemented as finite automata, and are therefore subject to the limitation of the number of internal states and, consequently, the finiteness of the period of the generated sequence. Scientific novelty lies in the explicit application of theoretical results of finite automaton theory to justify the limitation of the period of pseudorandom number generators. The results obtained contribute to the understanding of the fundamental limitations imposed by the computing environment on the properties of generated sequences.
Keywords:algorithm, finite automata, regular expressions, non-periodic infinite sequences, Kleene’s theorem, pseudorandom number generators
|
|
| |
|
Read the full article …
|
Citation link:
Kasyanov A. V. PERIODICITY OF RANDOM NUMBER GENERATORS BUILT ON A COMPUTING MACHINE // Современная наука: актуальные проблемы теории и практики. Серия: Естественные и Технические Науки. -2025. -№07. -С. 112-116 DOI 10.37882/2223-2966.2025.07.20 |
|
|
LEGAL
INFORMATION:
