ATKIN’S ECPP (Elliptic Curve Primality Proving) ALGORITHM

OSMANBEY UZUNKOLOCTOBER 2004

ATKIN’S ECPP (Elliptic Curve Primality Proving )ALGORITHM

A THESIS SUBMITTED TO
DEPARTMENT OF MATHEMATICSOFTECHNICAL UNIVERSITY OF KAISERSLAUTERN

BY

OSMANBEY UZUNKOLIN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE
DEGREE OF
MASTER OF SCIENCEIN
THE DEPARTMENT OF MATHEMATICS

October 2004

abstract
ATKIN’S ECPP ALGORITHM
Uzunkol, Osmanbey
M.Sc., Department of Mathematics
Supervisor: Prof. Dr. Gerhard Pfister
October 2004, cxxiii pages

In contrast to using a strong generalization of Fermat’s theorem, as in Jacobisum Test, Goldwasser and Kilian used some results coming from Group Theory
in order to prove the primality of a given integer N ∈ N. They developed analgorithm which uses the group of rational points of elliptic curves over finite
fields. Atkin and Morain extended the idea of Goldwasser and Kilian and usedthe elliptic curves with CM (complex multiplication) to obtain a more efficientalgorithm, namely Atkin’s ECPP (elliptic curve primality proving) Algorithm.
Aim of this thesis is to introduce some primality tests and explain the Atkin’s
ECPP Algorithm.

Keywords: Cryptography, Algorithms, Algorithmic Number Theory.

ii

öz

Hergün bir yere konmak ne güzel,
Bulanmadan donmadan akmak ne hoş,Dünle beraber gitti cancağızım!
Ne kadar söz varsa düne ait,Şimdi yeni şeyler söylemek lazım...

...............Mevlana Celaleddini’i Rumi...............

iii

I would like to thank first of all to my supervisor Prof. Dr . Gerhard Pfister forhis help before and during this work. Secondly, I would like to thank also Hans
Schönemann and Raşit Şimşek for their computer supports in computer algebra
system SINGULAR and programming language C++, respectively. At the end,
I want to thank to my family, especially my mother, and my darling ŞerminÇamdalı, without them this thesis would not have been realized.

iv

table of contents
abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

ii

dedicate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv
CHAPTER
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii
1.1

Primality Tests . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii

1.2

ECPP Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . .

ix

1.3

About Thesis... . . . . . . . . . . . . . . . . . . . . . . . . . . . .

x

2 Some results from Algebra & Number Theory . . . xii
2.1

Introductory arithmetics . . . . . . . . . . . . . . . . . . . . . . .

xii

2.2

Fermat’s theorem and Special prime numbers . . . . . . . . . . . xvi

2.3

Results from Algebraic Number Theory . . . . . . . . . . . . . . .

2.4

Quadratic Forms . . . . . . . . . . . . . . . . . . . . . . . . . . . xxiv

xx

3 Preliminaries from the arithmetic of Elliptic curves
xxviii
3.1

Some results from the theory of Elliptic Curves . . . . . . . . . . xxviii

3.2

Elliptic curves over C . . . . . . . . . . . . . . . . . . . . . . . . . xxxiv

3.3

Elliptic curves over finite fields Fq . . . . . . . . . . . . . . . . . . xxxvii

3.4

Fast Point Addition and Multiplication . . . . . . . . . . . . . . . xxxix

3.5

3.4.1

Point Addition . . . . . . . . . . . . . . . . . . . . . . . .

xl

3.4.2

Fast Point Multiplication . . . . . . . . . . . . . . . . . . . xlii

Point Counting and Other Problems . . . . . . . . . . . . . . . . xlixv

4 Primality Testing and Proving Algorithms . . . . . . .

li

4.1

Prime Number Generation . . . . . . . . . . . . . . . . . . . . . .

lii

4.2

Trial-division Method . . . . . . . . . . . . . . . . . . . . . . . . .

lii

4.3

Fermat’s Primality Test . . . . . . . . . . . . . . . . . . . . . . .

liii

4.4

Probabilistic Primality Testing Algorithms . . . . . . . . . . . . .

liv

4.4.1

Solovay-Strassen Probabilistic Primality Test . . . . . . . .

liv

4.4.2

Miller-Rabin Probabilistic Primality Test . . . . . . . . . .

lv

N − 1 Primality Testing Algorithms . . . . . . . . . . . . . . . . .

lvi

4.5

4.6

4.7

4.8

4.5.1

Test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . lvii

4.5.2

certificate . . . . . . . . . . . . . . . . . . . . . . . . . . .

lix

4.5.3

Special primes . . . . . . . . . . . . . . . . . . . . . . . . .

lix

N + 1 Primality Testing Algorithms . . . . . . . . . . . . . . . . .

lx

4.6.1

Test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

lxi

4.6.2

certificate . . . . . . . . . . . . . . . . . . . . . . . . . . .

lxi

4.6.3

Special primes . . . . . . . . . . . . . . . . . . . . . . . . .

lxi

ECPP Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . .

lxi

4.7.1

Test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . lxii

4.7.2

certificate . . . . . . . . . . . . . . . . . . . . . . . . . . . lxvi

Primality Testing in reality . . . . . . . . . . . . . . . . . . . . . . lxvi

5 ECPP (Elliptic Curve Primality Proving) ALGORITHMS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .lxviii
.
5.1

5.2

Goldwasser-Kilian ECPP Algorithm . . . . . . . . . . . . . . . . . lxix
5.1.1

Schoof’s Algorithms . . . . . . . . . . . . . . . . . . . . . lxix

5.1.2

ECPP Algorithm (Goldwasser-Kilian) . . . . . . . . . . . . lxxii

5.1.3

certificate . . . . . . . . . . . . . . . . . . . . . . . . . . . lxxiii

Atkin’s ECPP Algorithm . . . . . . . . . . . . . . . . . . . . . . . lxxiii
5.2.1

Generating Elliptic Curves with Complex Multilication . . lxxiii

5.2.2

ECPP ALGORITHM (Atkin) . . . . . . . . . . . . . . . . lxxviii

5.2.3

Problems and Approaches . . . . . . . . . . . . . . . . . . lxxx

5.2.4

certificate . . . . . . . . . . . . . . . . . . . . . . . . . . . lxxxvii

vi

5.3

Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . lxxxvii

6 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .lxxxix..
6.1

Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . lxxxix

6.2

Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

xc

7 Implementation, LiDIA classes and Conclusion . . . xcii
7.1

7.2

Implementation details . . . . . . . . . . . . . . . . . . . . . . . . xcii
7.1.1

SINGULAR source codes Examples . . . . . . . . . . . . . xcii

7.1.2

C + + source codes, used classes and Examples . . . . . .

ciConclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . cxviii

references . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . cxx

viichapter 1
Introduction
1.1

Primality Tests

Primality testing, distinguishing prime numbers from composite ones, goes backto very old research of number theory due to Eratosthenes who came up with thefirst primality testing to efficiently generate the set of prime numbers from 1 to
N in O(N log log N ) arithmetic steps by means of the so-called sieve of Eratosthenes method in 3rd century BC. Since 17th century, mathematicians have been
studying primality testing methods in order to distinguish prime numbers fromcomposites and factor integers. Fermat’s little theorem enable us to recognize
most of the composite integers. Owing to the improvements in the area of Data
security and cryptography, in particular public key cryptography, the importanceof finding big primes has been dramatically increased. Using the extended ideas
of Fermat’s theorem, Sollovay and Strassen, in 1977, and Miller and Rabin, in
1980, were developed probabilistic primality tests. Although, the answer prime inthese tests is not always true, even cannot be proven mathematically, these tests
especially Miller-Rabin test have been used in public key cryptography to build
cryptosystems based on factorization of integers, such as RSA and its variants,
and discrete logarithm problem (DLP), such as Diffie-Hellman and ElGamal. Furthermore, the answer composite is always true in both of these primality tests.
Hence, in some texts they are called compositeness tests.
The first general purpose primality testing algorithm was designed by Adleman, Pomerence and Rumely [10]. The running time of this algorithm was proved
to be O((log N )c.log log log N ) for some effective c > 0. Although, this algorithm
is fast polynomial, has expected polynomial complexity, the first appearance wasviiinot suited to use in practice. Afterwards this algorithm was made practical andsimplified by H. W. Lenstra and Cohen in [32], and then implemented by Cohenand A. K. Lenstra in [14].

1.2

ECPP Algorithms

In 1985, H. W. Lenstra introduced the usage of elliptic curves in factorizationof integers. After that Goldwasser and Kilian developed an algorithm with thehope of finding a primality test with the help of groups of rational points ofelliptic curves over finite fields. Their algorithm is called ECPP (elliptic curve
primality proving) algorithm, which uses the DOWN-RUN strategy of the elliptic curve analog of N − 1 primality testing method together with a theoreticalalgorithms due to Schoof. They showed that under reasonable hypothesis on the
distribution of primes in short intervals, the expected running time of ECPP isO(log 12 N ). After the previous success at producing proofs of compositeness, as
in Sollovay-Strassen and Miller-Rabin, this algorithm produces short proofs ofprimality. This proof is called hence certificate of primality.
The major difficulty in the ECPP algorithm of Goldwasser & Kilian is tofind the size of the group of rational points of elliptic curves by means of thetheoretical algorithms due to Schoof. Although, some progress has been made in
the direction of making Schoof’s algorithm practical by Atkin in [48] and Elkiesin [29], Atkin and Morain have found a better idea. They used elliptic curves
with complex multiplication, abbreviated by elliptic curves with CM, instead ofusing randomly chosen elliptic curves. Their algorithm, namely Atkin’s ECPP, isvery practical and used to prove the primality of the Titanic numbers, numbers
which have more than 1000-digits, by using weeks of workstation time. Moreover,as for the Goldwasser-Kilian algorithm, it is easy to verify the correctness of theresult for second programmer, i. e. it gives a certificate of primality for the prime
candidate N which enable to recheck the primality of N much faster.

ix

1.3

About Thesis...

The aim of this thesis is to explain and overview the important primality testing
methods and Atkin’s ECPP algorithm. It consists of the following chapters:• We will start with basic facts coming from algebra and number theory.
In particular, we will explain imaginary quadratic number number fields,
quadratic forms and Cornacchia’s algorithms, which are the basic algebraic
results used in our primality tests and ECPP algorithm.
• In chapter 3, elliptic curves and their arithmetic related with primality
proving will be intensively explained and the necessary background will becovered. In this chapter, we will also see how one can deal with problems
coming together with the computations of the groups of rational pointsof elliptic curves over different fields and in particular over finite fields Fq ,where q = pr , r ∈ N and p is a prime. Further, we will also shortly overview
the curves with CM and their relation between imaginary quadratic number
fields and forms.
• We will overview some primality testing methods in chapter 4. Furthermore,
we will introduce the so-called Poclingston’s theorem and N −1 (resp. N +1)
primality testing method, which is a primality testing algorithm based on
the full or partial factorization of N − 1 (resp. N + 1), where N is a prime
candidate. This method will enable us to introduce the general idea and
DOWN-RUN strategy of the ECPP algorithms that we will also give in a
general form.
• In chapter 5, we will explain our ECPP algorithms of Goldwasser-Kilian andAtkin, respectively. We will overview the approaches of dealing with point
counting problem of elliptic curves over finite fields, such as the theoreticalalgorithm of Schoof used in Goldwasser-Kilian ECPP algorithm and CMmethod in our Atkin’s ECPP algorithm. Moreover, we will see different
methods and approaches to improve and optimize the Atkin’s algorithm atthe end of the chapter.

x• The running time analysis of both Goldwasser-Kilian and Atkin will besummarized in chapter 6.
• At the end, we will give implementations of some primality testing methods
and some parts of Atkin’s ECPP algorithm together with the examples.
The computer package LiDiA was used to implement and give examples ofthese algorithms in the programming language C++. Some of the number
theoretical functions and primality tests were implemented in computer
algebra system SINGULAR, too.

xichapter 2
Some results from Algebra &Number Theory
In this chapter, we will briefly explain the necessary theory and backgroundcoming together with elementary number theory, quadratic forms and imaginary
quadratic number fields. All subjects have enormous literature. We begin withsome arithmetical results which are basics of our discussions later on. At thefirst, basic arithmetical tasks related to prime numbers will be introduced. We
will give the Fermat’s little theorem which will be a basic theoretical result in
our all primality testing and proving algorithms. Secondly we will review the
preliminaries of algebra and algebraic number theory which are related to ourN − 1 (resp. N + 1) and ECPP Algorithms. Especially the quadratic forms willbe the basic analogous number-theoretic result of our ECPP Algorithms.

2.1

Introductory arithmetics

We will review in this section some arithmetical properties coming from Algebra which are necessary to develop and define our theoretical results for prime
numbers.
Definition 2.1. Let R be a ring and a, b ∈ R. Then b is called divisible by a or
a divides b if there exists c ∈ R with b = a.c.
Remark 2.1. a | b (if a divides b), otherwise a - b (if a does not divide b).
Furthermore, we have; 0 | a ⇔ a = 0.

xii

Definition 2.2. a ∈ R is called an identity if a | 1, i. e. ∃c ∈ R such that 1 = a.c.
So by definition c is also a an identity and c = a−1 is then the multiplicative
inverse of a in R.
Definition 2.3. a, b ∈ R are called associate if a | b and b | a simultaneously.
Corollary 2.1. (R∗ , .) is an abelian group.
Proof : See reference [17].
Definition 2.4. Let a ∈ R, a 6= 0 and a is not an identity element. Then a iscalled irreducible if from the decomposition a = b.c, b, c ∈ R we get b ∈ R∗ orc ∈ R∗ . If a is not irreducible, then it is called composite.
Definition 2.5. Let p ∈ R, p 6= 0 and p is not an identity element. Then p iscalled prime element or just prime if from p | b.c with b, c ∈ R we get p | b or
p | c.
Remark 2.2. In general prime 6= irreducible
Question: When we have equality?
Proposition 2.1. If R is an integral domain, then each prime element a ∈ R is
irreducible.
Proof : See reference [17].
But again for a general integral domain the inverse of the above proposition
is false (irreducible ; prime). In fact, we need an analog algebraic structure
which have a division property like integers. Our structure must be in this sense
euclidean rings.
Proposition 2.2. Let R be a euclidean ring, then each irreducible element a ∈ R
is prime.
Proof : See reference [17].
As we see from the above two propositions we can conclude that in euclideanrings primes = irreducibles (as every euclidean ring is an integral domain).

xiii

Uniqueness of decomposition of prime elements
Lemma 2.1.1. Let R be a euclidean ring, a ∈ R, a 6= 0. If a ∈/ R∗ , then there
exists a prime element which divides a.
Proof : see reference [17].
Theorem 2.1. Let R be a euclidean ring, a ∈ R, a 6= 0.
1. Either a ∈ R∗ or a can be written as a product of prime elements, i.e.
∃s ∈ N and prime elements p1 , . . . , ps so that
a=

s
Y

pi .

i=0

2. Let a =Qt

j=0 qjbe an another factorisation of a. Then s = t and there

exists a permutation of the set {1, . . . , s} such that pi & qπ(i) are associate.
Actually above theorem tells us that each element of a euclidean ring can be
written in terms of prime elements (equivalently irreducible elements). We will
use this idea in our special case R = Z in the next section so as to conclude thatevery natural number has a unique prime number decomposition!
We will end this basic section with the definition of a greatest common divisor
and the general version of so-called euclidean algorithm.
Definition 2.6. Let R be an integral domain, a, b ∈ R, d be a common divisorof a & b. Then d is called a greatest common divisor, abbreviated by gcd, of a &b, if d0 | d for all common divisor d0 of a & b.
Lemma 2.1.2. Let R be a principal ideal domain, a, b ∈ R and I = (a, b) be an
ideal of R which is generated by a and b. If I = (d) with d ∈ R, then d is a gcd
of a and b.
Proof : see reference [17].

xivTheorem 2.2. Euclid Algorithm Let R be a euclidean ring with euclid function ψ, a, b ∈ R b 6= 0, I = (a, b).
Set r0 = a; r1 = b and ∀i ≥ 0 ri = qi .ri+1 + ri+2 such that ri+2 = 0 or
ψ(ri+2 ) < ψ(ri+1 ).
Then ∃ a smallest natural integer κ with rκ 6= 0 but rκ+1 = 0 and I = (rκ ).
Proof : See reference [17].
This theorem implies that for a given a, b ∈ R it is possible to find a gcd d ofa and b. Note that there exist x, y ∈ R such that d = ax + by. Also note that in
the general case gcd is not unique!
Remark 2.3. One can also give for this general case the so-called extended euclidean algorithm which simultaneously computes d, x and y. See reference [17]and [46].
At the we will give our first algorithm, namely extended GCD algorithm for
integers, in a pseudo-code.
ALGORITHM:extended GCD
Input: Given a, b ∈ Z with a ≥ b,
Output: d = gcd(a, b) and integers x, y satisfying ax + by = d,

1. If b = 0, then set d ← a, x ← 1, y ← 0, and return(d, x, y);
2. Set x2 ← 1, x1 ← 0, y2 ← 0, y1 ← 1;
3. While b > 0 do the following:(a) q ← ba/bc, r ← a − qb, x ← x2 − qx1 , y ← y2 − qy1 ,(b) a ← b, b ← r, x2 ← x1 , y2 ← y1 , and y1 ← y,

4. Set d ← a, x ← x2 , y ← y2 , and return(d, x, y).
At the end of this section, we are going to review the so-called Chinese Remainder Theorem, abbreviated by CRT for the general case.

xv

Theorem 2.3. Chinese Remainder Theorem Let R be a euclidean ring,t ∈ N and m1 , · · · , mt ∈ R such that mi and mj are coprime to each other for
i 6= j. Then we have
R/mR ∼=t
M

R/mi R.

i=1

Proof: see reference [17].
Corollary 2.2. Let R be a euclidean ring, t ∈ N and m1 , · · · , mt ∈ R suchthat mi and mj are coprime to each other for i 6= j. Furthermore, assume that
a1 , · · · , at ∈ R are given. Then ∃ x ∈ R with x ≡ ai mod(mi ) for 1 ≤ i ≤ t.

Q
Additionally, x mod m = ti=1 m1 · · · mt is uniquely determined.
Proof: immediate by CRT!

2.2

Fermat’s theorem and Special prime numbers

In this section we are going to revisit some properties of prime numbers. Afterwards, Fermat’s little theorem and related results will be discussed. At the end
we will see some special prime numbers. Their primality can be tested more easier
as we will see in Chapter 4.
Hier we have R = Z. Obviously Z is euclidean. Further its prime elements,
which are > 0, are called w.l.o.g. prime numbers (Prime elements of Z are p and−p, where p is a prime number).
Theorem 2.4. Euclid There are infinitely many prime numbers.
Proof : Let M be the set of all prime numbers. M =6 ∅ as 2 ∈ M. Let now
Q
p1 , . . . , pk be the distinct prime numbers and k ≥ 1. Let Q = 1 + k1=0 pi bylemma 2.1.1 ∃P which divides Q.
Q
Let P = pi ⇒ P | Q − ki=0 pi ⇒ P | 1 ⇒ contradiction to the assumption thatpi is prime ∀i, 1 ≤ i ≤ k.

xvi

By theorem 2.1 we can conclude that each natural number n has a uniqueprime factorisation. Then ∃s ∈ N and prime numbers p1 , . . . , ps such that
n=

s
Y

pi .

i=0

Notation: If we write down the same primes together we getn=tYpei i ,

i=0

