Suppose we are given a natural number n. Then Fermat's test asserts that if there is a natural number a (with (a, n) = 1) satisfying

(1)

[

Memoirs of the College of EducatiOn]

Akita University (Natural Science) 40,5-8 (1989)

An Elliptic Fermat Test

Hideji lTo

(Received Semptember

9, 1988) Introduction

Suppose we are given a natural number n. Then Fermat's test asserts that if there is a natural number a (with (a, n) = 1) satisfying

an~l "¥=

1 (mod n), then n is composite.

Although this is quite elementary, we can interpret this fact as follows in algebraic number theory. Let £, p be rational primes, t, a primitive £-th root of unity. Then the degree of p in the field extension Q

(t,) /

Q divides

£~1,

and we can calculate f as the smallest natural number satisfying pf == 1 (mod £).

Now, replace cyclotomic fields with the division fields of elliptic curves defined over Q.

By the arithmetic of such fields, we obtain a similar composite test. As in the classical case, this allows us to introduce a new kind of pseudoprimes. We calculated them to several bases up to 10

⁷^•

For example, to the base (2,1), that is, with respect to the elliptic curves defined over Z/2Z having 1 as the trace of Frobenius endomorphism, the smallest new pseudoprime is 30889 and there are only 28 of them below 10

⁷^•

