W pracy oszacowano średnią złożoność obliczeniową probabilistycznego algorytmu wyszukiwania pierwiastków pierwotnych modulo n. Uzyskany wynik może być w naturalny sposób uogólniony na przypadek algorytmu wyszukiwania generatorów dowolnej skończonej grupy cyklicznej jeśli znamy rozkład na czynniki pierwsze rzędu tej grupy.
EN
Primitive roots from a natural number n (i.e. generators of the multiplicative group Z* n) play an important role in many cryptographic algorithms like public key ciphers, digital signatures and key agreement algorithms. In the paper, proof of correctness of the probabilistic algorithm for finding primitive roots is given along with assessment of its average computational complexity. Results obtained for the multiplicative group Z* n can be in natural easy way generalized on the case of arbitrary finite cyclic groups.
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.