```Date: Fri, 30 Sep 1994 09:22:31 EDT Reply-To: Francois Morain Sender: Number Theory List From: Francois Morain 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 | ------------------------------- ```