Analysis of Probability Primality Tests

Prosti brojevi su temelj operacije racunalnog kriptiranja javnog klju ˇ ca. Budu ˇ ci da ´ pronalazak takvih velikih brojeva nije trivijalan, razvijeni su testovi pomocu kojih je ´ moguce determinirati prostost brojeva. U radu su prou ´ cavana dva vjerojatnostna testa ˇ prostosti, Miller-Rabinov te Solovay-Strassenov, njihove prednosti i nedostaci. Testovi su implementirani u programskom jeziku Python te je na primjerima velikih prostih brojeva pokazana njihova uspješnost.Prime numbers are the basis of the public-key encryption operation. Since it is very hard to find very large prime numbers, various tests are developed to determine if the nubmer is prime or not. In this thesis are analyzed two probability primality tests, Miller-Rabin and Solovay-Strassen, their advantages and disadvantages. Tests are implemented in programming language Python. On the examples of large prime numbers is shown efficiency of the tests