1f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project/* Generates provable primes 2f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * 3f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * See http://gmail.com:8080/papers/pp.pdf for more info. 4f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * 5f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * Tom St Denis, tomstdenis@gmail.com, http://tom.gmail.com 6f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project */ 7f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project#include <time.h> 8f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project#include "tommath.h" 9f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 10f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint n_prime; 11f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectFILE *primes; 12f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 13f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project/* fast square root */ 14f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectstatic mp_digit 15f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projecti_sqrt (mp_word x) 16f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project{ 17f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_word x1, x2; 18f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 19f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project x2 = x; 20f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project do { 21f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project x1 = x2; 22f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project x2 = x1 - ((x1 * x1) - x) / (2 * x1); 23f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } while (x1 != x2); 24f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 25f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (x1 * x1 > x) { 26f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project --x1; 27f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 28f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 29f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return x1; 30f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project} 31f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 32f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 33f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project/* generates a prime digit */ 34f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectstatic void gen_prime (void) 35f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project{ 36f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_digit r, x, y, next; 37f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project FILE *out; 38f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 39f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project out = fopen("pprime.dat", "wb"); 40f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 41f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* write first set of primes */ 42f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project r = 3; fwrite(&r, 1, sizeof(mp_digit), out); 43f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project r = 5; fwrite(&r, 1, sizeof(mp_digit), out); 44f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project r = 7; fwrite(&r, 1, sizeof(mp_digit), out); 45f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project r = 11; fwrite(&r, 1, sizeof(mp_digit), out); 46f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project r = 13; fwrite(&r, 1, sizeof(mp_digit), out); 47f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project r = 17; fwrite(&r, 1, sizeof(mp_digit), out); 48f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project r = 19; fwrite(&r, 1, sizeof(mp_digit), out); 49f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project r = 23; fwrite(&r, 1, sizeof(mp_digit), out); 50f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project r = 29; fwrite(&r, 1, sizeof(mp_digit), out); 51f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project r = 31; fwrite(&r, 1, sizeof(mp_digit), out); 52f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 53f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* get square root, since if 'r' is composite its factors must be < than this */ 54f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project y = i_sqrt (r); 55f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project next = (y + 1) * (y + 1); 56f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 57f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project for (;;) { 58f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project do { 59f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project r += 2; /* next candidate */ 60f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project r &= MP_MASK; 61f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (r < 31) break; 62f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 63f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* update sqrt ? */ 64f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (next <= r) { 65f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project ++y; 66f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project next = (y + 1) * (y + 1); 67f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 68f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 69f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* loop if divisible by 3,5,7,11,13,17,19,23,29 */ 70f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((r % 3) == 0) { 71f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project x = 0; 72f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project continue; 73f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 74f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((r % 5) == 0) { 75f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project x = 0; 76f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project continue; 77f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 78f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((r % 7) == 0) { 79f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project x = 0; 80f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project continue; 81f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 82f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((r % 11) == 0) { 83f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project x = 0; 84f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project continue; 85f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 86f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((r % 13) == 0) { 87f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project x = 0; 88f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project continue; 89f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 90f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((r % 17) == 0) { 91f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project x = 0; 92f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project continue; 93f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 94f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((r % 19) == 0) { 95f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project x = 0; 96f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project continue; 97f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 98f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((r % 23) == 0) { 99f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project x = 0; 100f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project continue; 101f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 102f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((r % 29) == 0) { 103f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project x = 0; 104f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project continue; 105f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 106f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 107f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* now check if r is divisible by x + k={1,7,11,13,17,19,23,29} */ 108f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project for (x = 30; x <= y; x += 30) { 109f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((r % (x + 1)) == 0) { 110f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project x = 0; 111f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project break; 112f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 113f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((r % (x + 7)) == 0) { 114f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project x = 0; 115f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project break; 116f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 117f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((r % (x + 11)) == 0) { 118f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project x = 0; 119f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project break; 120f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 121f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((r % (x + 13)) == 0) { 122f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project x = 0; 123f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project break; 124f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 125f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((r % (x + 17)) == 0) { 126f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project x = 0; 127f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project break; 128f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 129f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((r % (x + 19)) == 0) { 130f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project x = 0; 131f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project break; 132f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 133f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((r % (x + 23)) == 0) { 134f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project x = 0; 135f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project break; 136f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 137f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((r % (x + 29)) == 0) { 138f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project x = 0; 139f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project break; 140f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 141f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 142f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } while (x == 0); 143f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (r > 31) { fwrite(&r, 1, sizeof(mp_digit), out); printf("%9d\r", r); fflush(stdout); } 144f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (r < 31) break; 145f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 146f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 147f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project fclose(out); 148f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project} 149f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 150f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectvoid load_tab(void) 151f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project{ 152f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project primes = fopen("pprime.dat", "rb"); 153f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (primes == NULL) { 154f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project gen_prime(); 155f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project primes = fopen("pprime.dat", "rb"); 156f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 157f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project fseek(primes, 0, SEEK_END); 158f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project n_prime = ftell(primes) / sizeof(mp_digit); 159f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project} 160f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 161f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectmp_digit prime_digit(void) 162f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project{ 163f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project int n; 164f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_digit d; 165f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 166f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project n = abs(rand()) % n_prime; 167f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project fseek(primes, n * sizeof(mp_digit), SEEK_SET); 168f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project fread(&d, 1, sizeof(mp_digit), primes); 169f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return d; 170f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project} 171f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 172f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 173f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project/* makes a prime of at least k bits */ 174f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint 175f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectpprime (int k, int li, mp_int * p, mp_int * q) 176f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project{ 177f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_int a, b, c, n, x, y, z, v; 178f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project int res, ii; 179f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project static const mp_digit bases[] = { 2, 3, 5, 7, 11, 13, 17, 19 }; 180f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 181f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* single digit ? */ 182f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (k <= (int) DIGIT_BIT) { 183f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_set (p, prime_digit ()); 184f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return MP_OKAY; 185f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 186f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 187f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_init (&c)) != MP_OKAY) { 188f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return res; 189f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 190f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 191f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_init (&v)) != MP_OKAY) { 192f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto LBL_C; 193f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 194f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 195f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* product of first 50 primes */ 196f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = 197f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_read_radix (&v, 198f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project "19078266889580195013601891820992757757219839668357012055907516904309700014933909014729740190", 199f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 10)) != MP_OKAY) { 200f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto LBL_V; 201f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 202f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 203f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_init (&a)) != MP_OKAY) { 204f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto LBL_V; 205f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 206f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 207f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* set the prime */ 208f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_set (&a, prime_digit ()); 209f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 210f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_init (&b)) != MP_OKAY) { 211f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto LBL_A; 212f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 213f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 214f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_init (&n)) != MP_OKAY) { 215f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto LBL_B; 216f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 217f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 218f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_init (&x)) != MP_OKAY) { 219f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto LBL_N; 220f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 221f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 222f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_init (&y)) != MP_OKAY) { 223f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto LBL_X; 224f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 225f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 226f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_init (&z)) != MP_OKAY) { 227f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto LBL_Y; 228f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 229f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 230f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* now loop making the single digit */ 231f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project while (mp_count_bits (&a) < k) { 232f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project fprintf (stderr, "prime has %4d bits left\r", k - mp_count_bits (&a)); 233f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project fflush (stderr); 234f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project top: 235f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_set (&b, prime_digit ()); 236f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 237f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* now compute z = a * b * 2 */ 238f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_mul (&a, &b, &z)) != MP_OKAY) { /* z = a * b */ 239f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto LBL_Z; 240f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 241f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 242f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_copy (&z, &c)) != MP_OKAY) { /* c = a * b */ 243f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto LBL_Z; 244f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 245f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 246f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_mul_2 (&z, &z)) != MP_OKAY) { /* z = 2 * a * b */ 247f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto LBL_Z; 248f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 249f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 250f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* n = z + 1 */ 251f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_add_d (&z, 1, &n)) != MP_OKAY) { /* n = z + 1 */ 252f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto LBL_Z; 253f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 254f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 255f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* check (n, v) == 1 */ 256f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_gcd (&n, &v, &y)) != MP_OKAY) { /* y = (n, v) */ 257f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto LBL_Z; 258f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 259f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 260f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (mp_cmp_d (&y, 1) != MP_EQ) 261f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto top; 262f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 263f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* now try base x=bases[ii] */ 264f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project for (ii = 0; ii < li; ii++) { 265f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_set (&x, bases[ii]); 266f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 267f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* compute x^a mod n */ 268f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_exptmod (&x, &a, &n, &y)) != MP_OKAY) { /* y = x^a mod n */ 269f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto LBL_Z; 270f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 271f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 272f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* if y == 1 loop */ 273f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (mp_cmp_d (&y, 1) == MP_EQ) 274f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project continue; 275f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 276f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* now x^2a mod n */ 277f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_sqrmod (&y, &n, &y)) != MP_OKAY) { /* y = x^2a mod n */ 278f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto LBL_Z; 279f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 280f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 281f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (mp_cmp_d (&y, 1) == MP_EQ) 282f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project continue; 283f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 284f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* compute x^b mod n */ 285f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_exptmod (&x, &b, &n, &y)) != MP_OKAY) { /* y = x^b mod n */ 286f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto LBL_Z; 287f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 288f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 289f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* if y == 1 loop */ 290f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (mp_cmp_d (&y, 1) == MP_EQ) 291f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project continue; 292f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 293f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* now x^2b mod n */ 294f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_sqrmod (&y, &n, &y)) != MP_OKAY) { /* y = x^2b mod n */ 295f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto LBL_Z; 296f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 297f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 298f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (mp_cmp_d (&y, 1) == MP_EQ) 299f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project continue; 300f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 301f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* compute x^c mod n == x^ab mod n */ 302f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_exptmod (&x, &c, &n, &y)) != MP_OKAY) { /* y = x^ab mod n */ 303f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto LBL_Z; 304f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 305f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 306f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* if y == 1 loop */ 307f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (mp_cmp_d (&y, 1) == MP_EQ) 308f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project continue; 309f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 310f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* now compute (x^c mod n)^2 */ 311f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_sqrmod (&y, &n, &y)) != MP_OKAY) { /* y = x^2ab mod n */ 312f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto LBL_Z; 313f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 314f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 315f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* y should be 1 */ 316f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (mp_cmp_d (&y, 1) != MP_EQ) 317f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project continue; 318f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project break; 319f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 320f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 321f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* no bases worked? */ 322f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (ii == li) 323f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto top; 324f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 325f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project{ 326f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project char buf[4096]; 327f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 328f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_toradix(&n, buf, 10); 329f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project printf("Certificate of primality for:\n%s\n\n", buf); 330f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_toradix(&a, buf, 10); 331f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project printf("A == \n%s\n\n", buf); 332f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_toradix(&b, buf, 10); 333f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project printf("B == \n%s\n\nG == %d\n", buf, bases[ii]); 334f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project printf("----------------------------------------------------------------\n"); 335f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project} 336f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 337f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* a = n */ 338f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_copy (&n, &a); 339f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 340f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 341f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* get q to be the order of the large prime subgroup */ 342f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_sub_d (&n, 1, q); 343f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_div_2 (q, q); 344f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_div (q, &b, q, NULL); 345f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 346f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_exch (&n, p); 347f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 348f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project res = MP_OKAY; 349f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectLBL_Z:mp_clear (&z); 350f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectLBL_Y:mp_clear (&y); 351f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectLBL_X:mp_clear (&x); 352f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectLBL_N:mp_clear (&n); 353f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectLBL_B:mp_clear (&b); 354f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectLBL_A:mp_clear (&a); 355f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectLBL_V:mp_clear (&v); 356f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectLBL_C:mp_clear (&c); 357f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return res; 358f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project} 359f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 360f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 361f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint 362f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectmain (void) 363f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project{ 364f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_int p, q; 365f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project char buf[4096]; 366f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project int k, li; 367f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project clock_t t1; 368f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 369f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project srand (time (NULL)); 370f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project load_tab(); 371f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 372f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project printf ("Enter # of bits: \n"); 373f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project fgets (buf, sizeof (buf), stdin); 374f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project sscanf (buf, "%d", &k); 375f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 376f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project printf ("Enter number of bases to try (1 to 8):\n"); 377f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project fgets (buf, sizeof (buf), stdin); 378f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project sscanf (buf, "%d", &li); 379f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 380f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 381f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_init (&p); 382f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_init (&q); 383f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 384f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project t1 = clock (); 385f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project pprime (k, li, &p, &q); 386f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project t1 = clock () - t1; 387f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 388f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project printf ("\n\nTook %ld ticks, %d bits\n", t1, mp_count_bits (&p)); 389f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 390f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_toradix (&p, buf, 10); 391f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project printf ("P == %s\n", buf); 392f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_toradix (&q, buf, 10); 393f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project printf ("Q == %s\n", buf); 394f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 395f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return 0; 396f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project} 397f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 398f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project/* $Source: /cvs/libtom/libtommath/etc/pprime.c,v $ */ 399f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project/* $Revision: 1.3 $ */ 400f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project/* $Date: 2006/03/31 14:18:47 $ */ 401