Název: Solovay-Strassenův test prvočíselnosti
Překlad názvu: Solovay-Strassen primality test
Autoři: Vyhnalová, Sára ; Kala, Vítězslav (vedoucí práce) ; Vávra, Tomáš (oponent)
Typ dokumentu: Bakalářské práce
Rok: 2019
Jazyk: slo
Abstrakt: [eng] [cze]
This thesis studies the Solovay-Strassen test for primality of an integer n, which is based on the Jacobi symbol. After formulating the basic algorithm, we compute the probability that the number n being tested is really a prime number if the Solovay-Strassen test declared it so. We further improve the computation of the probability under the assumption that n is not divisible by specific small primes, which can be easily verified. Finally, we construct a new test, as an analogy of the Solovay-Strassen test, based on the quartic residue symbol. 1 Táto práca sa venuje algoritmu na testovanie prvočíselnosti celého čísla n, založeného na výpočte Jacobiho symbolu, nazývaného Solovay-Strassenov test. Po sformulovaní samotného algoritmu odhadneme pravdepodobnosť, že testo- vané číslo n je skutočne prvočíslo, ak to o ňom vyhlásil Solovay-Strassenov test. Práca ponúka aj vylepšenie výpočtu využívajúce, že n nie je deliteľné konkrét- nymi malými prvočíslami, čo môžeme veľmi jednoducho overiť. V záverečnej časti ide o konštrukciu vlastného testu, ako obdoby k Solovay-Strassenovmu testu, za- loženého na výpočte kvartického symbolu. 1
Klíčová slova: Jacobiho symbol; kvartický symbol; Solovay-Strassenov test; Jacobi symbol; quartic symbol; Solovay-Strassen test

Instituce: Fakulty UK (VŠKP) (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři UK.
Původní záznam: http://hdl.handle.net/20.500.11956/107791

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-398701


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Univerzita Karlova > Fakulty UK (VŠKP)
Vysokoškolské kvalifikační práce > Bakalářské práce