Construction of Pseudorandom Number Generators
| dc.contributor.advisor | Herendi, Tamás | |
| dc.contributor.author | Padányi, Viktória | |
| dc.contributor.authorvariant | Padányi, Viktória | |
| dc.contributor.department | Informatikai tudományok doktori iskola | hu |
| dc.contributor.submitterdep | Informatikai Kar | |
| dc.contributor.submitterdep | Informatikai Kar::Számítógéptudományi Tanszék | |
| dc.date.accessioned | 2024-08-28T09:41:06Z | |
| dc.date.available | 2024-08-28T09:41:06Z | |
| dc.date.created | 2024 | |
| dc.date.defended | 2024-07-25 | |
| dc.description.abstract | Gyakran használnak álvéletlenszám-generátorokat különböző elméleti és gyakorlati problémák megoldására. Ezeket a generátorokat alkalmazzák minden olyan területen, ahol szükség van véletlenszerű tesztadatokra vagy mintákra, például mesterséges intelligencia alkalmazásokban, szimulációkban, véletlenszerű algoritmusokban vagy pedig kriptográfiában. Két módszer létezik véletlenszámok sorozatának generálására: Az előállítás történhet álvéletlenszám-generátorokkal (PRNG) és valódi véletlenszám-generátorokkal (TRNG). Az álvéletlenszám-generátorok esetében általános megközelítés, hogy a sorozat elemeit rekurzív módon számítjuk ki az előző elemekből. A rekurzió a kezdeti mag (seed) felhasználásával indítható, amelyet iteratív módon kiszámítunk, majd a véletlenszerű értékeket ennek alapján származtatjuk. Az álvéletlenszám-generálásra léteznek elméleti és gyakorlati algoritmusok. Az elméleti megközelítés esetében a műveletek tetszőleges pontosságú számokon történnek (vagy végtelen halmazon), míg a gyakorlati módszer esetén fix pontosságú számokat használunk (általában véges halmazon, gyakran algebrai struktúrával). Mindkét esetben azonban elvárás a kapott sorozat egyenletes eloszlása, amit csak véges esetre definiáltunk. Azonban a sorozatok teljesen kiszámíthatóak és rendkívül hatékonyan tömöríthetőek, így nem képesek valódi, információelméletileg bizonyítható véletlen számok előállítására. Használat szempontjából érdekes kérdés az álvéletlenszám-generátorok tulajdonsága. Az eltérő alkalmazások más-más tulajdonságokat várnak el a generátoroktól. A felhasználás során fontos szempont lehet a generátor sebessége, valamint az erőforrásigénye, illetve az adott generátorok minősége, melyek statisztikai tesztekkel mérhetők. A statisztikai tesztek kulcsfontosságúak az álvéletlenszám-generátorok elemzésében. Kutatómunkám első lépéseként összegyűjtöttem néhány használatban lévő, egyenletes eloszlású elméleti és gyakorlati álvéletlenszám-generátort. A generátorokat tulajdonságuk és a használatban lévő próbák és vizsgálatok alapján rendeztem. A NIST teszt csomaggal vizsgáltam mélyebben az felsorolt generátorokat. A kutatásom következő periódusában részletes elemzést végeztem a négyzetközép módszerek csoportjába tartozó generátorokról, tanulmányoztam, hogy milyen fontos tulajdonságokkal rendelkeznek, illetve melyek az előnyös tulajdonságaik. A Neumann-féle négyzetközép módszerre fókuszáltam, amely során a számsorozatokat úgy generáljuk, hogy a kezdeti magértéket négyzetre emeljük, majd a kapott szám középső jegyei alkotják a következő számot. A periódus hossza a kezdeti értéktől függ, és rövid ciklusúnak bizonyult, azaz rövid számsorozat után ismétli önmagát. Ezt követően az általánosított számrendszerekkel folytattam a kutatást, Neumann János négyzetközép módszerét általánosítottam kanonikus számrendszerekre. A rendszerben két számjegy van (0,1) a sorozat pedig hasonló módon van definiálva: egy megfelelően megválasztott m-bites kezdőérték a kiindulás. Négyzetre kell emelni a magot, ki kell vágni a középső m-bitet, és ez a generátor következő magja. Ezekben a számrendszerekben a műveletvégzés hasonló a racionális egészekhez, viszont az átvitel számítsa kicsit komplikáltabb. Tehát, némileg bonyolultabb az átvitel reprezentációja. Dolgozatomban egy példát használok ennek a számításnak a levezetéséhez. A disszertációmban megtalálható a négyzetközép-módszer általánosítása, illetve ezen generátorok elemzése bináris kanonikus számrendszerekben. Kutatásom másik témája az automatákkal kapcsolatos. Definiáltam egy polinom információmennyiségét a CNS polinomhoz viszonyítva, és megmutattam, hogy szoros kapcsolatban áll a számrendszerbeli reprezentáció hosszával. Eredményeim alapján sikerült igazolnom, hogy minden kanonikus számrendszer polinomhoz létezik egy véges automata, amely képes a P alapú kanonikus reprezentációban a polinomok összeadásának végrehajtására. Végül elemeztem ezeknek az automatáknak a méretét, azaz az állapotok számát. Finomítottam B. Kovács - A. Pethő számolását, amivel a számok kanonikus számrendszerekben való felírásának hossza megbecsülhető. Az elért becslések segítségével korlátokat számolhatunk a fix hosszúságú négyzetek hosszára. A továbbiakban, a műveletvégzés volt fontos. Ennek célja elsősorban az volt, hogy megvizsgáljam hogyan alakul a négyzetszámok hossza számított korlátokhoz képest. A vizsgálatok elsődlegesen a négyzetközép-módszer miatt voltak érdekesek, ezért a négyzetre emelés tulajdonságait elemeztem mind gyakorlati mind elméleti szempontból. Többek között bizonyítottam, hogy tetszőleges kanonikus számrendszerhez létezik egy átalakító automata, amely az adott számrendszerben összeadás műveletét hajtja végre. Ehhez készítettem egy algoritmust, ami meghatározza a minimális összeadó automatát, ha a számrendszer egy bináris kanonikus számrendszer. Az összeadás tulajdonságai alapján elkészítettem egy algoritmust a Gray-kód felhasználásával, amely az algebrai egész számok négyzetét. A konstrukció segítségével elemeztem a négyzetre emelés néhány tulajdonságát bináris kanonikus számrendszerekben. Kutatásom ezen részének eredménye, hogy fel tudom sorolni az összes n hosszúságú négyzetszámokat. Az értekezés utolsó fejezetében bemutatom az algoritmust és azok megfigyeléseit. | |
| dc.description.abstract | Random numbers are used in various fields of science. Their usage is a must wherever random test data or random samples are required for instance artificial intelligence applications, scientific simulations, randomized algorithm, or cryptography. Two methods are possible to generate a sequence of random numbers: generating with Pseudorandom Number Generators (PRNG) and generating with True Random Number Generators (TRNG). PRNGs are using some recursive algorithm to compute the elements of the sequence from the previous values. There are theoretical and practical recurrences: in the theoretical case the algorithms use operations on arbitrary precision numbers (or on an infinite set), while in the practical case we use operations on fixed precision numbers (i.e., the base structure is a finite set, usually with some algebraic structure). In both cases natural requirement is the uniform distribution, what we defined only for the finite case. However, the sequences are completely predictable and highly losslessly compressible by definition. It is not possible for these schemes to generate TRNs with information-theoretically provable randomness. As the first step of my research, I gathered several widely-used theoretical and practical PRNGs with uniform distributions. I categorized the generators based on their properties and the tests and examinations commonly used. I delved deeper into the listed generators using the NIST test suite. I continued my research work by analyzing PRNGs based on the Middle Square Method. I performed a detailed analysis of the generators belonging to the group of MSMs, and I studied what important properties they have and what their beneficial properties are. I focused on John von Neumann's MSMs. This method is now primarily of historical significance, as it is no longer in use due to the limitations of the sequences it generates. These sequences have extremely short period lengths, which means that after a certain number of iterations, the method will produce either the same number repeatedly or cycle back to a previously generated number, ultimately leading to a repeating pattern or converging to zero. One can start with an n-digit number (seed), which becomes the first element of the sequence. The generator seed is squared, and then the least and most significant digits are removed, leaving only the middle part of the digits of the squared number. This middle part is then used as the subsequent seed for the next iteration of the method. After that, I continued my research with generalized number systems. I generalized John von Neumann's MSM to canonical number systems (CNSs). The number system has two digits (0,1), and the sequence is defined in a similar way: the starting point is a properly chosen m-bit initial value. Square the seed, cut out the middle m-bit, and this is the next seed of the generator. The arithmetics in these number systems are similar to the arithmetics in rational integers with the classical digit representation. However, the calculation of the next digit requires a more difficult reduction operation. I used an example to derive this calculation. The exact definition of the generalized version of MSM binary CNS and the analysis properties of these generators are described in the dissertation. I tested the generators with the NIST statistical test suite. The collected most essential results will be presented. Another topic of my research was related to automata, which is summarized in the dissertation. I discussed some properties of arithmetic in canonical number systems (CNSs) over algebraic integers. I defined the information quantity of a polynomial relative to the base of the CNS and proved that it has a strong relation with the length of the representation in the number system. Based on this result, I showed that for every CNS polynomial P, there exists a finite transducer automaton executing the addition operation of polynomials in canonical representation of base P. Finally, I observed the size -- i.e., the number of states -- of such automata. I have proven, among other things, the existence of a transducer automaton that performs the addition operation in a given canonical number system, and I have provided an algorithm to determine the minimal addition automaton if the number system is binary CNS. Based on the properties of addition, I have developed an algorithm using Gray code to count the all square numbers of length n of algebraic integers. Using the construction, I analyzed some properties of squaring in binary CNS. I focused on the squaring, because it was one of the most important operation. Therefore, I applied these estimates to the square of the numbers and determined in some cases analytical bounds. Henceforth, I studied with the primary aim of being able to enumerate the square numbers and investigate how their lengths actually behave, that is, how their lengths are related to the constraints. I will present the algorithm and their observations. | |
| dc.format.extent | 103 | |
| dc.identifier.uri | https://hdl.handle.net/2437/379351 | |
| dc.language.iso | en | |
| dc.language.iso | hu | |
| dc.subject | álvéletlenszám-generátorok, PRNGs, általánosított négyzetközép módszer, GMSM, összeadó automata kanonikus számrendszerekben, automata in CNSs, | |
| dc.subject.discipline | Informatikai tudományok | hu |
| dc.subject.sciencefield | Műszaki tudományok | hu |
| dc.title | Construction of Pseudorandom Number Generators | |
| dc.title.translated | Álvéletlenszám-generátorok konstrukciója |
Fájlok
Engedélyek köteg
1 - 1 (Összesen 1)
Nincs kép
- Név:
- license.txt
- Méret:
- 1.93 KB
- Formátum:
- Item-specific license agreed upon to submission
- Leírás: