Fredrik Huss: Var är nyckeln? En introduktion till primtalstester inom kryptografi

Abstract: This thesis aims to provide an introduction to primality tests within cryptography through 5 overarching questions. We review the history of cryptography to see the role of mathematics in cryptography, especially in relation to primality tests. We also analyze the role of primality tests in cryptography and examine what primality tests are through a few examples. The main primality tests discussed in this introduction are Miller Rabin´s primality test and the AKS primality test. In summary, the result of this thesis is as follows. The role of primality tests within cryptography is a tool to create keys needed to encrypt messages in asymmetric cryptography. Primality tests work through the trial of an integer n with an aspect unique to primes. Primality tests can be categorized into two groups. One is a probabilistic test, where, through multiple trials with witnesses, one can determine if an integer is a probable prime or not. Examples given are Fermat's primality test and Miller-Rabin's primality test. A deterministic primality test gives a definitive answer to whether an integer n is prime or not. Examples of deterministic primality tests given in this paper are Wilsons primality test and AKS primality test. Finally, we attempt to examine the practicality of primality tests in a cryptographic context through a comparison between the Miller-Rabin test and the AKS-test through the O-notation. We see that the AKS test is more complex than the Miller-Rabin test, and thus less practical within a cryptographic context, where speed and ease of use are the key to practicality.