projects / apple / security.git / blame
| Commit | Line | Data |
|---|---|---|
| b1ab9ed8 A |
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 | ||
| 39 | int 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 | ||
| 49 | main(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 |