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.

Table of Contents

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

About this Honors Thesis

Rights statement
  • Permission granted by the author to include this thesis or dissertation in this repository. All rights reserved by the author. Please contact the author for information regarding the reproduction and use of this thesis or dissertation.
School
Department
Degree
Submission
Language
  • English
Research field
Keyword
Committee Chair / Thesis Advisor
Committee Members
Last modified

Primary PDF

Supplemental Files