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 |
|
|---|
| Research Field |
|
|---|
| 关键词 |
|
|---|
| Committee Chair / Thesis Advisor |
|
|---|
| Committee Members |
|
|---|