In the same range, the number of (Fermat) pseudoprimes to the base 2 is 750 (see [4J). SO, it seems important to pursue our line of investigation.

1.

An

elliptic Fermat test

Let E be an elliptic curve defined over Q (we assume E(Q) * ^1». For a rational prime £, put E, = {PEE

I

£P =

O},

K, = Q (E,), i. e., the number field over Q generated by all the coordinates of the points in E,. Since E, is isomorphic to Z/£Z EB Z/£Z, the extension K,/Q is galois and there is an injective homomorphism Gal (K,/Q)

^--->-

GL

2

(Z/£Z). By a theorem of Serre, if E has no complex multiplication then this injection is an isomorphism except for finitely many primes £ ( [8J ,p.95).

Let p be a rational prime which is good for

E.

put Npm = # (E mod p) (Fpm) and apm = tr

^(n"'),

where Fpm is the finite field extension of Z/pZ with pm elements,

^7[

is the p-th power endomorphism of E mod p and trace is taken with respect to the

£~adic

representation 1>, of E mod p. Then Npm = l-apm + pm. As

7[

can be identified with an imaginary quadratic irrational number satisfying

x

² ~

apx + p = 0,

- 5 -

Akita University

(2)

Q (Jr),

an {a

p'}

is a Lucas sequence of type (a

p ,

pl. So it is easy to calculate N

p "

Put k

imaginary quadratic number field,and let f be the degree of p in

KdQ.

THEOREM. Suppose Q J ((a

p)2 -

4p).

( i )

If

Q

splits in k, then f

I(Q - 1).

( ii )

If

Q

remains prime in k, then f I

(Q2 - 1).

COROLLARY.

( i ) If Q splits in k, then Q2

I

Np'-'.

(ii)

If Qremains prime in k, then Q2

I

N

p'·-'.

Assume furthermore that Q

I

Np" Then we have Q2

I

N

p "

PROOF. These are essentially contained in our previous more precise result ( [lJ , Theorem

1).

One has only to note that (R/QR)X is isomorphic to (Z/QZr

^X

(Z/QZ)X in case ( i ), and in case

(ii),

(R/QR)X is a cyclic group of order

Q2-1,

where R = End

z/pz

(E mod pl.

(See also [ZJ ,Proposition Z.)

If

p remains prime in k, then the two eigen values of

<Pf(Jr)

(mod Q) are conjugate to each other over Z/

QZ.

From this, one can derive the rest of our assertion.

(Q.E.D.)

Now, start from a rational prime p. The isogeny classes of elliptic curves over Z/pZ correspond in one-to-one manner with the numbers a

E

Z,

I

a

I

< zIP. And we can lift any elliptic curve over Z/pZ to an elliptic curve E over

Q,

so that p is a good prime for E.

So by our theorem we can define a new kind of pseudoprimes as follows.

DEFINITION. An odd composite number L is called an elliptic pseudoprime to the base (p, a), where p is a prime and a

E

Z satisfies °

^~

^a ^< ^zIP, if it satisfies one of the following two conditions. Put d = 4p-a

²

>

0,

and denote by (-) the Jacobi symbol.

( i)

If (

~d ^{) =}

^1,

^then

^{U I}

NpH and pL-I

=" 1

(mod L).

(ii)If (

~d ) = -I, then

U I

Np"-' and pL-I

="

1 (mod L).

In case ( i ), we will call L of split type, and in case (

ii),

we will call L of remain prime type.

Since

K_f

contains

Q((f),

we think it natural to include usual Fermat condition pL-I

="

1 (mod L) in our definition. Also, we need only nonnegative values of a, because we require L to be odd (so a and -a give the same value of Np'-'). Recall that an odd composite number N is called a (Fermat) pseudoprime to the base a, if it satisfies a

^N^-

I

_=" ₁

(mod N). Hence by our definition, elliptic pseudoprimes constitute a part of (Fermat) pseudoprimes. We calculated them up to

10⁷

to the base

(Z, *),(3, *)

which will be described in the next section. From them we observe that if the elliptic curve E' corresponding to (p, a) is supersingular then pseudoprimes to the base (p, a) are abundant in number, whereas if E' is ordinary then there are not many of them. Following proposition explains a part of this phenomenon. (By abuse of notation, we sometimes write Np' = Nmand ap' = am.)

PROPOSITION

1.

Suppose L is a (Fermat) pseudoprime to the base p. Then to the base (p, OJ, we have

U I

NL'-l (So, if L also satisfies ( ~p ⁾

⁼

^-1, then L is an elliptic pseudoprime to the base (P, 0) of remain prime type.)

PROOF. By a recurtion formula an+l = alan - pan-I, we have an+l= -pan-I. (Cf. [5J ,p. 44 IV.

- 6 -

Akita University

(3)

1.In the notation there, Vn⁼ an, P = ai, Q = p.) So a2n = (-1)"2 pn, a2n =

O.

Hence we have N2n ⁼ ^{(1 -} (_1)npn)2 (*).

Since pL-1

==

1 (mod L), we see pIL'-I)/2

==

1 (mod L). So by (*) we get our assertion. (Q.E.D.) Naturally, there arise many questions about elliptic pseudoprimes and related matters (in an analogous way as described in [5J ). For example, are there infinitely many of them (for a single base, or. .. )? Can one define appropriate "strong" elliptic pseudoprimes? We hope some of these problems will be treated in our future papers.

Finally, as an another example to show the analogy between cyclotomic fields and division fields of elliptic curves, we will show the next proposition.

PROPOSITION 2.

Notations being the same as before, let q be a rational prime and let

£

be an odd prime factor of

(NdNp).

Suppose

£

J

((ap)2 - 4p)

and

£

J

(pq - 1).

Then we have

£ =-= 1 (mod q).

PROOF. We may assume that the endomorphism ring of

E'

is of maximal order. So, if £2 I Np" thenE' CFpq) cannot contain all of the points of order £ (otherwise, it means £ I(pq - 1), contrary to the assumption). Hence ¢£ (7l") mod £ is conjugate to

(6 ^~),

^a ⁼¹⁼ ^1. ^Hence

£ must split in k.If£2

J

Np', then by the Corollary, we have the same conclusion. So q divides

£ - 1.(See [lJ, Theorem 1.) (Q.E.D.)

An analogous statement with respect toQ(tp)is as follows. Put Mn⁼ pn - 1. For example, when n = 2, this is a Mersenne number. Let q be a prime, £ an odd prime.If£ divides

Mql

Mland £

J

(p - 1), then we have £

==

1 (mod q). So, it is interesting to consider factoring of Npm. Indeed, N. Koblitz recently raised the question of primality of

Np'/N p (

[3J ).

2. Examples

We made our calculations using muMATH-83 (Soft Warehouse, Honolulu) on several personal computers (mainlyPC9801~VX(NEC) and PC-286V (Epson)).

In the following, to each base we denote by NI (respectively, N2) the number of elliptic pseudoprimes of split type (respectively, of remain prime type) less than 10⁷^,and we put N

= NI

+

N2.

(1)Base (2,0). We have NI = 310, N2 = 285. So, N= 595. The next proposition shows the infinitude of elliptic pseudoprimes of remain prime type to the base (2, 0).

PROPOSITION 3.

If n

is

a (Fermat) pseudoprime, then

2n - I is

an elliptic pseudoprime of remain prime type to the base

(2, 0).

PROOF. As is well known, if n is a (Fermat) pseudoprime to the base 2, then 2n - 1 is also a pseudoprime to the base 2 ( [5J p. 87, [7J p. 154). Clearly 2n - 1 (n ~ 3) is of remain prime type inQ(.;=2). Hence, by Proposition 1 we get our assertion. (Q.E.D.)

(2) Base (2, 1).Nl = 22, N2 = 6, N = 28.

(3) Base (2, 2). N 1 = 334, N2 = 105, N = 439.

We will explicitly write down the 10 numbers(;;:;; 10⁷⁾which pass elliptic Fermat tests to allofthebases(2,a)(0;;:;; a;;:;; 2): 1152271, 1306801, 1357441,2213121,3057601,3581761, 5444489, 5632705, 5968873, 8134561.

(4) Base (3, 0). Nl = 377, N2 = 96, N = 473.

(5) Base (3,1). Nl = 19, N2 = 11,N = 30.

- 7

Akita University

(4)

(6) Base (3, 2). Nl = 24, N2 = 3, N = 27.

(7) Base (3, 3). Nl = 377, N2 = 96, N = 473.

The following four numbers alone pass elliptic Fermat tests to all of the bases (3, a) (0

~

a

~

3): 1541, 1615681,4767841,9582145. Above 10 numbers or these 4 numbers may be called elliptic pseudoprimes to the base 2 or 3. As is noted in Introduction, their number is very small compared with that of (Fermat) pseudoprimes or strong pseudoprimes. (Of course, above results show that there is no number which is simultaneously elliptic pseudoprime to all of the bases (2,

*),

(3,

*)

below 10

⁷^.)

We add two more observations. ( i ) The ratio N2: Nl is always rather small compared with that of prime numbers.

(ii)

There are (Fermat) pseudoprimes to the base 2 which are not elliptic pseudoprime to any base (2,

*).

Their number is 117 (in tme range

~

10

⁷^).

We write down first five such numbers: 4369, 11305, 18721,23001,23377. To the base 3, there are 256 such (Fermat) pseudoprimes.

References

[ 1 ] H. ito, A Note on the Law of Decomposition of Primes in Certain Galois Extension, Proc. Japan Acad., 53A (1977),115-118.

[2] H. ito, A Reciprocity Law in Some Relative Quadratic Extensions, Proc. Japa Acad., 56A (1980), 40-44.

[3] N. Koblitz, Primality of the number of points on an elliptic curve over a finite field, Pacific

J..

131 (1988), 157-165.

[ 4 ] C. Pomerance, J.

L.

Selfridge, S. S. Wagstaff, J

L,

The pseudoprimes to 25 • 10

⁹^,

Math.

Comp., 35 (1980), 1003-1026.

[5] P. Ribenboim, The Book of Prime Number Records, Springer-Verlag, New York- Berlin-Heidelberg-London-Paris-Tokyo, 1988.

[6] H. Riesel, Prime Numbers and Computer Methods for Factorization, Birkhauser, Boston, 1985.

[7]

K.

H. Rosen, Elementary Number Theory and its Applications, Addison-Wesley, Reading, 1984.

[8] J. H. Silverman, The Arithmetic of Elliptic Curves, Springer-Verlag, New York- Berlin-Heidelberg-Tokyo, 1986.

DEP ARTMENT OF MA THEMATICS AKITA UNIVERSITY

AKIT A,JAP AN

Suppose we are given a natural number n. Then Fermat's test asserts that if there is a natural number a (with (a, n) = 1) satisfying

An Elliptic Fermat Test

Hideji lTo

(Received Semptember

Suppose we are given a natural number n. Then Fermat's test asserts that if there is a natural number a (with (a, n) = 1) satisfying

1 (mod n), then n is composite.

Although this is quite elementary, we can interpret this fact as follows in algebraic number theory. Let £, p be rational primes, t, a primitive £-th root of unity. Then the degree of p in the field extension Q

Q divides

and we can calculate f as the smallest natural number satisfying pf == 1 (mod £).

Now, replace cyclotomic fields with the division fields of elliptic curves defined over Q.

By the arithmetic of such fields, we obtain a similar composite test. As in the classical case, this allows us to introduce a new kind of pseudoprimes. We calculated them to several bases up to 10

For example, to the base (2,1), that is, with respect to the elliptic curves defined over Z/2Z having 1 as the trace of Frobenius endomorphism, the smallest new pseudoprime is 30889 and there are only 28 of them below 10

In the same range, the number of (Fermat) pseudoprimes to the base 2 is 750 (see [4J). SO, it seems important to pursue our line of investigation.

An

Let E be an elliptic curve defined over Q (we assume E(Q) * 1». For a rational prime £, put E, = {PEE

£P =

K, = Q (E,), i. e., the number field over Q generated by all the coordinates of the points in E,. Since E, is isomorphic to Z/£Z EB Z/£Z, the extension K,/Q is galois and there is an injective homomorphism Gal (K,/Q)

GL

(Z/£Z). By a theorem of Serre, if E has no complex multiplication then this injection is an isomorphism except for finitely many primes £ ( [8J ,p.95).

Let p be a rational prime which is good for

put Npm = # (E mod p) (Fpm) and apm = tr

where Fpm is the finite field extension of Z/pZ with pm elements,

is the p-th power endomorphism of E mod p and trace is taken with respect to the

representation 1>, of E mod p. Then Npm = l-apm + pm. As

can be identified with an imaginary quadratic irrational number satisfying

x

apx + p = 0,

- 5 -

Akita University

an {a

is a Lucas sequence of type (a

pl. So it is easy to calculate N

Put k

imaginary quadratic number field,and let f be the degree of p in

THEOREM. Suppose Q J ((a

4p).

If

splits in k, then f

If

remains prime in k, then f I

COROLLARY.

( i ) If Q splits in k, then Q2

Np'-'.

If Qremains prime in k, then Q2

N

Assume furthermore that Q

Np" Then we have Q2

N

PROOF. These are essentially contained in our previous more precise result ( [lJ , Theorem

One has only to note that (R/QR)X is isomorphic to (Z/QZr

(Z/QZ)X in case ( i ), and in case

(R/QR)X is a cyclic group of order

where R = End

(E mod pl.

(See also [ZJ ,Proposition Z.)

p remains prime in k, then the two eigen values of

(mod Q) are conjugate to each other over Z/

From this, one can derive the rest of our assertion.

Now, start from a rational prime p. The isogeny classes of elliptic curves over Z/pZ correspond in one-to-one manner with the numbers a

Z,

a

< zIP. And we can lift any elliptic curve over Z/pZ to an elliptic curve E over

so that p is a good prime for E.

So by our theorem we can define a new kind of pseudoprimes as follows.

DEFINITION. An odd composite number L is called an elliptic pseudoprime to the base (p, a), where p is a prime and a

Z satisfies °

a < zIP, if it satisfies one of the following two conditions. Put d = 4p-a

>

and denote by (-) the Jacobi symbol.

( i)

~d ) =

then

NpH and pL-I

(mod L).

~d ) = -I, then

Np"-' and pL-I

1 (mod L).

In case ( i ), we will call L of split type, and in case (

we will call L of remain prime type.

Since

Let E be an elliptic curve defined over Q (we assume E(Q) * ^1». For a rational prime £, put E, = {PEE

^a ^< ^zIP, if it satisfies one of the following two conditions. Put d = 4p-a

~d ^{) =}

^then

NL'-l (So, if L also satisfies ( ~p ⁾

^-1, then L is an elliptic pseudoprime to the base (P, 0) of remain prime type.)

(6 ^~),