| Popis: |
Title: Frobenius primality tests Author: Jan Hora Department: Department of algebra Supervisor: prof. RNDr. Aleš Drápal, CSc. Dsc. Supervisor's e-mail address: drapal@karlin.mff.cuni.cz Abstract: In the present work we study Extended Quadratic Frobenius primality test. We study its functionality, error probability and taken time. We will define ring R(n, c), in which the test works. We will describe its structure depending up primality of tested number n, and algorithm of Frobenius test. We will show, that test succeeds anytime the tested number n is prime. We will study the upper bound for error probability of the test. We will show that test fails iff certain elements of set R(n, c) are chosen, Set of that elements will be denoted G(n, c). We will find conditions that G(n, c) must fulfil, and with them we will discover, that Frobenius test eroor probability is at most 1 24. We will analyse individual parts of algorithm and discover, that one cyclus of Frobenius test can be done with approximately 2 log n multiplications in Zn. Finaly the teoretical estimates will be compared with practical results. Keywords: primality test, Frobenius automorfism, cyklic group, roots of one 1 |
