# Primality Testing and Integer Factorization Using Elliptic Curves Open Access

## Wilson, Andrew Lawrence (2017)

Permanent URL: https://etd.library.emory.edu/concern/etds/79407z01j?locale=en
Published

## Abstract

Testing integers for primality and factoring large integers is an extremely important subject for our daily lives. Every time we use a credit card to make online purchases we are relying on the difficulty of factoring large integers for the security of our personal information. Similar encryption methods are used by governments around the world to protect their classified information, stressing the importance of the subject of primality testing and factoring algorithms to both personal and national security. Elementary number theory has been a key tool in the foundation of primality testing and factoring algorithms, specifically the work of Euler and Fermat, whose developments on modular arithmetic give us key tools that we still use today in the more complex primality tests and factoring methods. More recently people have used deeper ideas from geometry, namely elliptic curves, to develop faster tests and algorithms. In this thesis we continue this trend, and develop new primality tests that utilize previous theory of elliptic curves over finite fields. The primary point is that the points on these curves form a special group, which breaks down when working over Z/NZ, when N is not prime. Our theorems make use of the work of Kubert, Hasse, Mazur, and many more to yield a primality test that gives no false positives.

Contents

1 Introduction and Statement of Results 2 Background Number Theory and Factoring Algorithms 2.1 RSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.2 Fermat's Little Theorem . . . . . . . . . . . . . . . . . . . . . . . 4 2.2.1 Fermat's Little Theorem . . . . . . . . . . . . . . . . . . . 5 2.2.2 Fermat Primality Test . . . . . . . . . . . . . . . . . . . . 6 2.3 Rabin-Miller Test . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.4 Pollard's p-1 Method . . . . . . . . . . . . . . . . . . . . . . . . 8 3 Elliptic Curve Primality Testing and Factorization 3.1 Rational Points and the Group Law . . . . . . . . . . . . . . . . 10 3.2 Theorems of Mazur, Nagell-Lutz, and Kubert . . . . . . . . . . . 13 3.3 Elliptic Curve Primality Tests and Factoring Algorithms . . . . . 20 3.3.1 Goldwasser-Killian Test . . . . . . . . . . . . . . . . . . . 20 3.3.2 Lenstra's Elliptic Curve Factoring Algorithm . . . . . . . 21 4 New Developments 4.1 Alternative Representations of Elliptic Curves . . . . . . . . . . . 23 4.2 Generalization of Kubert's Table to Weierstrass Normal Form . . 27 4.3 New Tests for Primality . . . . . . . . . . . . . . . . . . . . . . . 28 5 Concluding Remarks. . . . . . . . . . . . . . . . . . . . . . . 34 References . . . . . . . . . . . . . . . . . . . . . . .36