1/************************************************************** 2 * 3 * curvegen.c 4 * 5 * CM curve generator. 6 * 7 * Compile with: 8 * 9 * % cc -O curvegen.c tools.c giants.c ellproj.c -lm -o curvegen 10 * 11 * Updates: 12 * 27 Sep 98 REC - Creation 13 * 14 * 15 * c. 1998 Perfectly Scientific, Inc. 16 * All Rights Reserved. 17 * 18 * 19 *************************************************************/ 20 21/* include files */ 22 23#include <stdio.h> 24#include <math.h> 25#include <stdlib.h> 26#include <time.h> 27#ifdef _WIN32 28 29#include <process.h> 30 31#endif 32 33#include <string.h> 34#include "giants.h" 35#include "tools.h" 36 37#define DCOUNT 27 38 39int disc12[DCOUNT] = {-3, -4, -7, -8, -11, -19, -43, -67, -163, -15, -20, -24, -35, -40, -51, -52, -88, -91, -115, -123, -148, -187, -232, -235, -267, -403, -427}; /* All discriminants of class number 1,2. */ 40 41/************************************************************** 42 * 43 * Main Function 44 * 45 **************************************************************/ 46 47#define CM_SHORTS 4096 48 49main(int argc, char **argv) { 50 giant p = newgiant(CM_SHORTS); 51 giant u = newgiant(CM_SHORTS); 52 giant v = newgiant(CM_SHORTS); 53 giant g[6]; 54 giant plus_order = newgiant(CM_SHORTS); 55 giant minus_order = newgiant(CM_SHORTS); 56 giant a = newgiant(CM_SHORTS); 57 giant b = newgiant(CM_SHORTS); 58 int d, dc, olen, k; 59 60 init_tools(CM_SHORTS); /* Basic algorithms. */ 61 printf("Give base prime p:\n"); fflush(stdout); 62 gin(p); 63 for(dc=0; dc < 6; dc++) g[dc] = newgiant(CM_SHORTS); 64 for(dc = 0; dc < DCOUNT; dc++) { 65 d = disc12[dc]; 66 /* Next, seek representation 4N = u^2 + |d| v^2. */ 67 if(cornacchia4(p, d, u, v) == 0) continue; 68/* Here, (u,v) give the quadratic representation of 4p. */ 69 printf("D: %d\n", d); fflush(stdout); 70 gtog(u, g[0]); 71 switch(d) { 72 case -3: olen = 3; /* Six orders: p + 1 +- g[0,1,2]. */ 73 gtog(u, g[1]); gtog(v, g[2]); 74 addg(g[2], g[2]); addg(v, g[2]); /* g[2] := 3v. */ 75 addg(g[2], g[1]); gshiftright(1, g[1]); /* g[1] = (u + 3v)/2. */ 76 subg(u, g[2]); gshiftright(1, g[2]); absg(g[2]); /* g[2] = |u-3v|/2. */ 77 break; 78 case -4: olen = 2; /* Four orders: p + 1 +- g[0,1]. */ 79 gtog(v, g[1]); addg(g[1], g[1]); /* g[1] = 2v. */ 80 break; 81 default: olen = 1; /* Two orders: p + 1 +- g[0]. */ 82 } 83 for(k=0; k < olen; k++) { 84 gtog(p, plus_order); iaddg(1, plus_order); 85 gtog(p, minus_order); iaddg(1, minus_order); 86 addg(g[k], plus_order); 87 subg(g[k], minus_order); 88 printf("curve orders: \n"); 89 printf("(%d) ", prime_probable(plus_order)); 90 gout(plus_order); 91 printf("(%d) ", prime_probable(minus_order)); 92 gout(minus_order); 93 } 94 } 95} 96 97 98 99 100 101 102 103 104 105 106