Andreas Gidstedt: Primalitetstest
Tid: Må 2021-08-23 kl 09.00 - 10.00
Plats: Zoom, meeting ID: 640 6342 1581 (password required, contact arias@math.su.se)
Respondent: Andreas Gidstedt
Sammanfattning: Samhället vi lever i idag blir allt mer digitalt och digital säkerhet blir med det mer och mer viktigt. Digital säkerhet handlar om att kunna skydda uppgifter en utomstående inte ska kunna ta del av. Till exempel bankuppgifter, lösenord, läkarjournaler etc. Dessa uppgifter krypteras för att förbli privata och för att kryptera behövs stora primtal. Ju större talen är desto längre tid tar det att avgöra om talet är ett primtal. Därför utvecklas metoder för att avgöra detta på ett effektivt sätt, primalitetstest. Detta arbetet kommer behandla framför allt primalitetstesten Solovay–Strassen, Miller–Rabin samt AKS-test. Hur de grundar sig, dess komplexitet och något hur de förhåller sig till varandra.
Abstract: The society we live in today is becoming more digital and by that digital security is becoming more important than before. Digital security is about protecting our information from outsiders, for example bank information, passwords, medical records, etc. This information is encrypted in order to remain private and to encrypt data we need large prime numbers. As the number becomes larger, the longer it takes to determine if the number is a prime number. Therefore, methods are being developed to determine this in an efficient way, primality testing. This work mainly covers the primality tests Solovay–Strassen, Miller–Rabin and AKS-test. How they are based, their complexity and something about how they relate to each other.