pi 6= pj if i 6= j, ei ∈ N. This is called canonical prime factor decomposition of n.
Theorem 2.5. Prime number Theorem Let π(x) be number of primes smaller
than ’x’ where x ∈ R. Thenπ(x). log x
= 1.
x→∞
x
lim

Remark 2.4.

1. Some cryptosystems like RSA needs big prime numbers, suchas prime numbers of exactly 128 bits in its binary representations. How
many does such primes exist?
By using Prime number theorem, we have approximately π(2128 )−π(2127 ) =
2128
2127
− 127.
(≈ 1, 906.1036 primes).
128. log 2
log 2

2. This theorem, as we see above, will be very useful in running time analysis
of our algorithm in chapter 6.
Now we will give the definition of Legendre- and Jacobi-Symbols;
Definition 2.7. Legendre-Symbol Let p > 2 be a prime number and a ∈ Z
then




 −1 if

a
( )=
0 if

p

 +1 if

a is a quadratic non − residue
gcd(a, n) 6= 1
quadratic a is a residue

Of course we can generalize this definition for any odd integer N instead of aprime number p.

xvii

Definition 2.8. Jacobi-Symbol Let N =Qkei
i=0 pi be an odd integer with all

pi ’s prime and a ∈ Z. Then ( Na ) is defined as follows:
(

a
a
a
a
) = ( )e1 ( )e2 . . . ( )ek .
N
p1
p2
pk

ALGORITHM:Jacobi-Symbol
Input: Given a, N ∈ Z,
Output: Legendre resp. Jacobi-Symbol ( Na ) ,1. (Test N = 0) if N = 0 output 0 if | a |6= 1,if | a |= 1 then terminate thealgorithm;
2. (Remove 2’s from N ) if gcd(a, N, 2) = 1, output 0 and terminate thealgorithm.Otherwise,(a) v ← 0 and while v is even set v ← v + 1 and N ← N/2(b) if v is even k ← 1, otherwise set k ← (−1)(a2 −1)8(c) if N < 0 set N ← −N and if in addition a < 0 set k ← −k;
3. (finished?) (Here clearly N is odd and positive)(a) if a = 0 then output 0 if b > 1, k if b = 1(b) otherwise set v ← 0 and while a is even do v ← v + 1 and a ← a/2(c) if v is odd set k ← (−1)(b2 −1)8k;

4. (Apply reciprocity law) k ← (−1)(a−1)(b−1)
4k. Then r ←| a | and a ←b mod(r), b ← r and GOTO 3;
As we already said that our basic number theoretical result is due to Fermat.
Fermat’s little theorem and the generalization of its inverse (actually inverse is ofcourse not true!) will be our basic results in our primality testing and afterwards
proving algorithms. We will review the results coming with Fermat’s theorem.
Theorem 2.6. Fermat’s Little Therem Let p be a prime number and a ∈ Nwith gcd(a, p) = 1 then ap−1 ≡ 1 mod(p).

xviii

Proof See reference for example [17].
Definition 2.9. A composite number N is said to be pseudoprime to the base a,denoted by psp(a), a ∈ Z , 1 ≤ a ≤ N − 1, if aN −1 ≡ 1 mod(N ).
Definition 2.10. A composite number N is said to be euler pseudoprime to theN −1base a, denoted by epsp(a), a ∈ Z , 1 ≤ a ≤ N − 1, if a 2 ≡ na mod(N ).
Proposition 2.3. For all odd number a ∈ N there are infinitely many psp(a)’sand epsp(a)’s.
Proof See reference [17].
Proposition 2.4. let p be an odd prime , p − 1 = 2l .m, where m is odd, a ∈ Z
with gcd(a, p) = 1. Then either am ≡ 1 mod(p) or there exists some j withj

0 ≤ j ≤ l such that a2 .m ≡ −1 mod(p)Proof See reference [17].
Definition 2.11. If N is composite and the above conditions are satisfied fora ∈ Z then N is called a strong pseudoprime to the base a, abbreviated byspsp(a).
Special Prime Numbers
Lemma 2.2.1. Let a, b ∈ N and a | n. Then 2a − 1 | 2n − 1.
Proof : See reference [17].
Corollary 2.3. If Mn = 2n − 1 is a prime, then n is a prime. Such primes arecalled Mersenne Primes
Proof : Trivial by above lemma.

Lemma 2.2.2. If Mp is prime then n = 2p−1 .Mp is a perfect number. Conversely
each even perfect number n has the form n = 2p−1 .Mp where Mp is a Mersenne
prime

xix

Proof : Due to Euclid see reference [17].
nLemma 2.2.3. If N = 2m + 1 is prime then m = 2n . The numbers Fn = 22 arecalled Fermat numbers.
We will discuss in Chapter 4, how for these special prime numbers we canapply our tests.

2.3

Results from Algebraic Number Theory

In this section we will give the necessary background from the theory of algebraic
number theory. We are going to explain quadratic forms and their relation withimaginary quadratic number fields, which are basics of the theory of Complex
Multiplication, abbreviated by CM-theory, that we will see in next chapter. These
results together with CM-theory will enable us to give N − 1 analog of a prime
number test actually our algorithm due to Atkin. Most of the results needed to
introduce our algorithm and related literature and references will also be given.
Note that up to now we have just introduced the number theoretical results
which are basics of all Primality testing algorithms. We also introduce in Chapter
4 the so-called Jacobi Sum Test which is also a true primality testing algorithm.
However, we will not give the prerequisite theory of that algorithm as it is outside
the scope of this thesis. The necessary background can be covered from the bookof Cohen [1].
Arithmetic in Quadratic Number Fields√
Let D ∈ Z, let D ∈ C be a root of the polynomial X 2 − D. Then√√
Q( D) := {a + b. D | a, b ∈ Q} ⊆ C.
√
Then Q( D) is a field, namely quadratic number field. If D < 0 (D > 0), thenit is called complex (real resp.).
√
Remark 2.5. Q( D) is a Q-vector space of dimension 2, a basis for example√
P1 = (1, 0) and P2 = (0, D).

xx

WLOG we can assume that D is a squarefree integer. i. e. D 6≡ 0 mod(4).
Consider just D ≡ 1, 2, 3 mod(4).
√√Definition 2.12. The map σ : Q( D) → Q( D);√√σ(a + b. D) = a − b. D is called conjugate.
Here are some properties of the conjugate map σ :√1. σ(α ± β) = σ(α) ± σ(β), ∀α, β ∈ Q( D),√
2. σ(α.β) = σ(α).σ(β), ∀α, β ∈ Q( D),√
3. σ( αβ ) = σ(α), ∀α, β ∈ Q( D) provided that β 6= 0,σ(β)
4. σ(β) = 0 if and only if β = 0.
√
Theorem 2.7. Let D be a square free integer. Then Q( D) is a field with√√Q ⊆ Q( D) ⊆ C. Each α ∈ Q( D) has a unique representation of the form√
α = a + b. D, a, b ∈ Q.
√
The map σ is an automorphism of Q( D) which fixes Q pointwise.
Proof : See reference. [17].

Definition 2.13. α0 = σ(α) Norm-function: N (α) = α.α0 and trace-function:
T (α) = α + α0√
Hence for a given α = a + b. D we have N (α) = a2 − b2 .D and T (α) = 2a.
Theorem 2.8.

√
1. The function S : Q( D) → Q is an epimorphism of addi-

tive groups.
√
2. if α ∈ Q( D), then we have N (α) = 0 if and only if α = 0 (as D 6= 2) the√
function S ∗ : Q( D)∗ → Q∗ is a homomorphism of multiplicative groups.

xxi

√
√
Now let α = a + b D ∈ Q( D) then we get a relation√√22
α2 = a2 + 2ab D + b2 D = |{z}2a (a + b D) − a| −{zb D}
S(α)

N (α)

