Primality Testing and Integer Factorization Using Elliptic Curves Pubblico

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	Emory College
Department	Mathematics
Degree	BS
Submission	Honors Thesis
Language	English
Research Field	Applied Mathematics Theoretical Mathematics
Parola chiave	Prime Curve Elliptic Primality Testing Factor Math
Committee Chair / Thesis Advisor	Ono, Ken, Emory University
Committee Members	Brody, Jed, Emory University Nagy, James, Emory University

Ultima modifica

Primary PDF

Thumbnail	Title	Date Uploaded	Actions
	Primality Testing and Integer Factorization Using Elliptic Curves ()	2018-08-28 15:45:18 -0400	Press to Select an action Download

Supplemental Files

Thumbnail	Title	Date Uploaded	Actions
	ThesisReferences.tex ()	2018-08-28 15:45:31 -0400	Press to Select an action Download