Date: Fri, 30 Sep 1994 09:22:31 EDT
Reply-To: Francois Morain <morain@polytechnique.fr>
Sender: Number Theory List <NMBRTHRY@NDSUVM1.BITNET>
From: Francois Morain <morain@polytechnique.fr>
Subject: #E(GF(2^300))
Let GF(2^300) be given as GF(2)[T]/P(T) with P(T) = T^300+T^5+1 and
a6 = T^16+T^14+T^13+T^9+T^8+T^7+T^6+T^5+T^4+T^3,
(which is 91128 -- our zip code -- expressed in binary and converted
as a polynomial in T).
The number of points on
Y^2+X*Y=X^3+a6
is
2^300+1-t = 2^7 * 5 * 1201 * 1277 * 1520155019
* 4643247953815878517507728948119
* 294018777025731748070255411191436938897883.
All the computations were done on a DEC 3000 alpha (240 OSF1 V2.0).
Finding the possible t mod l took 789397 seconds (or 9 days 4h 47 min).
The match-sort phase took 5500 seconds.
This computation was made possible by the implementation of
Couveignes's algorithm for computing factors of division
polynomials in small characteristic. This is the first interesting
result obtained with it and not the last one, since we are currently
trying to optimize many parts of the algorithm (e.g., using powers of
small primes, etc.). More details will be given in a preprint that
will be available in a near future.
R. Lercier and F. Morain
Technical appendix
-------------------
The first column contains the prime l, the second the power of l used,
the third the type of prime (Elkies or Atkin or done with Schoof's
basic algorithm). The fourth one is computing X^q mod Phi, the last
one the total time for that prime.
l | d | T | X^q | Tot |
===============================
2 |10 | E | - |31053. |
-------------------------------
3 | 1 | S | - |4.6672 |
-------------------------------
5 | 1 | S | - |21.180 |
-------------------------------
7 | 1 | S | - |56.878 |
-------------------------------
11 | 1 | S | - |1084.5 |
-------------------------------
13 | 1 | S | - |2133.4 |
-------------------------------
17 | 1 | S | - |8893.7 |
-------------------------------
19 | 1 | E | 21.79 |293.41 |
-------------------------------
23 | 1 | A | 21.95 |89.263 |
-------------------------------
29 | 1 | A | 82.57 |251.19 |
-------------------------------
31 | 1 | E | 97.17 |439.59 |
-------------------------------
37 | 1 | E | 100.2 |646.24 |
-------------------------------
41 | 1 | E | 275.1 |2214.6 |
-------------------------------
43 | 1 | A | 101.1 |1136.5 |
-------------------------------
47 | 1 | E | 132.5 |1555.6 |
-------------------------------
53 | 1 | A | 286.7 |2629.1 |
-------------------------------
59 | 1 | E | 258.1 |5095.4 |
-------------------------------
61 | 1 | E | 533.0 |11458. |
-------------------------------
67 | 1 | E | 974.1 |28620. |
-------------------------------
71 | 1 | A | 379.3 |6966.1 |
-------------------------------
73 | 1 | A | 453.7 |457.59 |
-------------------------------
79 | 1 | E | 689.5 |195666 |
-------------------------------
83 | 1 | A | 807.4 |5764.4 |
-------------------------------
89 | 1 | A | 849.8 |13019. |
-------------------------------
97 | 1 | E | 1053. |76501. |
-------------------------------
101 | 1 | E | 1713. |65768. |
-------------------------------
103 | 1 | E | 2247. |302535 |
-------------------------------
107 | 1 |EA | 2832. |2832.8 |
-------------------------------
109 | 1 | A | 1974. |22206. |
-------------------------------
Tot | | |15886. |789397 |
-------------------------------