⇒ α2 − S(α).α + N (α) = 0.
√Corollary 2.4. Every α ∈ Q( D) is a root of a polynomial in Q[x] of degree≤ 2. A monic polynomial µα ∈ Q[x] with minimal degree such that µα (α) = 0 iscalled minimal polynomial of α. Further, µα is uniquely determined.
√
Definition 2.14. Let α ∈ Q( D). Then α is called an algebraic integer ifµα ∈ Z[x].
Now we have actually three cases for minimal polynomials of having algebraic
integers:• Let α ∈ Z ⇒ µα = x − α ∈ Z[x],• Let α ∈ Q − Z ⇒ µα = x − α ∈/ Z[x],√• Let α ∈ Q( D) − Z; α is an algebraic integer ⇔ both T (α) ∈ Z and
N (α) ∈ Z.
√
Lemma 2.3.1. Let α ∈ Q( D). Then α is algebraic integer if and only if
α has the form(α=1(a + b2√D), a, b ∈ Z if√
a + b D, a, b ∈ Z ifa ≡ b mod(2) f or D ≡ 1 mod(4)D ≡ 2, 3 mod(4)Proof : See reference [17].

√Let OD be the set of all algebraic integers of Q( D). Then we have thefollowing corollary and theorem;
Corollary 2.5. OD is a ring. Moreover, it is an integral domain.
Proof : trivial by above lemma.

xxii

Theorem 2.9. OD is a free Z-Module of Rank 2, OD has Z-Basis (1, wD ) with
√

(
wD =

1
(1 +
2

√

D

if

D) if

D ≡ 2, 3 mod(4)D ≡ 1 mod(4)Moreover, OD ∼= Z ⊕ wD .Z.
Definition 2.15. Imaginary quadratic discriminant of an imaginary quadratic√
number field K = Q( −d), d > 0, square free is equal to
(
D=

d if

D ≡ 3 mod(4)4d if

D 6≡ 3 mod(4).
Corollary 2.6. The set of all algebraic numbers in K can be given by the following isomorphy;
(
OK =

√
Z + Z −d if

d 6≡ 3mod(4)ifd ≡ 3mod(4)√Z + −1+2 −d Z.
Definition 2.16. Order of an imaginary quadratic number field An order
O in K is a subring of K which is as a Z-Module finitely generated and of maximal
rank n = deg(K).
Definition 2.17. An ideal α of O is a sub-O-module, i. e. a sub-Z-module of O
such that every r ∈ O and i ∈ α we have r.i ∈ α.
Definition 2.18. An ideal α is said to be principal ideal of O, if there exists
x ∈ K such that α = xO. Furthermore O is a principal ideal domain (PID) if O
is an integral domain (for orders it is always the case) and if every ideal α of O
is a principal ideal.
Assume OK is principal order of an imaginary quadratic number field K. ThenO ⊂ OK .

xxiii

Definition 2.19. Two ideals α, β are said to be equivalent, if there exist a, b
∈ K∗ with a.α = b.β.
Equivalent classes form an ideal class U. Every ideal class of OD has an idealof the form;
aZ +

−b +

√

−D

2

Z f or a ∈ N, b ∈ Zwith additionally c = (b2 + D)/4a ∈ Z and gcd(a, b, c) = 1.
Definition 2.20. A fractional ideal i of O is a non-zero submodule of K suchthat there there exists a non-zero integer d with di an ideal of O.
Definition 2.21. Let i be a fractional ideal of O. We say that i is invertible if
there exists a fractional ideal j of O such that O = ij. Such an ideal j is thencalled inverse of the ideal i.
Lemma 2.3.2. Let i be a fractional ideal, and set
i0 = {x ∈ K, xi ⊂ O},
then i is invertible if and only if ii0 = O. Moreover, if this equality is true, theni0 is unique inverse of i and denoted by i−1 .
Proof : immediate!

2.4

Quadratic Forms

In this section we will introduce the quadratic forms and their relations withimaginary quadratic number fields and discriminants. In fact, the idea is that
quadratic forms & invertible fractional ideals of imaginary quadratic order O are
the same structure in an imaginary quadratic number field K. This equivalence
will enable us to find an another one in the next chapter, the equivalence between lattices Λ ⊂ C and hence the equivalence between elliptic curves over C,
which will be then particularly used in CM-theory and at the end in our ECPP
algorithm.

xxiv

Definition 2.22. A binary quadratic form over Z is a map:
f : Z2 → Z f (x, y) = ax2 + bxy + cz 2 , a, b, c ∈ Z with discriminant D = 4ac − b2 .
This form is called primitive if gcd(a, b, c) = 1. Hence, it can be identified as a
triple, i. e. f = (a, b, c).
Remark 2.6. Quadratic orders can be also represented in terms of matrices
f (x, y) = (x, y) a b/2  x
|

b/2 c
y
{z }
Mf

Definition 2.23. Two binary quadratic forms f & g are said to be equivalent,abbreviated by (f ∼ g), if ∃A ∈ SL(2, Z) with Mg = A−1 .Mf .A.
This is obviously an equivalence relation.
Definition 2.24. Binary quadratic forms f in equivalence classes [f ] form agroup called form class group, and denoted by Cl(D).
Let’s analyse this equivalence classes a little bit more;
Corollary 2.7. Each equivalence class contains exactly one form (a, b, c) witha, b& c are relatively prime and satisfy the following;| b |≤ a ≤ c & (| b |= a or a = c ⇒ b > 0). Such a form is called reduced.
Proof : See reference [11].
Theorem 2.10. Let OK be a principal order of an imaginary quadratic number
field K, and D be an imaginary quadratic discriminant of OK . Then define a
map;
2

2

φ : f (x, y) = ax + bxy + c 7−→ aZ +

−b +

√
2

−D

Z

with D = b2 − 4ac.
Then φ is a bijection between form class group Cl(D) and the ideal class group
Cl(O).
Proof : See reference [11].

xxvThis theorem says us that ;| Cl(D) |=| Cl(OD ) | which implies that h(OD ) = h(D)Review: h(OD ) (and h(D)) is by definition the cardinality of Cl(OD ) (cardinality of Cl(D), respectively).
Definition 2.25. Let D be an imaginary quadratic discriminant, n ∈ Z andf = (a, b, c) be a quadratic form with discriminant D. If ∃(x, w) ∈ Z2 such thatn = ax2 + bxw + w2 = f (x, w)
Then n can be represented by means of the function f . Such an n is called Normof an element of OD if there exists π ∈ OD with n = ππ̄.
Question: When have we such a form and how can we compute it?
Lemma 2.4.1. Let D be an imaginary quadratic discriminant n ∈ Z. Thereexists π ∈ OD with n = ππ̄ if and only if 4n = t2 + Dy 2 has a solution (t, y) ∈ Z2 .
We will end this section to explain the method to compute these diaphontine
equations. Note that it is not always the case that such a solution exists. In
order to find such a pair (t, y), we can use so-called Cornaicchia’s Algorithm
which also give us a chance to know whether or not such a solution exists. Thisalgorithm computes essentially for a given rational the continued fraction of thesquare root. This idea was also used so as to factor the integers. Note that finding
such a pair is equivalent to solving p = x̃2 + dỹ 2 for a prime number p. Notethat this algorithm will be also used in CM-Theory of elliptic curves for a given
discriminant D.
ALGORITHM: Cornaicchia’s Algorithm
Input: Given a square free integer D and a prime number p,
Output: A solution to p = x̃2 + dỹ 2 , if exists,
1. Let p/2 < x0 < p be solution to x2 ≡ −D mod(p);2. p ← q0 x0 + x1 , k ← 0;xxvi

3. Until x2k < p ≤ xk−1 do;(a) xk ← qk+1 xk + 1 + xk+2 k ← k + 1,p(b) x̃ ← xk , ỹ ← (p − x2k )/d,

4. if ỹ ∈ Z return (x̃, ỹ), else return ’No Solution’;One can also modify the algorithm to get a more efficient method. Here is
the modified version of Cornacchia due to Cohen. In this method we also do
not need to use (x̃, ỹ) transformation;
ALGORITHM: Modified Cornaicchia’s Algorithm
Input: Given a square free integer D and a prime number p such that D ≡ 0 or
1 mod(4) and | D |< 4p,
Output: A solution to 4p = x2 + dy 2 , if exists,√
1. (Case p = 2) If D + 8 is a square of a natural number return ( D + 8, 1),
otherwise return ’No Solution’;2. (Test if it is residue) using Jacobi-Algorithm compute k ←

D
p



. If

k = −1 return ’No Solution’;3. (Compute square root) Compute an integer x0 such that x20 ≡ D mod(p)and 0 ≤ x0 < p;(a) Set x0 ← p − x0 if x0 6= D mod(2),√(b) Set a ← 2p, b ← x0 , and l ← b2 pc

4. (Euclidean Algorithm) if b > l, set r ← a mod b, a ← b, b ← r and
GOTO step 4;
5. (Test Solution) If | D | does not divide 4p − b2 or if C = (4p − b2 )/ | D |is not the square of an integer return ’No Solution’. Otherwise return√(x, y) = (b, c).

xxviichapter 3
Preliminaries from thearithmetic of Elliptic curves
In this chapter, we will introduce some important results coming together withthe arithmetic of elliptic curves over different fields. Elliptic curves have an
extensive literature as they are used in many branches of both theoretical andapplied mathematics and are closely related with the theory of elliptic functions,from which they derive their name. Elliptic curves have been used and studied
in the recent in the proof of Fermat’s last Theorem. They have been also used infactorization of integers, cryptography, and as in our case primality proving for
more than two decades. Elliptic curves have an extensive usage in cryptography,
in particular public key Cryptography, since it is possible to reach a reasonablesecurity when we compare with other cryptosystems like RSA. Furthermore thesame level of security can be gained with a reasonable smaller key sizes, and henceof smaller memory and processor requirements. Additionally, they give a chance
to construct cryptosystems based on Discrete Logarithm Problem, abbreviated by
DLP. In primality proving, an analog method like N − 1 tests will be developedby means of complex multiplication (CM-) method of of elliptic curves.

3.1

Some results from the theory of Elliptic Curves

Definition 3.1. Let F ∈ R[x, y] be a polynomial of degree d (F 6= 0). Then
C := {(x, y) ∈ R2 | F (x, y) = 0}
is called a curve of degree d.

xxviiiLet K be a field and K̄ be an algebraic closure of K, let further (x0 , x1 , . . . , xn ) ∈K̄n+1 −{0}. Define (x0 : x1 : . . . : xn ) as a unique line between 0 and (x0 , x1 , . . . , xn ).
Definition 3.2. The n-dimensional projective space over K̄ is the set;
Pn = {(x0 : x1 : . . . : xn ) | (x0 , x1 , . . . , xn ) ∈ K̄n+1 − {0}}.
Notation: n-dimensional projective space over K̄ is also denoted by PnK̄ .
Definition 3.3.

1. A point (x0 : x1 : . . . : xn ) ∈ Pn is said to be a k-rational

point, if there exists λ ∈ K∗ so thatλ(x0 : x1 : . . . : xn ) ∈ K̄n+1 .
The set of all k-rational points of Pn is abbreviated by Pn (K).
2. (x0 : x1 : . . . : xn ) are called homogene coordinates of Pn .
Definition 3.4. A subset C ∈ P2 is called an algebraic curve, if ∃ a non-constanthomogene polynomial F ∈ K̄[x, y, z] such that C = V (F ).
Remark 3.1. Define Lz := V (z) ⊂ P2 , so that
Lz = {(x : y : z) ∈ P2 : z = 0} ∼= P1 .
Then there is an isomorhism(x:y:z)→(x/z,y/z)(s:t:1)←(s,t)
Then Uz is called affine part of P2 and Lz ∼= P1 is called line at infinity.

ϕz : Uz := P2 − Lz → K̄2 such that

Definition 3.5. Let C ∈ P2 be an algebraic curve. The affine part of C is thesubsetC 0 := C ∩ Uz .
Definition 3.6. An algebraic curve of degree d is said to be smooth, if there
exists a polynomial F ∈ K[x, y, z] of degree d such that(P ), ∂F(P ), ∂F(P )) 6= (0, 0, 0) ∀P ∈ C.
C = V (F ) and ( ∂F
∂x
∂y
∂z

xxix

Notation: Let ip (C, L) := denote the number of points of C

T

L, where L is

another line (resp. curve).
Theorem 3.1. Bezout’s theorem Let C1 , C2 be two smooth algebraic curvesin P2 . Then
X
P ∈C1

T

ip (C1 , C2 ) = deg(C1 ).deg(C2 ).
C2Proof: see reference [18].
Definition 3.7. Let C = V (F ) be a smooth algebraic curve of degree d, deg(F ) =d. Then Hesse-curve of C is the set
HC := V (det(∂2F)0≤i,j≤2 ) ⊂ P2
∂xi ∂xj.
2

F) is constant, and hence not a• For d ≤ 2, we have det( ∂x∂i ∂xjRemark 3.2.

curve in the concept of the definition 3.4.
2

F
• if det( ∂x∂i ∂x) 6= 0, then HC is also a smooth algebraic curve of degreej3d(d − 2) if d ≥ 3.
Definition 3.8. A point P ∈ C is called an inflection point, if there exists atangent L of C at the point P such that ip(C, L) ≥ 3. Then L is called inflection
tangent of C at P .
Theorem 3.2. (Let char(K) 6= 2) P ∈ C is an inflection point if and only if
P ∈ C ∩ HC .
Proof : See reference [18].
Remark 3.3. By Bezout’s theorem, there are at most 3d(d − 2) and at least 1
inflection points over an algebraic curve C.
Definition 3.9. Let C be a smooth algebraic curve of degree 3 and O ∈ C be
an inflection point. Define+:C × C −→ C
(P, Q) 7→ P + Q
xxx

as follows;
Let P¯Q be the line connecting P &Q (tangent if P = Q), Then by Bezouts we¯ be the line connecting
have P¯Q ∩ C = {P, Q, R} (with multiplicity). Let OR¯ ∩ C = {O, R, C}.
O&R then OR
Define P + Q := S.
Properties of the function ’+’:
1. ∀P ∈ C we have P + O = P (as O is an inflection point)
2. ∀P, Q ∈ C we have P + Q = Q + P .
3. ∀P ∈ C consider P¯O ∩ C = {P, O, Q}.Set: −P := Q¯ ) ∩ C = {P.O, −P } and OO¯ ∩ C = {O, O, O} as O is ansince: P (−P
inflection point, we have P + (−P ) = O.
4. ∀P, Q, R ∈ C: we have (P + Q) + R = P + (Q + R)
Proof : See reference [16]. Hence we can conclude that (C, +) is an abeliangroup.
Definition 3.10. An Elliptic Curve is the pair (E, +) where E is a smooth
algebraic curve of degree 3 and + is a group structure like above.
Remark 3.4. The choice of O as an inflection point is not necessary. However
if we choose O as an inflection point we have the following nice property:
P + Q + R = O ⇔ P, Q and R are collinear.
Remark 3.5. Let m ∈ Z. Then we define;

m.P =



P +P +
{z· · · + P} if |m−times

m>0

0 if

m=0






−(| m |).P

if

m<0

Theorem 3.3. Weierstrass Normal Form Let E be an elliptic curve and O
be an inflection point, let also E = V (F ) with deg(F ) = 3. Then there exists axxxi

projective transformation ϕA
ϕA : P2 → P2
so that Ẽ = V (F̃ ) withF̃ (X, Y, Z) = F (ϕA (X, Y, Z)) = Y 2 Z+a1 XY Z+a3 Y Z 2 −x3 −a2 X 2 Z−a4 XZ 2 −a6 Z 3Moreover, ϕ−1
A (O) = (0 : 1 : 0) is the unique point at infinity of Ẽ.
Proof : See reference [16].
Remark 3.6. With a coordinate transformation, elliptic curve E 0 is an affine
curve, i. e.
E 0 = E ∪ Uz = {(x, y) ∈ K̄2 : y 2 + a1 XY + a3 Y = x3 + a2 X 2 + a6 }plus a point at infinity O = (0 : 1 : 0).
Remark 3.7. For char(K) 6= 2, 3 there is an easier normal form with respect toa coordinate exchange. Then E has a form for E = V (F )F (X, Y, Z) = Y 2 − X 3 − aXZ 2 − bZ 3 and ∃a, b ∈ K̄that means;
E = {(X, Y ) ∈ K̄2 : Y 2 = X 3 + aX + b} ∪ {(0 : 1 : 0)}
Proof :See [6].
Lemma 3.1.1. Let E be an elliptic curve, then E is smooth if and only if 4a3 +27b2 6= 0.
Proof : trivial...
Theorem 3.4. Let char(K̄) 6= 2, 3. Further let E = V (F ) be an elliptic curvewith F (X, Y, Z) = Y 2 Z − X 3 − aXZ 2 − bZ 3 with a, b ∈ K̄ (particularly: 4a3 +xxxii

27b2 6= 0). Moreover, assume that P, Q ∈ E, P, Q 6= 0 and P 6= −Q and w.l.o.g.
we have P = (x1 , y1 , 1) & Q = (x2 , y2 , 1). Then we have;
P + Q = (λ2 − x1 − x2 : −λ(λ2 − x1 − x2 ) − µ : 1)−y1
2 x1
with λ := xy22 −x
and µ := y1 xx22 −y
if P 6= Q. If we have P = Q. Then ;
−x1
1

λ :=

3x21 +a−x31 +ax1 +2b
and
µ
:=
.
2y1
2y1

Proof : See [16].
Remark 3.8. If we have y1 = 0 ⇒ P = −P as we have −(x : y : 1) = (x : −y : 1).
Remark 3.9. Of course for the general Weierstrass normal form, i. e. if we havechar(K̄) = 2, 3, the generalized version of this addition process can be applied.
See [7].
Definition 3.11. An endomorphism φ of an elliptic curve E is a map
φ : E → E with φ(∞) = ∞. The set of all endomorphisms of an elliptic curve
forms a ring and is abbreviated by End(E).
For the structure of the endomorphism ring End(E) we have three choice,namely;1. End(E) = Z (not possible for curves over finite fields),
2. End(E) is an order of an imaginary quadratic number field,
3. End(E) is the maximal order of a quarternion algebra.
Remark 3.10. We will discuss the second case in detail in CM-theory later!
Definition 3.12. If we have Z ( End(E), then we say that E has complex
multiplication, denoted by E with CM.
Definition 3.13. The j-invariant of an elliptic curve E with ∆ 6= 0 is defined as3

a constant j(E) = 1728. (4a)where ∆ = 4a3 + 27b2 .
∆xxxiiiLemma 3.1.2. Let E1 and E2 be two elliptic curves over an algebraically closed
field K. Then E1 and E2 are isomorphic if and only if j(E1 ) = j(E2 ).
Proof: see [6].
Remark 3.11.

1. If we have j = 0 (resp. j = 1728), we have a = 0 and b = 1(resp. a = 1 and b = 0).
2. One can also show that for every j ∈ K, there exists an elliptic curve Ewith j(E) = j.

3.2

Elliptic curves over C

Definition 3.14. Given a lattice Λ in C with Λ = {nw1 + mw2 | n, m ∈ Z} withw1
w1 , w2 ∈ C∗ , w
∈
/ R.
2

1. A meromorphic function f is said to be elliptic if f (z + w) = f (z), ∀w ∈ Λ.
2. Weierstrass ℘-function associated to Λ is given byX℘(z; w) = z −2 +(z − w)−2 − w−2w∈Λ\{0}.
Then we have(℘(z; Λ) : z 7→℘(z; w) = z −2 +−2
− w−2 )w∈Λ\{0} ((z − w)

P

if

z∈
/Λ

∞ if

z∈Λ

.
Theorem 3.5. Weierstrass ℘-function is meromorphic, and it is elliptic (doubleperiodic) and satisfies the following differential equation;0℘ (z)2 = 4℘(z)3 − g2 (Λ)℘(z) − g3 (Λ)
with the constants g2 (Λ) = 60

1w∈Λ\{0} w4

P

xxxiv

and g3 (Λ) = 1401w∈Λ\{0} w6 .

PProof See reference [6].
Definition 3.15. Two lattices Λ1 and Λ2 are said to be homothetic, if there exists
λ ∈ C such that Λ1 = λΛ2 .
Definition 3.16. The j-invariant of a lattice Λis a complex numberj(Λ) = 1728.

g2 (Λ)3g2 (Λ)3=1728.
g2 (Λ)3 − 27g3 (Λ)2∆(Λ).
Theorem 3.6. Two lattices Λ1 and Λ2 are homothetic if and only if they havethe same j-invariant.
Proof: See reference [6].
Theorem 3.7. Let E = (a, b) be an elliptic curve over C. Then there exists
a uniquely defined lattice Λ ⊂ C so that a = −g2 (Λ)/4 and b = −g3 (Λ)/4
respectively.
Proof: See [6].
Proposition 3.1. Let O be an order in an imaginary quadratic number field K,
i be an invertible fractional ideal. Then i can be considered as a lattice over C.
Proof: See [6].
Theorem 3.8. Let Λ be a lattice, and ℘(z; Λ) the Weierstrass ℘-function. Furthermore, assume we have α ∈ C\Z. Then the followings are equivalent;
1. ℘(αz) is a rational function.
2. αλ ⊂ Λ.
3. There exists an order O in an imaginary quadratic number field and Λ ishomothetic to an invertible fractional ideal of that order O.
Proof: See [6] and [5].

xxxvTheorem 3.9. Let E be an elliptic curve over C and Λ be the corresponding
lattice. Then;
End(E) ∼= {α ∈ C | αΛ ⊂ Λ}.
By the above two theorems we have;End(E) of an elliptic curve E is an order O of an imaginary quadratic number
field if and only if the lattice Λ is homothetic to an invertible fractional ideal i ofO.
⇒ ∃ bijective map between set of invertible fractional ideals of imaginary
quadratic orders and set of isomorphy classes of an elliptic curve.
⇒ particularly we have j(i) = j(E), where j(i) and j(E) are j-invariants ofimaginary quadratic order O and elliptic curve E, respectively.
Theorem 3.10. Let O be an order in an imaginary quadratic number field K, ibe an invertible fractional ideal of the order O. Then j(i) is an algebraic integerof degree maximal h(O).
Proof: See [5].
Review: By previous chapter we have h(O) as the cardinality of the idealclass group Cl(O).
Let now K be an imaginary quadratic number field with maximal imaginary
quadratic order OK . Then one can represent the ideal class group Cl(OK ) of OK
with the represantatives;
i1 , · · · , ihD
where represantatives are lattices over C. Hence j(i1 ), · · · , j(ihD ) will determine
the j-invariants.
Let L be the smallest Galois extension of K, in which each j(is ), 0 ≤ s ≤ hD is
contained.
⇒ we have then an isomorphism C/is → Eis (C).

xxxvi

Let now E be an elliptic curve over C with End(E) ∼= OD and i1 , · · · , iD areelements of the ideal class group Cl(OD ). Let further ε denote the elliptic curve
over L and be given as follows;
j0 = j(ik )for some k ∈ {1, · · · , hD } with κ = j0 /(1728 − j0 ) and ε = (3κ, 2κ).
⇒ Lattices of E and ε are homothetic!
Theorem 3.11. Let K be an imaginary quadratic number field, OK be the ringof algebraic integers in K. Then there exist exactly hD isomorphy classes elliptic
curves with complex multiplication (CM) with OK where D is the imaginary
quadratic discriminant of OK . Moreover, they can be defined over Hilbert Class
Field HK . Class polynomial of a Hilbert Class Field is
HD (X) =hD
Y(X − j(is ))s=1.
Proof and details: see reference [6], [5] and their references.

3.3

Elliptic curves over finite fields Fq

Definition 3.17. Let E be an elliptic curve over a finite field Fq . The q th -powerof Frobenius map is defined by(ϕ:E(Fq ) → E(Fq )(x,y)7→(xq ,y q )O7→OIt is also easy to see that ϕ maps points on E to points on E, i. e. it respects
the group law. In fact ϕ is a group endomorphism of E over Fq .
Corollary 3.1.

1. Let E be an elliptic curve over Fq . then we have
| E(Fq ) |= q + 1 − txxxviiwhere t is the trace of Frobenius at q.
2. The Frobenius endomorphism ϕ and the trace of Frobenius satisfy the following functional equation
ϕ2 − [t]ϕ + [q] = [0]that is for a given point P = (x, y) on the curve (given in affine coordinates)
we have the following functional equality22(xq , y q ) − [t](xq , y q ) + [q](x, y) = O.
Note: addition and substaction are curve operations!
Proof : see reference [6].
Theorem 3.12. Hasse Let p be a prime number and q = pn , n ∈ N. Let also
E be an elliptic curve over Fq . Then√|| E(Fq ) | −(q + 1) |≤ 2 q.
Proof : See [6].
Definition 3.18. Let E be an elliptic curve over Fp , where p is a prime number.
Let also | E(Fp ) |= p + 1. Then E is called supersingular.
Lemma 3.3.1. If E is a supersingular elliptic curve over Fp . Then End(E) isthe maximal order of a quarternion algebra.
As we already discussed we have just 2 choices for the endomorphism ringof an elliptic curve over finite fields. (As it is the case for finite fields that
End(E)  Z)). The second case is the case of above lemma and the importantcase is explained by means of the following theorem;

xxxviii

Theorem 3.13. Let E be an elliptic curve over Fp , where p is a prime number.
The endomorphism ring of E is an imaginary quadratic order if and only if| E(Fp ) |6= p + 1.
Proof : see [6].
Remark 3.12. Let Υ ∈ OD be a prime ideal with O/Υ ∼= Fp . Furhermore,
ε = (α, β) is a non-supersingular elliptic curve over L and let E = (α mod Υ, β mod Υ)
be the reduced curve modulo Υ.
A curve ε has a ’good’ reduction modulo Υ if E is again a non-supersingularelliptic curve. It meansj(ε) mod(Υ) = j(E).
Theorem 3.14. If j ∈ Fp , j 6= 0, 1728, then there exist maximal two isomorphy
classes of elliptic curves over Fp . If j = 0 (resp. j = 1728), then there exist
maximal 6 (resp. 4) isomorphy classes.
Proof : see also for details [6].
Theorem 3.15. Deuring Let OK be a maximal imaginary quadratic order.
Moreover, let ε be an elliptic curve over HD with End(ε) ∼= OK and let further p
be a prime ideal of degree 1 (i. e. p = p) and (P ) = p.p for that P has a ’good’
reduction. Then, End(ε) ∼= End(E), i. e. End(E) = OK .
Proof : see [6] and [5].
⇒ ∃ some π ∈ OK with p = π.π, and then| E(Fp |= p + 1 − (π + π).

3.4

Fast Point Addition and Multiplication

At this position, we will give some algorithms and methods to find a random
point on a given elliptic curve and discuss the efficient fast point addition andxxxixmultiplication methods appeared in our computations later.
By Hasse’s theorem, we can conclude that for a given q we have a range of√
4 q about the value q + 1. In order try to find a random point for a given elliptic
curve over Fq , we can use the following algorithm due to [7] with almost uniform
distribution of elements of Fq .
ALGORITHM: Determining a random point in Fq
Input: An elliptic curve over Fq ,Output: A ’random’ point P ∈ Fq ,1. Do the the following;(a) Pick a random x ∈ Fq ;(b) Substitute x for X in the Weierstrass form of the curve E;(c) Try to find out Y ;(d) If such y’s can be found, choose one and set P = (x, y).
2. Until such a point P is found
3. Return P .
For prime fields Fp , each orders occur with an almost uniform distribution for
details see reference [43].

3.4.1

Point Addition

We will concentrate our attention only on p > 3 not for caharacteristics 2 or 3,
as we do not need such characteristic in our furher discussions (for fields of characteristic 2 of cryptographic interest, there are analogus methods as we describe
here for details see [7]). Our obeservations in point addtion and multiplication
are also based on the results from [7] and its references.

xl

Affine Coordinates
Review: As we already discussed for the fields characteristic is not equal to
2 or 3, for a given two points P1 = (x1 , y1 ) and P2 = (x2 , y2 ), given in affine
coordinates, such that P1 , P2 6= O and P1 6= −P2 (these two conditions can betrivially checked), we have P1 + P2 = P3 = (x3 , y3 ) and this can be compute as
follows
1. If P1 6= P2 ,−y1(a) λ = xy22 −x,
1(b) x3 = λ2 − x1 − x2 ,(c) y3 = (x1 − x3 ).λ − x3 − y1 .
2. If P1 = P2 ,(a) λ =

3x21 +a,2y1(b) x3 = λ2 − 2x1 ,(c) y3 = (x1 − x3 ).λ − x3 − y1 .
• For P1 6= P2 , we have one field inversion and three field multiplications,which can be abbreviated by 1I + 3M.
• For P1 = P2 , we have one field inversion and four field multiplications,which can be abbreviated by 1I + 4M.
Remark 3.13. We can neglect in this case the cost of field addition and multiplication by small constants (for example in the computation of λ for the case
P1 = P2 ).
Projective Coordinates
As we already explained, too, a projective point P = (X, Y, Z) satisfies thefollowing Weierstrass equation
Y 2 Z = X 3 + aXZ 2 + bZ 3 .

xli

If Z 6= 0, it corresponds to the affine point (X/Z, Y /Z). Hence, it turns outthat other projective representations can lead to more efficient implementations.
In particular, we will prefer ’weighted’ projective representation, i. e. (X, Y, Z)
will correspond to (X/Z 2 , Y /Z 3 ) whenever Z 6= 0. It is equivalent then to using
projective curve of the form
Y 2 = X 3 + aXZ 4 + bZ 6 .
Then the zero point O = (γ 2 , γ 3 , 0) for some γ ∈ F∗q . One can easily see that conversion from affine to projective is trivial, while conversion in the other direction
costs 1I + 4M.
The key observation in connection with weighted projective coordinates isthat point addition can be done using field multiplication only, with no inversions
required. The total costs is then 16M (for details see [7])3.4.2Fast Point Multiplication

Here point multiplication on the group of rational points of elliptic curves is the
special case of the problem of exponentiation of in general abelian groups (aswe use multiplication symbol for general setting of abelian groups). Therefore,
this problem corresponds to the related shortest addition chain for integers, i. e.
starting from 1, and computing at each step the sum of two previous result, whatis the least number of steps required to obtain k?
Certain characteristics of the elliptic curve version of the problem must also betaken into account to obtain faster computational methods and hence algorithms,
although general methods of exponentiation can be used to solve point multiplication problem.
We will not give details in the analysis of these algorithms that we will give
below. These can be found in [7] For the sake of correctness, when analyzing the complexity of the section, and for simplicity we will consider the case thexliifield of char. 2 which can easily be extended for our case p > 3, where p is a prime.
ALGORITHM: Point Multiplication: Binary MethodPjInput: A point P and an l-bit integer k = l−1
j=0 kj 2 ,Output: Q = [k].P ,1. Q ← O;
2. For j = l − 1; to 0 do;(a) Q ← [2]Q;(b) if kj = 1 then Q ← Q + P ;(c) j ← j − 1.
3. Return Q.
Our second method is m-ary method, where m = 2r for some r ≥ 1 and hence
binary method is the special case of this method corresponding to r = 1.
ALGORITHM: Point Multiplication: m-ary MethodPd−1
kj mj , kj ∈ {0, 1, · · · , m − 1}
Input: A point P and an integer k = j=0
Output: Q = [k].P ,1. Precomputation(a) P1 ← P ;(b) For i = 2; to m − 1 do;
i. Pi ← Pi−1 + P (we have Pi = [i].P );ii. i ← i + 1.
(c) Q ← O;
2. Main Loop(a) For j = d − 1; to 0 do;
i. Q ← [m]Q (this requires r doublings.);xliii

ii. Q ← Q + Pkj ;iii. j ← j − 1.
(b) Return Q.
It can be easily verified that the algorithm computes [k].P , following theHorner’s rule[m](· · · [m]([m]([kl−1 ]P ) + [kl−2 ]P ) + · · · ) = [k]P.
The doubling in the main-loop can be exploited to obtain additional savings: by
splitting the computation of [m]Q into two different stages, one can skip also
the multiples of P in the precomputation. this leads to an improvement on the
m-ary method, this modified version of m-ary method will be our third algorithm.
ALGORITHM: Point Multiplication: m-ary MethodPd−1
kj mj , kj ∈ {0, 1, · · · , m − 1}
Input: A point P and an integer k = j=0
Output: Q = [k].P ,1. Precomputation(a) P1 ← P , P2 ← [2]P ;(b) For i = 2; to (m − 2)/2 do;i. P2i+1 ← P2i−1 + P2 ;ii. i ← i + 1.
(c) Q ← O;
2. Main Loop(a) For j = d − 1; to 0 do;
i. If kj 6= 0 then do
A. Let sj , hj be such that kj = 2sj hj
B. Q ← [2r−sj ]Q (this requires r doublings.);
C. Q ← Q + Phj ;xliv

D. j ← j − 1.
ii. Else sj ← r
A. Q ← [2sj ]Q;
B. j ← j − 1.
(b) Return Q.
Note that a slightly modified version of horner’s method proves the correctness of this algorithm, too. At this stage we will once more generalize the method
and give the so-called Sliding Window Method.
ALGORITHM: Point Multiplication: Sliding Window MethodPjInput: A point P and an integer k = l−1
j=0 kj 2 , kj ∈ {0, 1}
Output: Q = [k].P ,1. Precomputation(a) P1 ← P , P2 ← [2]P ;(b) For i = 1; to 2r−1 − 1 do;
i. P2i+1 ← P2i−1 + P2 ;ii. i ← i + 1.
(c) j ← l − 1, Q ← O;
2. Main Loop(a) While j ≥ 0 do
i. If kj = 0 thenA. Q ← [2]Q,
B. j ← j − 1.
ii. Else do:
A. Let t be the least integer such that j − t + 1 ≤ r and kt = 1
B. hj ← (kj kj − 1 · · · kt )2 ,C. Q ← [2j−t+1 ]Q + Phj ,xlv

D. j ← t − 1.
(b) Return Q.
It is time now to mention the so-called Signed Digit representations, it is thecase that the subtraction in the group of rational pints of elliptic curves has virtually the same cost as addition. For canonical curve representations the negativeof a point P = (x, y) is (x, x + y) in characteristic two, and (x, −y) in odd characteristic. This leads us to reduce the number of curve operations by means ofaddtion-subtraction chains in point multiplication method.
Consider now integer representations of the form k =Plj
j=0 sj 2 , where sj ∈{−1, 0, 1}. It is said to be then binary signed digit, abbreviated by SD, representation. This representation includes all integers 0 ≤ k ≤ 2l+1 − 1 along with
their negatives. This redundancy can be traded off for a sparsity constraint which
results more efficient point multiplication algorithms.
Definition 3.19. An SD representation is said to be sparse, if it has no adjacentnon-zero digits, that is Sj sj+1 = 0 ∀ j ≥ 0. A sparse SD representation is also
called a non-adjacent form, denoted by NAF.
Lemma 3.4.1. Every integer k has a unique NAF. The NAF has the lowest
weight among all SD representations of k, and it is at most one digit longer than
the shortest SD representations of k.
Proof : See references also for more details [39], [38] Chapter 10, [37].
Our next algorithm computes the NAF of a non-negative integer given in binary representation.
ALGORITHM: Conversion to NAF
Pj
Input: An l-bit integer k = l−1
j=0 kj 2 , kj ∈ {0, 1}
PlOutput: k = j=0 sj 2j , sj ∈ {−1, 0, 1}
1. c0 ← 0;
2. For j = 0; to l do;

xlvi

(a) cj+1 ← b(kj + kj+1 + cj )/2c (assuming that ki = 0 for i ≥ l);(b) sj ← kj + cj − 2cj+1 ;(c) j ← j + 1.
3. Return (sl sl−1 · · · s0 ).
It is by Morain and Olivos showed that NAFs have fewer zeros than binary
representations, i.e. they proved that in expected weight of a NAF of length l is
l/3. For details see [36].
Now we will give a slightly generalized algorithm sliding window method,
namely Signed m-ary Window Decomposition.
ALGORITHM: Signed m-ary Window DecompositionPj
Input: An l-bit integer k = l−1
j=0 kj 2 , kj ∈ {0, 1}, kl = 0
Output: A sequence of pairs {(bi , ei )}d−1
i=0
1. d ← 0, j ← 0;
2. While j ≤ l do;(a) If kj = 0
i. j ← j + 1(b) Else doi. t ← min{l, j + r − 1}, hd ← (kt kt−1 · · · kj )2 .
ii. If hd > 2r−1 then do:
A. bd ← hd − 2r ,B. increment the number (kl kl−1 · · · kt+1 )2 by 1.
iii. Else
A. bd ← hd ,B. ed ← j, d ← d + 1, j ← t + 1
3. Return the sequence (b0 , e0 ), (b1 , e1 ), · · · , (bd−1 , ed−1 )xlvii

Proof of the correctness of algorithm: The correctness of the algorithm
is verified inductively by ascerting the the condition

k=

d−1
X

bi 2ei +lX

kj 0 2j0

j 0 =ji=0each time the loop in Step 2 is checked. As j > l, the second sum of theabove equation vanishes, giving the desired decomposition of k, then the proof
is straightforward. The only observation here is that the condition in step b.ii
holds, then b.ii.A substracts 2j+r from the sum in equation and b.ii.B adds itback as we have t = j + r − 1.
Now after having the sequence of {(bi , ei )}d−1
i=0 , the modification of the sliding
window method is easy to construct.
ALGORITHM: Signed m-ary WindowsP
ei
Input: A point P , and such that k = d−1i=0 bi 2
Output: Q = [k]P .
• Precomputation
1. P1 ← P , P2 ← [2]P2. For i = 1 to 2r−2 − 1 do(a) P2i+1 ← P2i−1 + p2 ,(b) i ← i + 1
3. Q ← Pbd−1 .
• Main Loop
1. For i = d − 2 to 0(a) Q ← [2ei+1 −ei ]Q,(b) If bi > 0 then Q ← Q + Pbi ,(c) Else Q ← Q − P−bi ,xlviii(d) i ← i − 1.
2. Q ← [2e0 ]Q,
3. Return Q
Using the analysis analog to that of unsigned window scheme, one can derive
the correctness of the algorithm for details see [7].

3.5

Point Counting and Other Problems

Remark 3.14. There are also other concepts of elliptic curves coming together
with primality proving algorithms and public key cryptography, some of these arefollowings• Determining the Group Order, point counting algorithm, of rational pointsof elliptic curves over finite fields. For these there are lots of approaches,– Baby Step-Giant Step Schoof ’s Algorithms, ant its variants e. g.
due to Etkies’ and Atkin’s based on the variation of Hasse’s theorem.
– Counting the points by means of constructing non-supersingular elliptic curves with complex multiplication.
• Discrete Logarithm for elliptic curves, abbreviated by ECDLP, which givesa change to obtain analogus cryptographic protocols like ElGamal andDiffie-Hellmann. Note that according to Pohling-Hellmann approach solving DLP modulo n, where n is order of an abelian group G,
n = pe11 .pe22 · · · Prer is equivalent to solving each DLP modulo pi , where pi ’s
are prime for 1 ≤ i ≤ r.
Note: We will introduce the concepts of Point Counting Problem in details
in Chapter 5 & 6. Because of the fact that primality proving algorithms of Goldwasser & Killian and Atkin’s are principally based on the Point Counting Problem
and hence Schoof’s approach (or its variants) and CM-method, respectively.

xlix

We will also see computationally efficient methods of the above concept ina detail and try to get efficient methods in particular for curves with complex
multiplication. Furthermore, we will also see how the results coming from thearithmetic of elliptic curves over C or Q and the results of Algebraic Number
Theory that we developed in the former chapter will be applied in our primality
testing and proving algorithms.
For more general treatment of the theory of arithmetic of elliptic curves andtheir usage in extensive areas of both applied and theoretical mathematics canbe found in [6] and [5]. Furthermore, for the usage of elliptic curves particularly
in Cryptography, Coding theory and Factorization of integers see [1] and [38].

lchapter 4
Primality Testing and Proving
Algorithms
In this chapter, we are going to introduce and explain different primality testing &proving algorithms. We will start with a historical prime listing method, namely
sieve of Eratoshenes, which will give us a possibility up to a given bound, say it
up to 1016 , to store prime numbers and therefore enables us to verify whether agiven prime candidate N , N < 1032 , is prime by means of just checking whether
it is divisible by any of the list element.
Question• What is a Primality Test / Primality Proof ?
• What is the meaning of certificate in our context?
Definition 4.1.

1. If our algorithm gives us a possibility to reprove the pri-mality of the candidate mathematically then we say that our algorithm is
a Primality Proving algorithm.
2. If with our algorithm it is not possible to recheck mathematically that ourcandidate is prime, then we say that our algorithm is a Primality Testingalgorithm. In that case we have also two possibilities;(a) An algorithm is said to be a True Primality Testing, if it can determinewith mathematical certainty that our candidate is prime.
(b) An algorithm is said to be a Probabilistic Primality Testing, if ourcandidate is a probable prime.

li

3. If it is possible to reprove the primality of our prime candidate, then we saythat it has a (primality) certificate.

4.1

Prime Number Generation

In this section, we will explain a very historical primality listing methods. For
generalization and modern methods see [2].
ALGORITHM: Sieve of Eratosthenes
Input: A natural number B, B > 2, and the set L = {2}Output: Prime numbers between [2, B],
1. List the numbers n ∈ [2, B], for example ai = i, 2 ≤ i ≤ B and initialisep = 2;
2. While p < B do:(a) Start with p and delete all n’s of the form k.p with k ≥ 2;(b) Find the smallest non-deleted number p0 with p0 > p, then L = L∪{p0 };(c) p ← p0 and goto b;
3. Return L.
Remark 4.1. One can improve the efficiency in the followings• Considering just i ∈ [2, B], or better the numbers coprime to 210 = 2.3.5.7.
• One can also generalize the sieve to the intervals [A, B], such as [A, A+106 ].

4.2

Trial-division Method

The easiest way to test whether a number is prime or not is the so-called trial√
division. If a given number N ∈ N is not divisible by any of the primes ≤ N ,then we can conclude that N is prime. (As if N = a.b, 1 < a ≤ b < N ⇒a2 ≤ a.b = N ⇒ p2 ≤ N for primes p | a) Of course, since the complexity islii√O( N ), it is not possible for big numbers to use this method (say it more than
100-digits).But one can use trial-division to factor an integer to test whether wehave small factors or not. Therefore, ideally it can also be used at the first up
to a given bound in before terminating our more advanced algorithms later. One
can choose a bound B and by means of sieve of Eratosthenes store the primes ina list to see at the first if our prime candidate is divisible by any element of thislist. Of course if it is the case, we can conclude that our candidate is composite
and divisible by that element of our previously chosen list.

4.3

Fermat’s Primality Test

According to the Fermat’s last theorem, one can consider that whether we havesomehow an inverse of Fermat so that we can apply a Primality Testing based on
this inverse. But unfortunately such an inverse does not exist. But we can havea compositeness Test owing to the following Corollary of Fermat.
Proposition 4.1. A number N is composite if there exists a ∈ N such thataN −1 6≡ 1 mod(N ).
Proof : trivial by Fermat’s theorem.
Definition 4.2. The composite number N which passes Fermat’s test is called
Carmichael Number. The smallest such a number is 561 = 3.11.17
Theorem 4.1. There are infinitely many Carmichael Numbers.
By above theorem it is clear that Fermat test can not guarentee at all whether
the checked candidate is a true prime. However this test enables us to detect mostof the composite numbers at the first. Furthermore, by means of generalizationof Fermat’s and trying to get a generalized version of inverse of Fermat’s theorem
will give us a change to introduce the N − 1, N + 1, and hence at the end
Jacobi-sum and ECPP algorithms. There are also other probabilistic primality
tests by means of generalizing Fermat. In the next section we will deal with suchalgorithms. They are also used with some modification in cryptographic protocols

liiiwhen the true primality testing and proving algorithms are not available or not
required to guarantee a reasonable security of the considered cryptosystem.

4.4

Probabilistic Primality Testing Algorithms

Now it is time to give the probabilistic primality tests, namely Solovay-Strassen
and Miller-Rabin Tests. The idea is to use the definitions of pseudoprimality,
euler pseudoprimality and at the end strong pseudoprimality.

4.4.1

Solovay-Strassen Probabilistic Primality Test

Now Solovay-Strassen Algorithm will be given. This and Miller-Rabin Algorithms
are actually probabilistic algorithms. The answer composite is always true ,hence they are called in some texts Compositeness Algorithms. Moreover, if thecandidate is prime then the answer is always ’prime’. However, it is possible tohave a false answer ’prime’, though the candidate may actually be ’composite’.
ALGORITHM:Solovey-Strassen
1. N ∈ N, N is odd;
2. choose a number t ∈ N randomly and for 1 ≤ i ≤ t choose ai randomly;
3. For 1 ≤ i ≤ t compute(a) ci ≡ ani mod(N ) with reciprocity law
N −1(b) bi ≡ ai 2 mod(N );4. if bi 6= ai for some i,then Return: ’composite’ ;5. else Return: ’possibly prime’;
Proposition 4.2. Solovay-Strassen error-probability bound Let N be an
odd composite integer. The probability that the Solovay-Strassen test declares
N to be ’prime’ is less than ( 12 )t .

liv

4.4.2

Miller-Rabin Probabilistic Primality Test

We just generalize the above idea of Sollovay-Strassen by considering strong pseudoprimes instead of Euler pseudoprimes (because spsp < epsp < psp ). We therefore introduce the Miller-Rabin Test, which is also called strong pseudoprimality
test.
ALGORITHM:Miller-Rabin
1. N ∈ N, N is odd, set N = 1 + 2l .m, where m is odd;
2. choose a number t ∈ N randomly and for 1 ≤ i ≤ t choose ai randomly;
3. Test for 1 ≤ i ≤ t(i)whether ami ≡ 1 mod(N )j(ii)or there exists j with 0 ≤ j ≤ l such that a2 .m ≡ −1 mod(N );4. if both (i) & (ii) are false, Return:’composite’;
5. else Return: ’possibly prime’;
Proposition 4.3. Miller-Rabin error-probability bound Let N be an odd
composite integer. The probability that the Miller-Rabin test declares N to be’prime’ is less than ( 41 )t .
Remark 4.2. fixed bases in Miller-Rabin a strategy that is sometimes employed is to fix the bases a in the Miller-Rabin algorithm to be the first few primes(composite integers may be ignored using iteratively the Miller-Rabin), insteadof choosing them at random. Note that trial division and the so-called prime list
may be used at the first to reduce the unnecessary computation in Miller-Rabinalgorithm, i. e. choose a bound B and list all primes p < B and use at the firsttrial division to guarantee that the given candidate is not divisible by any of theseprimes < B. For instance, if one chooses B = 256, then %80 of composite odd
numbers can be discarded before employing Miller-Rabin.
Remark 4.3. Let’s compare Sollovay-Strassen & Miller-Rabin algorithms according to [2]:lv

1. The Soolovay-Strassen test is computationally more expensive.
2. The Sollovay-Strassen test is harder to implement as it also involves Jacobi
symbol computations.
3. The error probability for Sollovay-Strassen is bounded by ( 12 )t , while theerror probability for Miller-Rabin is bounded by ( 41 )t .
Therefore we can conclude that there is no need to use Sollovay-Strassen
instead of Miller-Rabin.

4.5

N − 1 Primality Testing Algorithms

There are also some primality testing algorithms based on the inverse of the Fermat’s theorem. Indeed, our aim here is to get an inverse of Fermat by using some
additional informations. Actually if we can factor the number N −1 completely or
partially one can give a proof of primality with some extra informations. We will
now give the most important proposition of both N − 1 (resp. N + 1) primality
testing algorithm and our ECPP Algorithms.
Theorem 4.2. Lucas Let a, N ∈ N with gcd(a, N ) = 1. If aN −1 ≡ 1 mod(N ),N −1

but a d 6≡ 1 mod(N ) for every divisor d > 1 of N − 1, then N is prime.
Proof see [17].
Theorem 4.3. Let N ∈ N, N − 1 =a

N −1≡ 1 mod(N ) but a

N −1
pi

Qt

ei
i=1 pi .

If there exists a ∈ N with6≡ 1 mod(N ), then N is prime.

Proof see [17].
Theorem 4.4. Let N ∈ N, 2 | N , and N − 1 =N −1exists ai with aiN −1 ≡ 1 mod(N ), ai i

Qtei
i=1 pi for 1 ≤ i ≤ t.

If there6≡ 1 mod(N ), then N is prime.

Proof see [17].
Note that in order to apply any of the above theorem, we need the complete
factorization of N − 1. Mostly, it is not possible to have such complete factorization, but we have one of the divisor of N − 1 which satisfies some properties thenlvi

we can also test the primality of the candidate N .
Pocklingston’s theorem will be the center of such partial factorization of N −1,
as we will see, we can get also depending on this theorem other testing criterias.
Proposition 4.4. Pocklington’s Theorem Let p be a prime divisor N-1. As−1
−1sume that we can find an integer ap such that aN≡ 1 mod(N )and (aN−pp1, N ) = 1. Then if d is any divisor of N, we have d ≡ 1 mod(pαp ), where pαp is
the largest power of p which divides N-1.
proof: It is enough to look at all prime divisors of N.Now if p is a prime≡ 1 mod(d), since ap is coprime to N hence to d. On
divisor of N, we have ad−1
p
N −1

−1
the other hand , we have ap p 6≡ 1 mod(d), as (aN− 1, N ) = 1. If e is the exactporder of ap modulo d, then we have e divides d-1 but not (Np−1) but e divides N-1.
hence pap | e | d − 1, hence d ≡ 1 mod(pap ).
Proposition 4.5. Assume that we can write N − 1 = F.U where (F, U ) = 1, F is√completely factored and F > N . Then, if for each prime dividing N we can find
an ap satisfying the conditons of Pocklington, then N is prime. Conversely, if N
is prime , for any prime p dividing N-1, one can find ap satisfying the conditionsof Pocklington.
Corollary 4.1. Assume that we can write N − 1 = F.U where (F, U ) = 1,
F is completely factored, all the prime divisors of U are greater then B, and√B.F ≥ N . Then, for each p dividing F we can find an ap satisfying conditions−1of Pocklington, and if furthermore we can find an aU cuch that aN≡ 1 mod(N )U

and (aFU − 1, N ) = 1, then N is prime. Conversely, if N is prime, then ap and aU
can be always found.

4.5.1

Test

Now we will give N − 1 algorithm by means of a pseudocode. At the first we will
give an algorithm for the case that we can have the full factorization of N − 1,in the second case we concentrate our attention on partially factorized case.

lvii

ALGORITHM:N − 1 Test (Fully factorized N − 1)
Input: N ∈ N, N is odd, the bases ai , 0 ≤ i ≤ r, which passed Miller-Rabbin
test,
Output: ’prime’, or ’composite’.
1. Set i = 0 (m0 first base);s

2. Determine s, t such that N − 1 = m2i t;
3. While i < k do:(a) if mti ≡ 1 mod(N ), then i ← i + 1,(b) while k < s do:k• If m2i t ≡ −1 mod(N ), i ← i + 1 and STOP,• k ← k + 1,(c) If k = s return ’composite’.
4. Return ’prime’.
Now if we cannot factorize the N − 1 fully we will just test the conditions of
Pocklington in the following algorithm:
ALGORITHM:N − 1 Test (Partially factorized N − 1)
Input: N ∈ N, N is odd, P is a prime divisor of N − 1, and Q =Qnqi
i=0 pi is adivisor of N − 1 with prime factors pi ’s such that N − 1 = Q.P with Q < P .
Output: ’prime’, or ’composite’.
1. Choose an natural number a ∈ N such that 1 < a < N ,2. If aN −1 6≡ 1 mod(N ), then GOTO 1,
3. If gcd(aQ − 1, N ) 6= 1, then GOTO 1,
4. Return ’prime’.

lviii

4.5.2certificate

The so-called DOWN-RUN method to get the pairs (i, mi ), together with exponents we get the so-called certificate. In fact if we store these datas, for a second
programmer it is possible to verify the primality or compositeness of the result
once more.

4.5.3

Special primes

Easiest form is N − 1 = 2m
Let n ∈ N be an odd integer. We know thatxn − 1= 1 + x + · · · + xn−1
x−1
Let us substitute x with −x, then we haven +1(−x)n −1
= 1 − x + · · · + (−x)n−1 ⇒ xx+1
= 1 − x + · · · + xn−1 ⇒ x + 1 | xn + 1, if−x−1

we have n ≡ 1 mod2.
Let m = bu, where u is odd, then x := 2b ⇒ 2b + 1 | 2bu + 1 = N . According
to lemma 2.2.3 we have then together with theorem 3.3 that if a ∈ Z withaFn −1 ≡ 1 mod(Fn ), and a(Fn −1)/2 6≡ 1 mod(Fn ), then we can conclude that Fn isnprime, where Fn = 22 + 1.
Theorem 4.5. Peppin Let n ≥ 1. Then Fn is prime if and only if
32

2n −1

≡ −1 mod(Fn ).

Theorem 4.6. Let n ≥ 2 and p | Fn , p is prime. Then we have p ≡ −1 mod(2n+2 ).
Note: Proofs of the above two theorem see [17].
With the help of the Poclington’s theorem we can conclude also the following
results
Theorem 4.7. Let N = K.2n + 1, 2 - K, 0 < K < 2n + 2. Then N is prime if
N −1

and only if ∃ a ∈ Z with a 2 ≡ −1 mod(N ).

lixTheorem 4.8. Let N = K.2n + 1, n ≥ 2, K is odd and 3 - K. Furthermore,assume that we have 0 < K < 2n + 2. Then N is prime if and only if
N −1

3 2 ≡ −1 mod(N ).

4.6

N + 1 Primality Testing Algorithms

Our aim is now to find a similar Test for N + 1, when the factorization of N − 1
is not partially or fully possible.
2
Remark 4.4. Let p, q be two integers, so thatq p − 4.q is not a square, thenx2 + px + q have two distinct zeros r1,2 = p2 ±p2
− q. If we consider r1 we get
4

the following recursive formula ;Proposition 4.6. Powers of r can be given in the following way
V (m) + U (m).
r1m =

p

p2 − 4q2

where V (m) and U (m) can be calculated recursively as follows :U (0) = 0, U (1) = 1, U (m) = pU (m − 1) + qU (m − 2),
V (0) = 2, V (1) = p, U (m) = pV (m − 1) − qV (m − 2),
U and V are lucas sequences of p and q.
Proof : see see [17].
Proposition 4.7. (Lucas Test) Let N be an odd integer. If there exists δ with( Nδ ) = −1 and for every prime factor r of N+1 there exist some p and q withp2 − 4q = δ such that
U (N + 1) ≡ 0 mod(N ) & U (are satisfied, then N is prime.
Proof : see [17].

lxn+1) 6≡ 0 mod(N )r4.6.1Test

Now we will give N − 1 algorithm by means of a pseudocode (only for partiallyfactorized case).
ALGORITHM:N + 1 Test (Partially factorized N + 1)
Input: N ∈ N, N is odd, P is a prime divisor of N + 1, and Q =Qnqi
i=0 pi is adivisor of N + 1 with prime factors pi ’s such that N + 1 = Q.P with Q < P .
Output: ’prime’, or ’composite’.
1. Choose r, s such that gcd(r, s) = 1,
2. If ( r−4s
) 6= −1, then GOTO 1,
N
3. If V ( N 2+1 ) 6≡ 0 mod(N ), then GOTO 1,
4. If V ( Q2 ) 6≡ 0 mod(N ), then GOTO 1,
5. Return ’prime’.

4.6.2

certificate

As in the case of N − 1, we can get a certificate for N + 1 tests in terms of theparameters r, s. As we know that here r depends on the number s, we can choose
also r = 1 if s is even, and r = 2 if s is an odd integer.

4.6.3

Special primes

We know by Corollary 2.2 that if N = 2n − 1 is prime, then n must also be prime.
Recall that we say such primes Mersenne Primes. One can use the so-called N +1
tests much more efficiently.

4.7

ECPP Algorithms

As we have already seen from the above two sections, if we have the partial
factorization of N − 1 or N + 1, there is a version of inverse of Fermat’s littlelxitheorem. With some additional requirements it is not actually a difficult problem
to be able to test the primality of a given number. It is also clear that thesealgorithms are somewhat special, as they need the factorization of N − 1 resp.
N + 1. The first general purpose primality proving algorithm was introduced
in 1979 by Addleman, Pomerence and Rumely. This algorithm is called Jacobi
Sum Test and based on the group rings of cyclotomic extensions. The idea of thistest is therefore also to do with a generalization of Fermat’s little theorem. The
running time of this algorithm is O((logN )c.log log logN ) for some constant c > 0.
Hence, it is almost a polynomial time algorithm. However the algorithm was notpractical. Cohen and Lenstra developed a practical version of this algorithm andis of use also in practice.
The reason why ECPP Algorithms are superior in practice is that it gives
a short primality certificate (or certificate of primality), that is once given theparameters of the algorithm it is much more easy for the second party to verify
the result ( in our case prove or disprove the primality of the number which wasconsidered to be prime ). Jacobi Sum test cannot give such a certificate, that issecond programmer has to write and execute the entire test once more, though
it is slightly faster than our ECPP Algorithms up to 600-700 digits.

4.7.1

Test

Here we will explain the algorithm based on elliptic curves over finite fields, instead of using the suitably strong generalizations of Fermat’s theorem, we will
use the group of rational points of elliptic curves over FN itself. Now at the firststep we will morally certain that our number N is prime, i. e. it has passed theprobabilistic primality proving tests such as Sollavay-Strassen and Miller-Rabin.
Hence we will work as if N was a prime, assuming for example that each non-zeroelement modulo N is invertible. In the event that there exist some non-invertible
elements modulo N , we will immediately stop the algorithm and give a nontrivial factor of N by taking a GCD with N (for example by using extended
GCD Algorithm). We will therefore consider an elliptic curve over Z/N Z. It

lxii

means that we consider a Weierstrass equation y 2 = x3 + ax + b a, b ∈ Z/N Z,(4a3 + 27b2 ) ∈ (Z/N Z)∗ (it is not necessary to consider general Weierstrass equation as (N, 6) = 1). Furthermore, we will perform the group operation of rational
points of our elliptic curve as if N was a prime. Hence, we can assume from now
on that all computations can be performed without any problems.
Our basic strategy in our ECPP Algorithm is the so-called DOWN-RUN strategy of the following theorem, which is the elliptic curve analog of the theoremsof N − 1 and N + 1 tests.
Theorem 4.9. Let N be a positive integer coprime to 6 and different from 1.
Let E be an elliptic curve modulo N . Assume that we know an integer m and apoint P ∈ E(Z/N Z) satisfying the following conditions.
1. There exists a prime divisor q of m such that√4q > ( N + 1)2
2. m.P = OE = (0 : 1 : 0)
3. ( mq ).P = (x : y : t) with t ∈ (Z/N Z)∗
Then N is prime.
proof : Assume that N was not a prime Let p be the smallest prime divisor of
N in E(Z/pZ),the image of P has order a divisor of m but not divisor of m/q ast ∈ (Z/pZ)∗ . Since q is a prime q divides the order of the image of P in E(Z/pZ),√√
i.e. q ≤| E(Z/pZ) |. By Hasse’s Thm. q < ( p + 1)2 . Since p ≤ N (as being√
the smallest prime by assumption) we get q < ( 4 N + 1)2 which is trivially acontradiction to our assumption.
Now we are facing with 3 main problems to solve here namely,• How to choose the elliptic curve?
• How to find P ?

lxiii• How to choose m ∈ N?
Now the following proposition gives the answer of the second and third question.
Proposition 4.8. Let m =| E(Z/pZ) |. If for a prime number q dividing m√
4q > ( N + 1)2
is satisfied then there exists a point P ∈ E(Z/N Z) s.t. m.P = OE = (0 : 1 : 0)and ( mq ).P = (x : y : t) with t ∈ (Z/N Z)∗ . Note that m =| E(Z/pZ) | can becomputed as if N was a prime.
The ECPP (elliptic curve primality proving ) algorithms is given then as follows;
ALGORITHM:ECPP
INPUT: a number N ∈ Z, whose primality will be (dis)proved.
OUTPUT: If N is composite , a divisor of N , if N is prime return ’prime’.
1. choose a non-supersingular elliptic curve E over Z/N Z
2. m ←| E |;√3. choose a prime number q > ( 4 N + 1)2 such that q | m;
4. Choose a ’random’ point P ∈ E;
4.1 If m.P 6= 0 go to 4;
4.2 If mq .P = 0 go to 4;
4.3 if there exists an error return the divisor of N (extended GCD algorithm)
5. return ’prime’.
As we see in this algorithm, we reached an algorithm analog to the one that
we developed in N − 1 and N + 1 tests. As we already explained these tests are
special since they need the partial or full factorization of N −1 or N +1. However,
if we change the group FN with the group of elliptic curves over FN , we can reacha general primality proving algorithm, which also, in contrast to Jacobi sum testlxiv

and its variants, gives us a chance to reprove or disprove the result that we havetested. For further discussions on short prime certificates see the next chapter.
Further, the idea is unchanged, namely the so-called DOWN-RUN strategy. We
get intermediate prime candidates, and applying the DOWN-RUN strategy, we
get the following;
Remark 4.5. The primality of a number N can be reduced to the primality ofthe smaller prime candidates q < N by means of the above ECPP Algorithm.
Moreover, applying this algorithm recursively, we can prove the primality of thegiven prime candidate N just by trial-division or N − 1 test, as we can get anintermediate prime candidate q < 1016 .
After introducing our algorithm, we have to deal with the following problems,
which are actually coming together with the results of the theory of arithmetic ofelliptic curves over C or FN in Chapter 3, and the results from Number Theory
and Algebraic Number Theory in Chapter 2.

• How can we choose elliptic curves?
• How can one compute the cardinality of the group of rational points ofelliptic curves over finite fields, whose characteristic is ’big’?
• Is this algorithm practical?
Our basic difficulty in our algorithm is to find m =| E(Z/pZ) |. We will discussin detail the methods (both theoretic and practical) in the next chapter. Afterthat we will give the complexity analysis of the Algorithm in chapter 6 and inchapter 7 we will give the implementation details.
As we already see, we need in this case also an elliptic curve E over ZN with√the property that it has a prime divisor, which satisfies the condition > ( 4 N +1)2 .
Furthermore, we need also a point P on this curve which satisfies the conditionsof the Theorem 4.9. That means we have a probabilistic algorithm, although theresult is always true and reprovable. Note that in case N is not a prime, it islxv

not possible to terminate the algorithm, but if we insert the condition of GCD
with the intermediate result, we will get a divisor of N and which also gives us achance to detect the divisor of N , for the case N is composite.

4.7.2

certificate

As we already witnessed in N −1 and N +1 tests, we can apply in ECPP algorithm
also the so-called DOWN-RUN strategy here we get recursively the intermediate
prime candidates:
N0 = N, N1 (= q), · · · , Ni , · · ·Definition 4.3. N0 = N (= q0 ), N1 (= q1 ), · · · , Ni (= qi ), · · · with corresponding
elliptic curves Ei and the cardinalities mi , are called primality certificate bymeans of ECPP.
In contrast to the Jacobi sum test, we can get with these certificate candidates
a certificate algorithm, which verifies the result in a much more little time thanoriginal algorithm.

Remark 4.6. As we already explained this, algorithm gives a short certificate
by means of mi ’s . It gives a possibility that anybody can prove to his or her
satisfaction the primality of N using much less work than executing the original
Algorithm.

4.8

Primality Testing in reality

We can of course combine all of the algorithms discussed in this chapter so as
to obtain a true primality testing method, which may be used in cryptographic
protocols such as Diffie-Helmann and ElGammal.

lxvi

ALGORITHM:A Combined Primality Testing
INPUT: a number N ∈ Z, whose primality will be (dis)proved,
OUTPUT: If N is composite , a divisor of N , if N is prime return ’prime’.
1. Test, if N is coprime to 30. If not return {’N ’ has a divisor gcd(N, 30)};
2. Test, if N is divisible by any elements p of prime list up to < 1016 (trial
division) if yes return {’N ’ has a divisor p};
3. Test, whether 2N −1 ≡ 1 mod(N ) (almost all composite number can be
therefore detected), if not return {’N ’ has a divisor p};
4. Factorise N −1 and terminate N −1 algorithm, if we have answer ’composite’
return {’N ’ has a divisor p};
5. Factorise N +1 and terminate N +1 algorithm, if we have answer ’composite’
return {’N ’ has a divisor p};
6. Terminate Miller-Rabbin Algorithm with a given bound (parameter), if wehave answer ’composite’ return {’N ’ has a divisor p};
7. terminate ECPP algorithm, if we have answer ’composite’ return {’N ’
has a divisor p};
8. return {’prime’}.
Note that one can also use in step 7 Jacobi sum test, if there is no need tocertify the primality of the number. The algorithms of Jacobi sum and ECPP havebeen also combined methods based on the concept of ’dual elliptic primes’ (see[28]).

lxvii

chapter 5
ECPP (Elliptic Curve
Primality Proving)
ALGORITHMS
We have basically explained the theory of primality testing algorithms and ECPP
algorithms in the last chapter. Our basic problem now is to determine, as we discussed, the order of the group of rational points of elliptic curves over finite
fields. One method is due to Schoof. His algorithm is a Baby Step-Giant Step
algorithm based on the theorem of Hasse, which computes m =| E(Z/pZ) | intime O(log 8 N ). The ECPP Algorithm, which uses the Schoof’s algorithm so as tofind m =| E(Z/pZ) |, is due to Goldwasser and Kilian. It was showed that underreasonable hypothesis on the distribution of prime numbers in short intervals, theexpected running time of the algorithm is O(log 12 N ), hence is polynomial in logN .
The theoretical advance has been made by Adleman and Huang, by proving
the following theorem.
Theorem 5.1. There exists a probabilistic polynomial time algorithm which canprove or disprove that a given number N is prime.
Their idea is to use, in addition to elliptic curves, Jacobians of curves of genus
2, and a similar algorithm to the one like Goldwasser and Kilian. Although, theiralgorithm is not practical, they proved the above theorem, see [25], i. e. theyfound an algorithm which runs in polynomial time. Of course both Goldwasser
and Kilian and Jacobi Sum tests are not of that type since only the expectedrunning times are polynomial, but the worst case may not be!

lxviii

5.1

Goldwasser-Kilian ECPP Algorithm

Goldwasser & Killian used the same idea of the ECPP-Algorithm that we explained in last chapter. They use the so-called Schoof Algorithms to find the
cardinality of the group of E(FN ).

5.1.1

Schoof ’s Algorithms

Problem: To find | E |. For every point P ∈ E(Fq ) with n = ord(P ) we have ak ∈ N such that k.n =| E |.
√√⇒ By Hasse’s theorem k.n ∈ [q + 1 − 2 q, q + 1 + 2 q] =: I.
√
Observation: If ord(P ) > 4 q, then there exists exactly one k ∈ N suchthat k.n ∈ I (and hence k.n =| E |).
Baby-Step Giant-Step Algorithm
Idea:• Choose a ’random’ point P ∈ E(Fq ) and verify that (in apprx.
√
ord(P ) > 4 q.

√

q steps)• Determine the unique number k.n ∈ I with k.n.P = O (and hence | E |).
ALGORITHM:A Baby-Step Giant-Step

1. Initial Step;√• Set h := 2 q, hence | E |∈ [q + 1 − h, q + 1 + h],• Define t0 := trace(φ) − h. Then | E |= q + 1 − trace(φ) = q + 1 − h − t0with t0 ∈ [0, 2h],√√
• Set m := d 2he = d2 4 qe ⇒ ∃a, b ∈ {0, 1, · · · , m − 1} such thatt0 = am + b.
2. Baby-Steplxix

(a) For b < m:i. compute b.P and store in a list,
ii. b ← b + 1.
3. Giant-Step(a) For b < m:i. Compute (q + 1 + h − am).P,
ii. Compare, if (q + 1 + h − am).P = b.P . If so return {t0 = am + b},
iii. b ← b + 1.
4. Return {q + 1 − t0 + h}.
By the construction we have am + b = t0 ∈ [0, 2h] ⇒ trace(φ) = t0 − h ⇒| E |= q + 1 − trace(φ) = q + 1 − t0 + h, which proves hence the correctness of
the above algorithm.
Schoof ’s Algorithm
In this case we will try to find the trace t = trace(φ), where φ the Frobenious.
As we know from the functional equation | E(Fq ) |= q + 1 − t.
Idea: Compute at the first t modulo p for all p prime.
Chinese Remainder Theorem: throughout the equations t mod(pi ) for i =1, · · · , k, we can determine t mod(p1 · · · pk ) uniquely.
√ √We know that t ∈ [−2 q, 2 q] (by Hasse) so that t is uniquely determined√by tmod(pi ) for i = 1, . . . , k if p1 · · · pk > 4 q. It is meaningfull to start with
p1 , p2 , p3 , · · · = 2, 3, 5, · · ·ALGORITHM: Schoof ’s Algorithm

lxx

1.Step: Trying to find a p-torsion point P on E, where p is a prime (P 6= 0),
not neceserally P ∈ E(Fq ). We can find this point by means of modular polynomials.
Let [m] : E → E is a morphism, i. e. there exist homogene polynomials
θm , wm , ψm such that [m].(P ) = (θm : wm : ψm ).
These polynomials are known and written recursively as (assuming W.L.O.G.)z = 1:
ψ0 (X, Y ) = 0, ψ3 (X, Y ) = 3X 4 + 6aX 2 + 3bX − a2
ψ1 (X, Y ) = 1, ψ4 (X, Y ) = (2X 2 + 10bX 4 − 10a2 X 2 − 2baX − 2a − b2 )ψ2
2
3,m>0− ψm−1 ψm+1
ψ2 (X, Y ) = Y , ψ2m+1 (X, Y ) = ψm+2 .ψm
22
ψ2m (X, Y ) = ψ12 (ψm+2 ψm+1
− ψm−2 ψm+1
)ψm .

P is a p-torsion point ⇔ [P ](P ) = O = (0 : 1 : 0) is the unique point at
infinity ⇔ ψp (P ) = 0.
In fact: P is a p-torsion point on E ⇔ Y 2 = X 3 + aX + b and ψm (X, Y ) = 0.
W.L.O.G. we can assume that ψm is linear (substitude the non-linear terms withthe first equation). Then we can solve ψm with respect to Y , namely hm (X).
Therefore: P = (x : y : 1) ∈ E with p.P = O ⇔ hm (x) = 0 & Y 2 = X 3 +aX +b.
2.Step: For ψ = 0, · · · , p − 1, test whether now ψφ(P ) = φ2 (P ) + q.P , where
φ is Frobenious and P is p-torsion point.
If YES: t = ψ mod(p) then by Corollary 2.1 part 2, we have a functional
equation
φ2 + q − tφ ≡ 0
so we have ψφ(P ) = φ2 (P )+q.P = t.φ(P ) ⇒ φ((ψ−t)p) = 0 ⇒ (ψ−t)p ∈ Ker(φ)
Ker(φ) = {(x : y : z) | (xq , y q , z q ) = (0 : 1 : 0)} = {(0 : 1 : 0)} = {O}⇒ (ψ − t).p = 0 ⇒ p | ψ − t ⇒ t ≡ ψ mod(p).

lxxiHence we get t modulo p, then by means of Chinese Remainder Theorem(CRT), we will get t mod(p1 · · · pk ), and hence | E |= q + 1 − t. Note that thisalgorithm was improved by Atkin and Elkies for details see [29], [48].

5.1.2

ECPP Algorithm (Goldwasser-Kilian)In this section, we will give the algoritm due to Goldwasser & Kilian in a pseudocode due to Cohen [1].
ALGORITHM:ECPP Algorithm (Goldwasser-Kilian)
INPUT: a number N ∈ Z, whose primality will be (dis)proved,
OUTPUT: If N is composite , a divisor of N , if N is prime return TRUE.
1. Initialize Set i ← 0 and Ni ← N .
2. Is Ni small? If Ni < 216 , trial divide Ni by the primes from the list up to
215 . If Ni is not prime GOTO step 9.
3. Choose a random curve Choose a and b at ’random’ in Z/Ni Z, andcheck that 4a3 + 27b2 ∈ (Z/Ni Z)∗ . Let E be the elliptic curves whose affine
Weierstrass equation is y 2 = x3 + ax + b.
4. Use Schoof Using Schoof’s Algorithm, compute m ←| E(Z/Ni Z) |. If
Schoof’s algorithm fails GOTO step 9.
5. Is m OK? Check whether m = 2q where q passes the Miller-Rabbin test
(or more generally, trial divide m up to a small bound, and check thatthe remaining factor q passes the Miller-Rabbin test and is larger than√
( 4 Ni + 1)2 ). if this is not the case GOTO step 3.
6. Find P Choose at ’random’ x ∈ Z/Ni Z until the Legendre (or Jacobi)
3

symbol ( x +ax+b) is equal to 0 or 1 (this will occur after a few trial atNimost). Then compute y ∈ Z/Ni Z such that y 2 = x3 + ax + b. if there is a
failure GOTO step 9.

lxxii

7. Check P ? Compute P1 ← m.P and P2 ← (m/q).P . If during the computations some division is impossible GOTO 9. Otherwise, check that P1 = OE ,i. e. that P1 = (0 : 1 : 0) in projective coordinates. If P1 6= OE , GOTO
step 9. finally if P2 = OE , GOTO step 6.
8. Recurse Set i ← i + 1 and Ni ← q and GOTO step 2.
9. Backtrack (We are here only when Ni is not prime, which is unlikely
occurence.) If i = 0, output a message saying that N is ’composite’ andterminate the algorithm. Otherwise, set i ← i − 1 and GOTO step 3.
Remark 5.1. As stated in the algorithm, if N is not a prime, the algorithm may
run indefinitely and so should perpaps not be called algorithm in this sense.

5.1.3

certificate

The results that we introduced in the last chapter can be without any reserve
applicable.

5.2

Atkin’s ECPP Algorithm

We see in this chapter and chapter 3 that the basic problem to be able to deal
with our primality proving algorithms is that we have to find the size of thegroup of rational points of elliptic curves over a finite field Fq . This problem
is solved in Goldwasser-Kilian algorithm using the theoretical algorithm due to
Schoof. However, Schoof’s Algorithm and its variants seem almost impossible toimplement. We will therefore use the properties of elliptic curves over finite fields
related to complex multiplication, that we introduced in chapter 3.

5.2.1

Generating Elliptic Curves with Complex Multilication

As we already defined in chapter 3, an elliptic curve has Complex Multiplication(CM), if End(E) is strictly bigger than Z. By theorem 3.10, j(τ ) is an algebraic

lxxiiiinteger of degree hD . If Z[τ ] is the maximal order of some imaginary quadratic
number field K, then H = K(j(τ )) is an extension of K of degree hD . This isactually the maximal unramified abelian extension of K. As we already explainedin theorem 3.10, H is called the Hilbert class field of K, i. e. it is a field underwhich every ideal in Z[τ ] will become principal when considered as an ideal in ZH .
It is required to find the Hilbert class polynomial, HD (x), of theorem 3.10.
An intermediate approach will here be used to do this. Set q = e2iπτ , and!24∆(τ ) = q 1 +X(−1)n q n(3n−1)/2 + qn(3n+1)/2.

n≥1This can be computed as if it was written. Then we will use the well-known
theorem on modular forms thatg23 − 27g32 =



2π
w2

12
∆.

Now the formula that we will use for computing j(τ ) isj(τ ) =

(256f (τ ) + 1)3,
f (τ ))
where f (τ ) = ∆(2τ
. Now we will give the algorithm to find the Hilbert class∆(τ )Polynomial due to Cohen.
ALGORITHM: Hilbert Class Polynomial
Input: Given a negative discriminant D
Output: The monic polynomial of degree hD in Z[X] of which j((D +is a root.
1. Initialize Set P ← 1, b ← Dmod(2) and B ← bp| D | /3c;

2. For j = 0; to l do;
3. Initialize a Set t ← (b2 − D)/4 and a ← max(b, 1);

lxxiv

√

D)/2)

4. Test If a - t GOTO step 4. Otherwise compute j ← j((−b +√D)/(2a))using the above formulas. Now if a = b or a2 = t or b = 0 set P ← P.(X −j),else set P ← P.(X 2 − 2Re(j)X+ | j |2 );5. Loop on a Set a ← a + 1. If a ≤ t, GOTO step 3;
6. Loop on b Set b ← b + 2, if b ≤ B GOTO step 2, otherwise coefficients of
P to the nearest integer, output P and terminate the algorithm.
We need to state a remark due to Cohen:
Remark 5.2. The final coefficients of P (known to be integers) must be computedwith an error at most 0.5 For this, we need to make a priori estimate on the sizeof coefficients of P . In practise, we look at the constant term, which usually
not far from being the largest. This term is equal to the product of values√j((−b + D)/(2a)) over all reduced forms (a, b, c), and the modulus of this is√approximately equal to eπ |D|/(2a) hence the modulus of the constant term isrelatively close to 10k , wherep
π |D|X1k=,ln(10)awhere the sum running over all reduced forms (a, b, c) of discriminant D.
Construction of elliptic curves with CM
Instead of taking ’random’ elliptic curves as in Goldwasser-Kilian algorithm, we
will choose elliptic curves with complex multiplication by an order of an imagi√nary quadratic number field K = Q( D) where N , our prime candidate, splits
as a product of two elements. This will enable us apply the theorem 3.15 due to
Deuring which will give us immediately the cardinality of E(Z/N Z).
In this case we will work as if N was prime, too. We must find a negative
discriminant D such that N splits as a product of two elements (so as to ensure
ourselves that the curve is not supersingular), and hence N is not inert in K. Thiscan be acchieved by means of Cornacchia’s algorithm of Chapter 2. Applying

lxxv

this algorithm repetitively to get a solution of x2 + Dy 2 = 4N we can find sucha discriminant D. Once such a pair (x, y) is found than we have
√
x+y D
,
π=
2
now by applying Deuring, we get
m =| E(Z/N Z |= N + 1 − π − π̄ = N + 1 − x.
We know that m = p + 1 − t, where t is the trace of Frobenius. Recall thatt = π + π̄, where π is an element of norm N . A solution by means of Cornacchia
of x2 + Dy 2 = 4N means that
√
x+y D
π=±
.
2
Then, the order N + 1 + x will be the order of quadratic twist of E. Hence,by theorem 3.14 in general case we have just these two elliptic curves up to isomorphism (E and its quadratic twist), which actually proves the following lemma:
Lemma 5.2.1. Suppose E and E 0 have the same j-invariant but not isomorphic
to each other over a field Fp , where p is a prime. If j 6= 0 and j 6= 1728, then E 0
is quadratic twist of E and if E = p + 1 − t and E 0 = p + 1 + t.
Proposition 5.1. Let w(D) be the numbers of roots of unity in the imaginary
quadratic order of discriminant D, hence w(D) = 2 if D < −4 (as in the above
case!), w(−4) = 4 and w(−3) = 6. Then there exist exactly w(D) isomorphismclasses of elliptic curves modulo N with CM by the imaginary quadratic order of
discriminant D
Proof : immediate from thm. 3.14.
¯ where ζ
Above proposition corresponds to the factorisation N = (ζπ)(ζπ),
runs over all w(D)-th roots of unity (note that this will in paricular correspondto the above situation ζ = ±1 if D < −4).

lxxvi

Our second aim is to write down explicitely the equation of these elliptic
curves. Since N splits in the order of discriminant D, we have w(D) | N − 1and there exist (N − 1)/2 values of g ∈ Z/N Z ((N − 1)/3 if D = −3) such thatg (N −1)/p 6= 1 for each prime dividing w(D). Choosing one values of g we get thefollowing equations of elliptic curves√

Lemma 5.2.2. Let c = j/(1728 − j), where j = j( D+2 D ).
1. If D < −4 we have the following affine equation of ellitic curve E
y 2 = x3 − 3cg 2k x + 2cg 2k for K = 0 or 1.
2. If D = −4 we havey 2 = x3 − g k x for 0 ≤ k ≤ 3.
3. If D = −3 we havey 2 = x3 − g k for 0 ≤ k ≤ 5.
Now at the end we will explain how we can find the roots of Hilbert class polynomials over Z/N Z. This is the problem of factoring, and hence finding the rootsof, polynomials over finite fields. We will introduce the so-called Berlekamp’s
algorithm to solve this problem, which is the generalisation of Gauss eleminationin Linear Algebra. For details see [46] and [2].
ALGORITHM: Berlekamp’s Algorithm
Input: Given a square-free polynomial f (x) of degree n in Z/N Z[x].
Output: The factorization of f (x) into monic irreducible polynomials.
1. For each i, 0 ≤ i ≤ n − 1, compute the polynomial;iN

x mod(f (x)) =n−1
X

Nij xj .

j=0

Note that each Nij is an element of Z/N Z.
2. Form the n × n matrix Q whose (i, j)-entry is Nij ;lxxvii3. Determine a basis v1 , · · · , vt for the null space of the matrix (Q − In ), where
In is the n × n identity matrix. The number of irreducible polynomials off (x) is then precisely t;
4. Set F ← {f (x)}. (F is the set of factors of f (x) found so far; their productis equal to f(x).);5. For i from 1 to t do;(a) For each polynomial h(x) ∈ F such that degh(x) > 1 do the following:i. compute gcd(h(x), vi (x) − α) for each α ∈ Z/N Z,
ii. Replace h(x) in F by all those polynomials in the gcd computations whose degrees are ≥ 1.
(b) i ← i + 1.
6. Return the polynomials in F as the factors of f (x).

5.2.2

ECPP ALGORITHM (Atkin)

Now we will introduce our ECPP Algorithm due to Atkin in form of pseudocode.
As we saw in the proceeding section, our aim is now, instead of finding ’random’
elliptic curves and applying our DOWN-RUN strategy as in Goldwasser-Kilian,
to apply the the theory of complex multiplication for elliptic curves and to use
elliptic curves with complex multiplication in our general DOWN-RUN strategy.
Our aim here is that we will give at the first the algorithm and in the following
sections we are going to try to enhance the efficiency of the algorithm and totry to optimize some of the computational problems coming together with ouralgorithm and elliptic curve generation with CM in finite fields with large prime
characteristic.
ALGORITHM:ATKIN’S ECPP
INPUT: a number N ∈ Z, whose primality will be (dis)proved,
OUTPUT: If N is composite , a divisor of N , if N is prime return TRUE.

lxxviii

1. Initialize Set i ← 0, n ← 0 and Ni ← N .
2. Is Ni small? If Ni < 216 , trial divide Ni by the primes from the list up to
215 . If Ni is not prime GOTO step 14.
D
3. Choose next discriminant Let n ← n + 1 and D ← Dn .If ( N) 6= 1,GOTO step 3. Otherwise, use Cornacchia’s Algorithm to find a solution,if
exists, of the equation x2 + | D | y 2 = 4N . if no such solution exists, GOTO
step 3.
4. Factor m For m = N + 1 + x, m = N + 1 − x (and in addition for m =N + 1 + 2y, m = M + 1 − 2y if D = −4, and m = N + 1 + (x + 3y), m =N + 1 − (x + 3y)if D = −3), then factor m.
5. Does a suitable m exist? If, using the proceeding step, for at least one
value of m we can find a q dividing m which passes the Miller-Rabbin test√and > ( 4 Ni + 1)2 , then GOTO step 6, otherwise GOTO step 3.
6. Compute the elliptic curve If D = −4, set a ← −1, b ← 0. If D = −3,
set a ← 0, b ← −1. Otherwise compute the minimal polynomial HD ∈√Z[X] of j((D + D)/2). Then reduce HD modulo Ni and let j be one of
the roots of H¯D ≡ HD mod(Ni ). Then set c ← j/(1728 − j) mod(Ni ),a ← −3c mod(Ni ), b ← 2c mod(Ni ).
7. Find g By making several ’random’ choices of g. find g such that g is aquadratic non-residue modulo Ni , and in addition if D = −3, g (Ni −1)/3 6≡
1 mod(Ni ).
8. Find P Choose at ’random’ x ∈ Z/Ni Z until Legendre (resp. Jacobi)
3

symbol ( x +ax+b) is equal to 0 or 1 (this will occur in a few trial at most).
Ni
Then compute y ∈ Z/Ni Z such that y 2 = x3 + ax + b (if this algorithm fails
GOTO step 14) Finally set k ← 0.
9. Find right curve Compute P2 ← (m/q).P and P1 ← q.P2 on the curve
whose affine coordinate is y 2 = x3 +ax+b. If during the computations somelxxix

division was impossible, GOTO step 14. If P1 = O = (0 : 1 : 0) GOTO
step 12.
10. Set k ← k + 1. If k ≥ w(D) GOTO step 14, else if D < −4 set a ← ag 2 ,b ← bg 3 , if D = −4 set a ← ag, if D = −3 set b ← bg and GOTO step 8.
11. Find a new P Choose at ’random’ x ∈ Z/Ni Z until Legendre (resp. Ja3cobi) symbol ( x +ax+b) is equal to 0 or 1 (this will occur in a few trial atNimost). Then compute y ∈ Z/Ni Z such that y 2 = x3 + ax + b (if this algorithm fails GOTO step 14). If P1 6= O = (0 : 1 : 0) then GOTO step10.
12. Check P If P2 = OE , GOTO step 2.
13. Recurse Set i ← i + 1, Ni ← q and GOTO step 2.
14. Backtrack (We are here when Ni is not prime, which is very unlikely.)
If i = 0, output a message saying that N is composite and terminate thealgorithm. Otherwise, set i ← i − 1 and GOTO step 3.
As seen in the algorithm, the basic difference comparing with GoldwasseKilian is to find the elliptic curves with CM, after that we try to use the sameN − 1 analog DOWN-RUN strategy, that is applying this algorithm we will geta list of probable primes and will try to prove the primality of smaller numbers
and by means of this number we will conclude the primality of our actual prime
candidate N .

5.2.3

Problems and Approaches

We are going to discuss in this section the problems that we have to deal withcoming together with our above algorithm and introduce some approaches tomake this algorithm more practical.

lxxx

Factoring m
Firstly, we have to check whether m satisfies the the condition which will enable
us to apply the Theorem 4.9, i. e. that m is not prime, but its largest prime√
factor q is larger than ( 4 N + 1)2 . Since we introduced a practical algorithm, we
have to deal with this problem much more seriously than in Goldwasser-Kilian
test. We will use firstly the trial divide m up to a much higher bound, and thenwe will use much serious factorization algorithms such as Pollard-ρ and p − 1 tofactor m. Here are some approaches of Atkin to solve factorization problem:
Pollard’s ρ: It is reasonable to find all factors less than 108 with this method.
We decide to make 105 iterations of this method. Atkin accumulated the iteratesof the function and do only two gcd’s. See [42], [41] and [11].
ECM: One can use the algorithm as described in [41] with the parametrizations of [42] and [41] for having curves with some prescribed small divisors.
One of the basic problem is the storage. One concentrates just on the numbers< 10700 see [11].
Pollard’s p − 1: Note that this is reasonable when testing the Cunningham
numbers which have often the property of being congruent to ±1 modulo somelarge known prime integer. So one can spend a little time to see whether we havea possibility to get a factor of m of that type.
If m is not suitable to apply the conditions of theorem 4.9, we have still one
more change, that is we can use the other elliptic curves up to isomorphism as
we introduced in proposition 5.1 and lemma 5.2.2.
Which curve are we in?
We have w(D) elliptic curves modulo N , where D is an imaginary quadratic
discriminant (Corollary 5.1). However, a priori only one of these curves up toisomorphism corresponds a suitable value of m, and it is not clear which one oflxxxi

these. For D = −3 or D = −4 it is easy to see a recipe which one is actually
the right curve (As they are corresponding cases of j = 0 and j = 1728). For
D < −4, such a recipe is almost impossible to find. What we can do is simply
to compute m.P for our suitable m and a ’random’ P , (P 6= O), on one of these
two elliptic curves. If this is not equal to the identity, in projective coordinatesm.P 6= O = (0 : 1 : 0). If this is equal to identity we cannot conclude that we areon the right curve, but as P has been randomly chosen, we can probably still use
the curve to satisfy the hypothesis of theorem 4.9. note also that, we do not needto prove mathematically that our curve is the right one, since our aim is just to
satisfy the conditions of the theorem by means of a an elliptic curve over Z/N Z.
What is a good discriminant D?
In order to obtain the equation of the curve, it is necessary to find the values ofj modulo N . This is very very difficult if the class number hD is large. Hence,
we have to start with imaginary quadratic discriminant D whose correspondingclass numbers hD is as small as possible.
Remark 5.3. Some people have expressed concerns that using small class numbers hD in cryptographic purposes. Because, the resulting curve may be thenmore amenable to some future attacks than more general field K. On average it√
is expected that the class number of hD will grow as O( D), so small class numbers are in some sence special as we explained in our ECPP algorithm. This may
cause possible a future, as yet unknown, attacks to try to solve discrete logarithm
problem (DLP), and hence cryptosystems, based on the groups of rational pointsof elliptic curves constructed with CM-method. For details see [7].
Let p be a prime number. Then according to chapter 1 that p is a norm√in Q( D) if and only if p is represented by the principal form of H(D). For
practical purposes as we introduced above, we can assume that D < 1016 withhD ≤ 50. They form a set D We have then presumably | D |= 10628 (For details[11]).

lxxxiiWhat happens if we have a theoretical failure?
We explained in chapter 3 that we have a complex multiplication, i. e. if End(E)is strictly larger than Z, then we have two cases, namely

1. End(E) is an order of an imaginary quadratic number field,
2. End(E) is the maximal order of a quarternion algebra.
Our curve construction corresponds the first case, i. e. we constructed elliptic curves which are an order of an imaginary quadratic number field. However,
if we face with the case 2 (supersingularity case), then it is possible to have atheoretical failure:√
If q ≤ ( 4 N + 1)2 , then we cannot apply our theorem. In paricular, it cannot
be used when the number of points, m, is a perfect square and Z/N Z is isomorhic
to (Z/M Z)×(Z/M Z) with m = M 2 . This is exactly the case 2, i. e. if M | N −1.
We have also then by Hasse√

N −1≤M ≤√N +1√
putting b N c = a and N = a2 + r, with 0 < r < 2a + 1 ⇒ a ≤ M ≤ a + 1.
Suppose after that at the first M = a. Then as M | N − 1 we havea | a2 + r − 1
that is a | r − 1. Then we have two cases.
• When r = 1, one has N = a2 + 1 and E has complex multiplication by
Q(D) with D = (m − N − 1)2 − 4N = −4a2 .
• When r > 1 as 0 < r < 2a + 1, we have r − 1 = a and thus N = a2 + a + 1.
√
It is then easy to see that E has complex multiplication by Q( −3). For
details see [11].

lxxxiii

Hilbert Polynomials
Proposition 5.2. The norm of j in Q(j), which is the same as HD (0), is the
cube of an integer in Z.
Proof see [11].
It is worth remarking here that we will not need to prove mathematicallythat our computations regarding j are correct, as the ECPP algorithm and corresponding proof depends only on our calculations on the curves. We describeda method and algorithms in section 5.2.1 with special emphasis on the numericalvalue of the function j(τ ).
Atkin has checked and verified the result of the above proposition whether
HD (0) is a cube of an integer with error bound 0.5, as we have explained in 4.2.1
for the discriminant D = 23 and got the following Hilbert class polynomial
H23 (X) = X 3 + 3491750X 2 − 5151296875X + 233753 .
Weber Polynomials
The coefficients of HD (X) of j become larger if the class number hD grows.
Although, one can afterwards reduce the results modulo N , to compute these coefficients, we will need to use high precision computations of the values of j(τ ) for
every quadratic irrational τ corresponding to reduced imaginary quadratic formof discriminant D. Since these computations are independent of N, one of thesolution might be that results of these will be stored before going into algorithm,
but again as the coefficients are very large that even for a moderately sized list
we would need an enormous amount of storage.
In order to avoid such kinds of computational challenges, we are going to use
meromorphic functions which are closely related to the function j(τ ) and whichhave analogous arithmetic properties. These functions are called Weber functions
or Weber polynomials. Results are due to [11] and [7].

lxxxiv

Define the following Weber functions, using Dedekind’s η-function, η(z):−1h(τ ) = ζ48

γ2 (τ ) =√ η(2τ )η((τ + 1)/2)
η(τ /2), h1 (τ ) =, h2 (τ ) = 2
,
η(τ )
η(τ )
η(τ )

h(τ )24 − 16(h(τ )24 + 8)(h1 (τ )8 − h2 (τ )8 )
,
γ
(τ
)
=
,
3
h(τ )8h(τ )8where ζn = e2πi/n . These functions are not all algebraically independent because
they are all related to j via the equations (for more details see [11]);j=3
3(h24 − 16)3
(h24
(h24
1 + 16)2 + 16)=== γ23 = γ32 + 1728.
24
24
24
h
h1
h2

Weber calls µ(τ ) a class invariant if µ(τ ) lies in the Hilbert class field of Q(j).
Clearly j(τ ) is a class invariant. Furher, with Weber functions one can determine
much more class invariants. These give rise to polynomials, abbreviated usually
by WD (X), using almost the same idea to compute HD (X). Finding roots ofthese polynomials, which have considerably small coefficients in general, will allow us to recover the j-invariants.
Let −D be an imaginary quadratic discriminant and d be a square free pos√√
itive integer such that Q( −D) = Q( −d). Then we can apply the following
conditions in turn• If D ≡ 3 mod(6) use µ =√−D.γ3 (τ ),√• If D ≡ 7 mod(8) use µ = h(τ )/ 2,• If D ≡ 3 mod(8) use µ = h(τ ),√• If D ≡ ±2 mod(8) use µ = h1 (τ )/ 2,• If D ≡ 5 mod(8) use µ = h(τ )4 ,√• If D ≡ 3 mod(8) use µ = h(τ )2 / 2.
The only problem here is that if we have D ≡ 3 mod(8) and D 6≡ 3 mod(6).
In that case the degree of Weber polynomial WD (x) is then 3hD not hD . So it islxxxv

a better idea then not to use such discriminants.
We get above for the case D = 23 the following Hilbert class polynomial
H23 (X) = X 3 + 3491750X 2 − 5151296875X + 233753 .
If we use the Weber polynomials instead of Hilbert class polynomials we get
W23 (X) = X 3 − X − 1.
The above example shows that how we can benefit by using Weber polynomials
instead of Hilbert class polynomials.
Furher discussions
Some improvement can be done by examining the possible splitting property of√
the rational primes in the quadratic extension K = Q( −d) and its Hilbert classfield. This reduces the following lemma due to [7]:Lemma 5.2.3. Let d be a square free integer and p such that we can find asolution to the diaphontine equationp = x2 + dy 2 .
Then we have the followings;
1. If p ≡ 3 mod(8) then D ≡ 2, 3 or 7 mod(8).
2. If p ≡ 5 mod(8) then D ≡ 1 mod(2).
3. If p ≡ 7 mod(8) then D ≡ 3, 6 or 7 mod(8).
) = ( −D
) = 1.
In particular, we must have ( −dppAs we introduced earlier one can perform the Berlekamp’s algorithm to factor
the polynomials HD over Z/N Z. However, this can be expensive, since for agiven N , the complexity of such a computation is basically proportional to thelxxxvisquare of the degree of the polynomial, i. e. in our case ∼ hD . These explain
why we discarded the case D ≡ 3 mod(8), since in this case, we might work on
polynomials of degree 3hD . The methods to factor the polynomials over theirgenus field and other computational remarks related to these can be found indetail in the articel of Atkin. See [11].

5.2.4

certificate

As we introduced both in general ECPP algorithm and in ECPP algorithm ofGoldwasser & Kilian, it is also possible to verify the result of the algorithm, if wehave built a sequence of intermediate probable primes together with the foundelliptic curves and its number of points and a point on it satisfying the requirements of theorem. This is as we already explained is a certificate of primality.
This is generalization of the ideas of Pratt & Pomerence, see [45] and [44].
For example, Kaltofen and Valente agreed on the certification of 222-digit prime.
They also checked the 1226-digit record.

5.3

Remarks

We introduced the Atkin’ ECPP algorithm. In contrast to the ECPP algorithm ofGoldwasser and Kilian, this algorithm performs well in practice, since it is ample
to use this algorithm to prove the primality of numbers from 100 to thousands
decimal digits and more. It is possible with current technology of computers
to test the arbitrary integers up to 400 digits in a few days on a single SU N
3/60 workstation with this algorithm. Numbers with less than 800 digits can be
performed in about one week of real time using distributed process on about 10
workstations.

lxxxvii

However, there are also some remaining uncertainties to find the best strategy
for applying methods to larger probable prime inputs. The general operations
which should be implemented efficiently and optimally , and whose timings on aparticular machine are relavent to the strategy are:• Sieving and subsequent factorization of the number of points of groups ofrational points of an elliptic curve,• Exponentiaton modulo a large prime p (and equivalent square roots, pseudoprime tests),• Exponention on elliptic curves modulo a large prime p,• Solution of polynomial equation congruences modulo a large prime p.

lxxxviii

chapter 6
Analysis
In this chapter, we are going to analyze the running time complexities of our
ECPP algorithms due to Goldwasser-Kilian and Atkin, respectively.

6.1

Preliminaries

The following two theorems due to Heath-Brown and Lenstra, respectively, allow
us to analyze our algorithm for uniformly distributed inputs.
Theorem 6.1. Heath-Brown Call an integer y sparse if there are less then√√y/2blog yc primes in the interval [y, y + b yc]. Then there exist a constant α
such that for sufficiently large x,| {y : y ∈ [x, 2x], y is sparse} |< x5/6 log α x.
Proof: see [9].
Theorem 6.2. Lenstra Let p > 5 be a prime. Let,√√S ⊆ [p + 1 − b pc, p + 1 + b pc].
If a curve given by (A, B), A, B ∈ Z in Weierstrass normal form, over Zp ischosen uniformly, then,prob(| (A, B) |∈ S) >c
| S | −2. √,log p 2b pc + 1

where c is a some fixed constant.

lxxxixProof: see [9].
Essentially the size of a ’random’ group is at most O(1/log p) times less likely
to have a particular property as a randomly selected integer in√√[p + 1 − b pc, p + 1 + b pc],
provided that | S |> 2.

6.2

Analysis

We are going to firstly have a look at the analysis of random elliptic curve generation, which satisfies the conditions of our main theorem 4.9. We now analyse therunning time of elliptic curve generation part satisfying our condition in terms ofthe number of points in an appropriate interval around p/2. Define S(p) byS(p) :=√√ 
p + 1 − b pc p + 1 + b pc,
, q is prime .
q:q∈
2
2


√
Lemma 6.2.1. Let p > 5 be a k-bit prime, and suppose that | S(p) |= O( p/log c p).
Then prime number generation will run for expected O(k c+8 ) steps before it terminates.
Proof: see [9].
Lemma 6.2.2. Let p > 5 be a prime, and let (A, B) be chosen uniformly fromcurves over Zp . Let also S(p) be defined as above. Thenprop(| (A, B) | is twice a prime) >c | S(p) | −2.
+ 1,√
log p 2b pc

where c is some fixed constant.
Proof: see [9].
After introducing the basic facts which was used to analyse the ECPP algorithm of Goldwasser & Kilian, we are going to give the theorems which and theirprove can be found in [32] and [24] in details.

xcTheorem 6.3. Suppose that there exist two positive constants c1 and c2 such√that the number of primes in the interval [x; x + 2x] (x ≥ 2) is greater than√c1 x(logx)−c2 . Then Goldwasser-Kilian algorithm proves the primality of N in
expected time O((log N )10+c2 ).
Theorem 6.4. There exists two positive constants c3 and c4 such that for allk ≥ 2, the proportion of prime numbers N of k-bits for which the expected time ofGoldwasser-Kilian algorithm is bounded by c3 (log N )11 is at least 1−c8 2−k1loglog k.

At the end we can summarize the analyzis of the algorithm as follows:
1. Given an input of length k, the algorithm produces a certificate of primalitythat is of length O(k 2 ), and requires O(k 4 ) steps to verify.
2. The algorithm terminates in expected polynomial time on every prime number, provided that the following conjecture is true:
CON JECT U RE : (∃c1 , c2 > 0)π(x +

√

√
c2 x
x) − π(x) ≥,log c1 x

f or x suf f iciently large.
3. There exist constants c1 and c2 such that for all k sufficiently large, thealgorithm will terminate in expected c1 k 11 time for all but at most,
2k
c /log log k

2k 2

,

of the inputs. In other words, the algorithms can be proved to run quickly
on all but vanishingly small fraction of the prime numbers.
As for Goldwasser-Kilian algorithm, we have only the heuristic analysis citedin [33]. Atkin and Morain found that the running time of Atkin’s ECPP isroughly O((log N )6+ ). for some  > 0. Other implementation details and practical considerations to make this algorithm more practical and more optimized
was briefly discussed in chapter 5, and for further details see [11].

xcichapter 7
Implementation, LiDIA classes
and Conclusion
7.1

Implementation details

7.1.1

SINGULAR source codes Examples

We will start with our implementations with a prime listing algorithm (like sieve of
Eratosthenes) in programming language SINGULAR by using the prime funtion.
Note: Limitation for the integers in SINGULAR (upper bound) is 2147483647.

.................................................................................
//The following function computes the list of primes given//in lower and upper bound from bigger to smaller//Written by Osmanbey Uzunkol...
proc primelist(int a,int b){list myprime;
int temp=prime(b);myprime[1]=temp;
int temp2=temp;
if (a!=1) {//if..
for(int i=2;temp>a;i++) {//if.
temp=prime((temp2-1));

xcii

if ((temp>a)&& (temp>2) ) {myprime[i]=temp;
temp2=temp;}}//end of if.

return(myprime);//end of if..
}else {
list myprime2=primelist((a+1),b);
int b=size(myprime2);
list myprime3;
for (int i=1;i<=b;i++) {myprime3[i]=myprime2[i];}myprime3[b+1]=2;
return(myprime3);}}.................................................................................
Example: Let us illustrate how this function works with a small example:.................................................................................
> primelist(45353109,45353264);[1]:45353237[2]:45353207[3]:45353201
[4]:

xciii

45353183[5]:45353173[6]:45353149[7]:45353111.................................................................................

.................................................................................
//Following programme tests whether the given prime candidate N//passes the trial-division algorithm as explained in the thesis//It computes the primes up to 32768 in a list and then tries to//divide the candidate any of this list elements. If one of the element//divides N then returns the prime, and proves that this number is//composite together with its divisor. If it returns 1 then we have a// (probable) prime. Written by Osmanbey Uzunkol...
ring r=0,x,lp; //in order to use the type number to compute big integers
proc isdivisible(number N) {list l=primelist(1,32768); //note that this option can be changed
int temp=size(l);//depending on the situation...

int i=1;
while(i<=temp) {if ((N mod l[i])==0){
if (l[i]!=N){
return(l[i]);
}
else

{

return(1);}xciv

}//end of ifi++ ;}return(1);}.................................................................................
Example: The following example illustrates and prove that given number isdivisible by the prime 3251.

.................................................................................
> isdivisible(1992882373366515526677171625362176265267366353667161984875872441);// ** redefining b **3251.................................................................................

Example: The following example shows that the given candidate 1532986441051165789751670481
04782789635951257974397 is (probable) prime. Although it is actually not, since
153298644105116578975167048104782789635951257974397 = 9661373.15867169615034693203043
402641092812547031489.

.................................................................................
> isdivisible(153298644105116578975167048104782789635951257974397);// ** redefining b **1.................................................................................

.................................................................................
//The following fuction computes the Legendre symbol for primes and Jacobi//symbol for integers in general as explained in the thesis.
//Written by Osmanbey Uzunkol..
ring r=0,x,lp;

xcv

proc Jacobi(number a,number n) {int i;
int s;
number temp=a;a=a mod n;
if (a==0){return(0);}if (a==1){

return(1);}if (gcd(a,n)>1) {return(0);}else {
while(temp mod 2==0) {temp=(temp/2);i++;}
if (i%2==0){ s=1;}
else {
if((n mod 8)==1||(n mod 8)==7) {
s=1;
else

}
{

s=-1;}}
if ( ((n mod 4)==3) && ((temp mod 4)==3) ) {s=(-s);}

if (temp!=1) {number n1=n mod temp;
int temp1=s*Jacobi(n1,temp);
return(temp1);}

xcvi

else {
if (i%2==0){

return(1); }else {
if((n mod 8)==1||(n mod 8)==7) {return(1);
else

}
{

return(-1); }}}}//end of else}.................................................................................
Example: Some examples of Jacobi funtion: For the first example as gcd(14414442441, 1626616611
101713) = 7, we have;.................................................................................
> Jacobi(14414442441,1626616611101713);0.................................................................................
Second and third one illustrate the case of quadratic residue and non-residue,
respectively.

.................................................................................
> Jacobi(64553633552,3232442001);
1> Jacobi(77575775,288287376);-1.................................................................................

.................................................................................
//The following function may be used instead of primelist function in

xcvii

//fermattest and Sollovay-Strassen Test.
//Written by Osmanbey Uzunkol..
proc base(int a){list l;int j=1;
for(j=1;j<=a;j++){l[j]=j+1;}
return(l);}.................................................................................

.................................................................................
//This function tests the primality (actually compositeness)//of the prime candidate N by using Fermat primality test//as explained in the thesis with the chosen prime base elements//between the below given bounds.Upper bound can be changed//within the limitations of integers in SINGULAR.
//Note that with a fast multiplication methods as we explained//for elliptic curves the efficiency can be speeded up. If//the answer takes much time than one has to use C++ version.
//Written by Osmanbey Uzunkol.
ring r=0,x,lp;
proc fermattest(number N){
if(isdivisible(N)>1){
return(0);}else{number r;number temp;
number exp=(N-1);

xcviiinumber j;list l=primelist(32768,33768);
int k=size(l);int i;
for(i=1;i<=k;i++) {
r=1;
for(j=1;j<=exp;j=j+1){
temp=l[i]*r;
r=temp mod N;}
if(r mod N!=1 mod N){
return(0);}}return(1);}}.................................................................................
Example: The compositeness of the candidate 64366536553727646563 was provenby calling the fermattest:.................................................................................
> fermattest(64366536553727646563);// ** redefining b **0.................................................................................
Furhermore, the (probable) primality of the following integer, which is a divisorof the above integer, was also proven. However, it takes lots of time as themultiplication procedure is slow in SINGULAR. Actually, if it takes more than 1
minute, the answer is probably a probable prime but it is a better idea to checkit in C++ version.

xcix

.................................................................................
> fermattest(3608596543910279);// ** redefining b **1.................................................................................

.................................................................................
//This function tests the primality (actually compositeness)//of the prime candidate N by using Sollovay-Strassen primality test//as explained in the thesis with the chosen prime base elements(not random)//between the below given bounds.Upper bound can be changed//within the limitations of integers in SINGULAR.
//Note that with a fast multiplication methods as we explained//for elliptic curves the efficiency can be speeded up. If//the answer takes much time than one has to use C++ version.
//Written by Osmanbey Uzunkol.
ring r=0,x,lp;
proc sollovay_strassen (number N){
if(isdivisible(N)>1){
return(0);}else{number r;number temp;
number exp=((N-1)/2);
number j;list l=primelist(32768,33768);
int k=size(l);int i;
for(i=1;i<=k;i++) {
r=1;
for(j=1;j<=exp;j=j+1){ctemp=l[i]*r;
r=temp mod N;}
if(r mod N!=Jacobi(l[i],N) mod N){
return(0);}}return(1);}}.................................................................................
Example: We will give two examples one is composite the other is (probable)
prime. However, the caution that we mentioned in fermattest is also the casehere.

.................................................................................
> sollovay_strassen(424234251616626552525441551421);// ** redefining b **0.................................................................................

.................................................................................
> sollovay_strassen(91346224180575661878056249);// ** redefining b **1.................................................................................

7.1.2

C + + source codes, used classes and Examples

In this section, we will see some implementation of primality tests with the help
LiDIA C++ library for Computational Number Theory. At the end by means ofciprimeproof method developed by J. Hechler, see [30] for LIDIA, the implementation of ECPP algorithm will be given in an example file written in C++ with
examples.
Here with the help of primelist function a list of primes in a given lower/upperbounds:.................................................................................
//This programme computes a list of prime numbers given in//lower and upper bound. It is almost the same as wriitten//in SINGULAR, but it is more efficient//due to fast computational capability of LiDIA//written by Osmanbey Uzunkol#include <LiDIA/prime_list.h>#include <iostream>using namespace LiDIA;
using namespace std;
unsigned long * primelist(unsigned long lower,unsigned long upper){unsigned long *prime;
prime_list primelist(lower,upper);int i;
i=primelist.get_number_of_primes ();int j=0;prime[j]=primelist.get_first_prime();unsigned long temp=prime[i];while (j<i){
j++;prime[j] = primelist.get_next_prime();temp=prime[j];}return(prime);cii}
int size_primelist(unsigned long lower,unsigned long upper){unsigned long *prime;
prime_list primelist(lower,upper);int i;
i=primelist.get_number_of_primes ();return(i);}int main(){unsigned long lower, upper, prime;
cout << "Please enter lower bound: "; cin >> lower ;cout << "Please enter upper bound: "; cin >> upper ;cout << endl;
prime_list p_list(lower, upper);prime = p_list.get_first_prime();while (prime){
cout << prime << endl;
prime = p_list.get_next_prime();}return 0;}.................................................................................
Example: the same example that we gave for primelist function for SINGULAR (note that in this time list is from smaller prime to bigger:.................................................................................
Please enter the lower bound: 45353109

ciii

Please enter the upper bound: 45353264
45353111
45353149
4535317345353183
4535320145353207
45353237.................................................................................

.................................................................................
int isdivisible( unsigned long N){
unsigned longp;prime_list pl(2, 10000000);for(p = pl.get_first_prime();p<1000000;p=pl.get_next_prime){
if (N%p==0) return(0);else return(1);}}#include <LiDIA/prime_list.h>#include <iostream>using namespace LiDIA;
using namespace std;
int main(){unsigned long N;
cout<<"enter the possible prime <10^14"<< N; cin>>N;
cout<<endl;
cout<<isdivisible(N)<<endl;
return 0;}

civ

.................................................................................

.................................................................................
//This example programme computes Legendre-Jacobi symbol//as in the SINGULAR...
//exaple written by Osmanbey Uzunkol..
#include <LiDIA/bigint.h>#include <iostream>using namespace LiDIA;
using namespace std;
int main(){//In this programme we will compute//Jacobi/Legendre symbol of (a/n)
bigint a,N;
cout<<"Please enter the value of a: "; cin>>a;
cout<<"Please enter the value of N: "; cin>>N;
int i=jacobi(a,N);
cout<<"The Jacobi(Legendre)-symbol is: "<<i<<endl;
return(0);}.................................................................................
Example: As in the case of singular, three cases of Jacobi-symbol will be given
as examples:.................................................................................
please enter the value of a: 7176672728939384494949948949
please enter the value of n: 82272666155561551666616617177100101
The Jacobi(Legendre)-symbol is: 1.................................................................................

.................................................................................

cv

please enter the value of a: 6546647437473783882871
please enter the value of n: 6161652526626616117711172782271
The Jacobi(Legendre)-symbol is: -1.................................................................................

.................................................................................
please enter the value of a: 10786846916586309307182037205410965
please enter the value of n: 100000000181152552587186285254317809165567093021
The Jacobi(Legendre)-symbol is: 0.................................................................................

.................................................................................
//The source code of fermattest of LiDIA will be given in this programme//example file written by Osmanbey Uzunkol..
#include <LiDIA/bigint.h>#include <iostream>using namespace LiDIA;
using namespace std;
int fermattest(const bigint & n){bigint tmp_a, tmp_n, res;register int a = 2;
if (n < 2)
return 0;
if ((n == 2) || (n == 3) || (n == 5) || (n == 7))
return 1;
tmp_n.assign(n);dec(tmp_n);while (a <= 7) {cvi

if (!remainder(n, a))return 0;
else {
tmp_a.assign(a);power_mod(res, tmp_a, tmp_n, n);if (!res.is_one())
return 0;
else {
if (a == 2)
a += 1;else
a += 2;}}}
return 1;}
int main(){bigint N;
cout<<"please enter the prime candidate N : "; cin>>N;
cout<<endl;
if(fermattest(N)) cout<<N<<" is (probably) prime"<<endl;
else cout<<N<<" is a composite number"<<endl;
return 0;}.................................................................................
Example: The following two examples will show composite and (probable) prime
cases, respectively.................................................................................
please enter the prime cadidate N: 4343552525663633554245226366366355351

cvii4343552525663633554245226366366355351 is a composite number.................................................................................

.................................................................................
please enter the prime cadidate N: 2543015553938550490663
2543015553938550490663 is a (probably) prime.................................................................................

.................................................................................
//The source code of fermattest of LiDIA will be given in this programme//example file written by Osmanbey Uzunkol..
#include <LiDIA/bigint.h>#include <iostream>using namespace LiDIA;
using namespace std;bool
bigint::is_prime (const int b1) const{
static long a[10] = {3, 5, 7, 11, 13, 17, 19, 23, 29, 31};long b, j, ok, i, k = 0, sx;
if (!longify(sx)) {// can not be converted to longif (sx <= 0)
return false;
if (sx == 2)
return true;
if (sx <= 31) {for (i = 0; i < 10; i++)if (sx == a[i])return true;cviii

return false;}}
if (is_le_zero() || is_even())
return false;
if (b1 <= 0)lidia_error_handler("is_prime", "#tests <= 0");if (b1 > 9)
b = 9;else
b = b1;bigint erg;
bigint H(37), Q(*this);Q.dec();
bigint N_minus1(Q);while (Q.is_even()) {Q.divide_by_2();k++;}for (i = 0; i <= b; i++) {power_mod(erg, bigint(a[i]), Q, *this);if (!erg.is_one() && erg.compare(N_minus1)) {j = k;cixok = 0;while ((j > 0) && !ok) {square(erg, erg);
remainder(erg, erg, *this);if (!erg.compare(N_minus1)) ok = 1;
j--;}if (!ok) {return false;}}}for (; i <= b1; i++) {if (!compare(H))
return true;
power_mod(erg, H, Q, *this);if (!erg.is_one() && erg.compare(N_minus1)) {j = k;
ok = 0;while ((j > 0) && !ok) {square(erg, erg);
remainder(erg, erg, *this);if (!erg.compare(N_minus1)) ok = 1;

cx

j--;
}
if (!ok) {return false;}}
H = H.next_prime();}return true;}

int main(){bigint N;
cout<<"Please enter the prime cadidate :"; cin>>N;
if (is_prime(N,10))cout<<N<<" is (probable) prime"<<endl;
else
cout<<N<<" is composite"<<endl;
return 0;}.................................................................................

.................................................................................
please enter the prime cadidate :6636536366366363636555626266263101
6636536366366363636555626266263101 is composite.................................................................................

cxi

.................................................................................
please enter the prime cadidate: 449017159180743482307697943
449017159180743482307697943 is (probable) prime.................................................................................

.................................................................................
//A factorization example for use in N-1 or N+1//tests when we can factorize the intger fully.
//Note that there are other factorizetion functions that//enable us to test the primality of N if the//partial factorization is available for N-1 or N+1.
#include <LiDIA/rational_factorization.h>#include <iostream>using namespace LiDIA;
using namespace std;
int main(){rational_factorization f;
bigint n;cout << "\n Please enter a number: ";cin >> n;f.assign(n);f.factor();if (f.is_prime_factorization())
cout<<"\n Prime Factorization: " << f << endl;
else
cout<<"\n Factorization: "<< f << endl;
return 0;}.................................................................................
Example: an example of prime factorization of integer N in the form (pi , ei )cxii

whereN=kYpei i where p0i s are prime;i=1.................................................................................
Please enter a number: 722373666447774889299438843747747773738
Prime Factorization: [(2,1),(137,1),(281,1),(4787,1),(393373,1),(5327244139616992287109027,1)].................................................................................
We will see the Cornacchia algorithms written in the bigint class of LiDIA due
to the pseudocode (Modified Cornacchia’s algorithms) that we gave in chapter 2.

.................................................................................
bool cornacchia (bigint & x, bigint & y, const bigint & DD, const bigint & p){
bigint x0, a, b, l, r;
bigint D, tmp2, D_abs, p_four;bigint rr;
bool r_is_sqr;
long s;if (!DD.is_negative())
lidia_error_handler("cornacchia", "D not negative");s = (4 - (DD.least_significant_digit() & 3)) & 3; // DD mod 4
shift_left(p_four, p, 2);
D.assign(DD);
if (!is_prime(p) || !p.is_positive() || p == 2)
lidia_error_handler("cornacchia", "no odd prime number");if ((-D) >= p_four)cxiii

lidia_error_handler("cornacchia", "|D| >= 4*p");if (s != 1 && s != 0)
lidia_error_handler("cornacchia", "D != 0 or 1 mod 4");
if (jacobi(D, p) == -1) {return false; // (D/p) = -1 -->no solution}
else {
ressol(x0, p+D, p);
if (x0.is_even() != D.is_even())
subtract(x0, p, x0);
shift_left(a, p, 1);b.assign(x0);shift_left(l, p, 2);
sqrt(l, l); // l = floor(2*sqrt(p)) = floor(sqrt(4p))
while (b > l) {remainder(r, a, b);a.assign(b);b.assign(r);}square(l, b);
subtract(a, p_four, l);// a = 4p - b^2 now
D.negate();remainder(r, a, D);cxiv

if (!r.is_zero()) {return false;}
else {
divide(r, a, D);
r_is_sqr = is_square (rr, r);if (!r_is_sqr) {return false;}
else {
x.assign(b);y.assign(rr);return true;}}}}.................................................................................
Now at the end, we will use the primeproof class (see for more details [30] and[20]) to write down an example file in C++ and give examples of N − 1, N + 1
and ECPP algorithms;.................................................................................
#include <iostream>#include <LiDIA/bigint.h>#include <LiDIA/prime_proof.h>#include <LiDIA/certificate.h>using namespace LiDIA;
using namespace std;
int main(){cxv

bigint N;
cout << "Please enter the prime candidate : ";cin >>N;
prime_proof proof;
certificate c;proof.set_verbose(true);
proof.set_ecpp_mode(1);proof.set_prime(N);bool success = proof.prove_prime();if(success)cout<<N<<" is prime"<<endl;
else cout<<N<<" is not prime"<<endl;
return 0;}.................................................................................
Examples:.................................................................................
Please enter the prime candidate : 2142973051
Primelength:10
Make the SPP test
SPP: n-1=2^l*q, l: 1 q: 1071486525
SPP: Test was succesful
2142973051 is prime.................................................................................

.................................................................................
Please enter the prime candidate : 138934276198614100615367165789108366819377188
1773889298737782991998387756530022001881727277301776266377277271
Primelength:109
13893427619861410061536716578910836681937718817738892987377829919983877565300220

cxvi

01881727277301776266377277271 is not prime.................................................................................

.................................................................................
Please enter the prime candidate : 614367291872088173452017745619376378920198837
62567829919982778299100166355178390100988277164520918846551729001987262661567188
17272663781899199882772891991000093838829928839928882999288891977177188818881177
11000118811717
Primelength:219
61436729187208817345201774561937637892019883762567829919982778299100166355178390
10098827716452091884655172900198726266156718817272663781899199882772891991000093
83882992883992888299928889197717718881888117711000118811717 is not prime.................................................................................
We will finish this section by giving a primality proof by using ECPP inan easy to understand form due to [7]. Note that it is easy to verify and get
certificate by means of intermediate datas below;.................................................................................
1267650600228229401496703205653
169317673849406496638751929789

535428649309014131591402355077

1223116517107234371890879608558

348818700976692547697219665601

1267650600228230776357544186344
1764763222984205716110037______________________________________
1764763222984205716110037
1237106009019141934754397

824737339346094623169598

498566265383685655850376

1698160958763013389415626

1764763222981587729747968
21321838780409719______________________________________

cxvii

21321838780409719
5979072666605065

11093328037873283

12289991207526417

5086330291908954

21321839059327264
636820759.................................................................................
Using DOWN-RUN, we got the number 636820759. By calling the primelist
function, we can easily see that this number is prime by means of trial division. Hence, we proved the primality of 1267650600228229401496703205653 byreducing the primality of it to the prime 636820759.

7.2

Conclusion

The aim of this thesis was to introduce modern primality testing methods andto explain the so-called Atkin’s ECPP Algorithm. Most of the primality tests
were covered by means of explaining the necessary theoretical background comingfrom algebra, number theory and arithmetic of elliptic curves and by means of
introducing the methods in an algorithmic approach. Furthermore, we introduced
intensively the computational problems and solutions coming together with thetheory of elliptic curves, in particular curves with CM. Additionally, approaches
to make the ECPP algorithm more practical were also discussed. At the endof thesis, several programming examples of primality tests are given together
with the examples of Atkin’s ECPP in computer algebra system SINGULAR andprogramming language C++, with the help of using LiDIA computer package forcomputational number theory.

cxviiireferencescxix

references[1] H. Cohen, A Course in Computational Algebraic Number Theory, SpringerVerlag, Second corrected Printing, 1995,[2] A.J.Menezes, P.C. van Oorschot, S.A. Vanstone. Kornberg, Handbook of Applied Cryptography, CRC Press, 1996,[3] J. Buchmann, Einführung in die Kryptographie, Springer-Verlag, 1999,[4] M. O. Rabin, Probabilistic Primality Testing, J. Number Theory, 12(1980)
128-138,[5] J. Silverman, Advanced topics in the arithmetic of Elliptic Curves, SpringerVerlag, 1994,[6] J. Silverman, The Arithmetic of Elliptic Curves, Springer-Verlag, 1986,[7] I. Blake, G. Seroussi, N. Smart, Elliptic Curves in Cryptography, Cambridge
University Press, 1999,[8] N. Koblitz, A Course in Number Theory and Cryptography, Springer-Verlag,
1987,[9] S. Goldwasser, J. Kilian, Primality Testing Using Elliptic Curves,[10] L. M. Adleman, C. Pomerance, R. Rumely On distinguishing prime numbers
from composite numbers, Ann. Math. 117, 173-206,[11] A. O. L. Atkin, F. Morain, Elliptic curves and Primality Proving, Math.
Comp. , 61, 29-67, 1993,[12] M.Agraval, N.Kayal, N.Sexana, Primes is in P, paper August 2002,[13] D. Cox, Primes of the form x2 + ny 2 , John Wiley and Sons, 1989,cxx

[14] H. Cohen, A. K. Lenstra Implementation of a new primality test, Math.
Comp. 48, 177(1987), 103-121,[15] S. Galbraith, J. McKee, The probability that the number of points on an
elliptic curve over a finite field is prime, Journal of the London MathematicalSociety, 62, no. 3, pg. 671-684, 2000,[16] Geometrische Methoden in der Kryptographie, Vorlesungsskript TUKaiserslautern, SS 2003,[17] Primzahltests and Kryptographie I-II, Vorlesungsskript TU-Kaiserslautern,
WS 2003-2004 and SS 2003,[18] Algebraische Geometrie I, Vorlesungsskript TU-Kaiserslautern, WS 20022003,[19] F. Morain, Building cyclic elliptic curves modulo large primes, Eurocrypt’91,
pg. 531-543,[20] LIDIA C++ library for computational number Theory, www.informatik.tudarmstadt.de/TI/LiDIA /Wellcome.html,[21] S. B. Lippman, C++ Primer, 2.Edition, Addison-Wesley,[22] G.-M. Greuel, G. Pfister, H. Schoenemann A Computer Algebra System for
Polynomial Computations, FB Mathematik TU-Kaiserslautern,[23] M. Welschenbach, Kryptographie in C und C++, 2. Auflage, Springer-Verlag,[24] S. Goldwasser, J. Kilian, almost all primes can be quickly certified, in 18th
Annual Symposium on Foundations of Computer Science, IEEE, pg. 316-329,
Berkeley, California, May 1986,[25] L. M. Adleman, M. A. Huang Recognizing primes in random polynomial
time, in Proceedings 19th STOC(1986) ACM Press, pg. 462-469, New-york
City, May 25-27, 1987,

cxxi

[26] E. R. Berlekamp, Factoring polynomials over large finite fields, Math. Comp.
24, 111 (1970), 713-735,[27] W. Bosma, Primality testing using elliptic curves, Tech. Rep. 85-12, Math.
Instituut, Universiteit van Amsterdam, 1985,[28] P. Mihailescu, F. Morain, Dual elliptic primes and Cyclotomy primality proving,[29] N. D. Elkies, Elliptic and modular curves over finite fields and related computational issues, in Computational perspectives on Number Theory: Proceedings of a Conference in honor of A. O. L. Atkin, American MathematicalSociety International Press, 7, 1998,[30] J. Hechler, Primzahlnachweis mit Hilfe elliptischer Kurven, Diplomarbeit,
Okt. 2003 TU-Darmstadt,[31] H. W. Lenstra, JR. Elliptic curves and number theoretic algorithms, Trch.
Rep. Report 86-19 , Math.Inst., Univ. Amsterdam, 1986,[32] H. Cohen,H. W. Lenstra, Primality testing and Jacobi sums, Math. comp.
42, 165(1984), 297-330,[33] A. K. Lenstra, H. W. Lenstra, JR. Algorithms in number theoty, In Handbook of Theoretical Computer Science, J. van Leeuwen, Ed. vol. A: Algorithms and Complexity. North Holland, 1990, ch. 12, pp. 674-715,[34] K. Ireland, M. Rosen, A classical introduction to modern number theory, vol.
84 of Graduate texts in Mathematics, Springer, 1982,[35] F. Morain, Elliptic curves, primality proving and some titanic primes, 1989,(1992),[36] F. Morain, J. Olivos Speeding up the computations on an elliptic curve using
addition-substraction chain, Info. Theory Appl. 24, 531-543, 1990,[37] W. E. Clark, J. J. Liang On arithmetic weight for a general radics representation of integers, IEEE Trans. Info. Theory, 19, 823-826, 1973,

cxxii

[38] C. H. van Lint, Introduction to Coding Theory, Springer-Verlag, 1982,[39] G. Reitwiesner, Binary Arithmetic, Adv. in Comp., 1, 231-308, 1960,[40] P. Ribenboim, The book of prime number records, Third edition Springer
1995,[41] R. P. Brent, Some integer factorization using elliptic curves, Australian Computer Science Communications 8(1986), 149-163,[42] P. L. Montgomery, Speeding the Pollard and elliptic curve methods of factorization, Math. Comp. 48, 177 (January 1987), 243-264,[43] A. O. J. McKee, Subtleties in the distribution of the numbers of points on
elliptic curves over a finite field, J. LMS,
[44] C. Pomerence, Very short primality proofs, Math. Comp. 48, 177 (1987),
315-322,[45] V. R. Pratt, Every prime has sufficient certificate, SIAM J. Comput. 4(1975), 214-220,[46] Einführung in die Computer Algebra, Vorlesungsskript WS 2002-2003,[47] F. Morain , Distributed primality proving and the primality of (23539 + 1)/3,
In Advanced Cryptology - EUROCRYPT’90 (1991), I. B. Demgard, Ed., vol.
473 of Lect. Notes in Computer Science, Springer-Verlag, pp. 110-123. Proceedings of the Workshop on the Theory and Application of Cryptographic
Techniques, Aarhus, Denmark, May 21-24, 1990,[48] O. Atkin The number of points on an elliptic curve modulo a prime,
manuscript (1991),[49] T. Oetiker, H. Partl, I. Hyna, E. Schlegl, A not very short Introduction to
LATeX, Version 1.0, November 16, 1994.

cxxiii