1f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project#include <tommath.h> 2f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project#ifdef BN_MP_PRIME_NEXT_PRIME_C 3f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project/* LibTomMath, multiple-precision integer library -- Tom St Denis 4f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * 5f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * LibTomMath is a library that provides multiple-precision 6f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * integer arithmetic as well as number theoretic functionality. 7f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * 8f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * The library was designed directly after the MPI library by 9f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * Michael Fromberger but has been written from scratch with 10f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * additional optimizations in place. 11f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * 12f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * The library is free for all purposes without any express 13f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * guarantee it works. 14f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * 15f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * Tom St Denis, tomstdenis@gmail.com, http://math.libtomcrypt.com 16f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project */ 17f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 18f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project/* finds the next prime after the number "a" using "t" trials 19f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * of Miller-Rabin. 20f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * 21f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * bbs_style = 1 means the prime must be congruent to 3 mod 4 22f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project */ 23f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint mp_prime_next_prime(mp_int *a, int t, int bbs_style) 24f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project{ 25f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project int err, res, x, y; 26f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_digit res_tab[PRIME_SIZE], step, kstep; 27f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_int b; 28f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 29f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* ensure t is valid */ 30f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (t <= 0 || t > PRIME_SIZE) { 31f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return MP_VAL; 32f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 33f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 34f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* force positive */ 35f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project a->sign = MP_ZPOS; 36f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 37f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* simple algo if a is less than the largest prime in the table */ 38f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (mp_cmp_d(a, ltm_prime_tab[PRIME_SIZE-1]) == MP_LT) { 39f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* find which prime it is bigger than */ 40f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project for (x = PRIME_SIZE - 2; x >= 0; x--) { 41f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (mp_cmp_d(a, ltm_prime_tab[x]) != MP_LT) { 42f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (bbs_style == 1) { 43f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* ok we found a prime smaller or 44f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * equal [so the next is larger] 45f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * 46f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * however, the prime must be 47f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * congruent to 3 mod 4 48f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project */ 49f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((ltm_prime_tab[x + 1] & 3) != 3) { 50f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* scan upwards for a prime congruent to 3 mod 4 */ 51f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project for (y = x + 1; y < PRIME_SIZE; y++) { 52f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((ltm_prime_tab[y] & 3) == 3) { 53f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_set(a, ltm_prime_tab[y]); 54f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return MP_OKAY; 55f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 56f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 57f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 58f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } else { 59f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_set(a, ltm_prime_tab[x + 1]); 60f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return MP_OKAY; 61f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 62f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 63f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 64f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* at this point a maybe 1 */ 65f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (mp_cmp_d(a, 1) == MP_EQ) { 66f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_set(a, 2); 67f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return MP_OKAY; 68f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 69f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* fall through to the sieve */ 70f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 71f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 72f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* generate a prime congruent to 3 mod 4 or 1/3 mod 4? */ 73f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (bbs_style == 1) { 74f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project kstep = 4; 75f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } else { 76f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project kstep = 2; 77f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 78f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 79f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* at this point we will use a combination of a sieve and Miller-Rabin */ 80f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 81f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (bbs_style == 1) { 82f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* if a mod 4 != 3 subtract the correct value to make it so */ 83f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((a->dp[0] & 3) != 3) { 84f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((err = mp_sub_d(a, (a->dp[0] & 3) + 1, a)) != MP_OKAY) { return err; }; 85f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 86f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } else { 87f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (mp_iseven(a) == 1) { 88f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* force odd */ 89f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((err = mp_sub_d(a, 1, a)) != MP_OKAY) { 90f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return err; 91f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 92f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 93f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 94f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 95f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* generate the restable */ 96f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project for (x = 1; x < PRIME_SIZE; x++) { 97f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((err = mp_mod_d(a, ltm_prime_tab[x], res_tab + x)) != MP_OKAY) { 98f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return err; 99f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 100f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 101f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 102f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* init temp used for Miller-Rabin Testing */ 103f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((err = mp_init(&b)) != MP_OKAY) { 104f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return err; 105f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 106f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 107f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project for (;;) { 108f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* skip to the next non-trivially divisible candidate */ 109f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project step = 0; 110f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project do { 111f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* y == 1 if any residue was zero [e.g. cannot be prime] */ 112f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project y = 0; 113f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 114f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* increase step to next candidate */ 115f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project step += kstep; 116f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 117f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* compute the new residue without using division */ 118f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project for (x = 1; x < PRIME_SIZE; x++) { 119f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* add the step to each residue */ 120f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project res_tab[x] += kstep; 121f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 122f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* subtract the modulus [instead of using division] */ 123f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (res_tab[x] >= ltm_prime_tab[x]) { 124f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project res_tab[x] -= ltm_prime_tab[x]; 125f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 126f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 127f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* set flag if zero */ 128f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (res_tab[x] == 0) { 129f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project y = 1; 130f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 131f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 132f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } while (y == 1 && step < ((((mp_digit)1)<<DIGIT_BIT) - kstep)); 133f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 134f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* add the step */ 135f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((err = mp_add_d(a, step, a)) != MP_OKAY) { 136f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto LBL_ERR; 137f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 138f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 139f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* if didn't pass sieve and step == MAX then skip test */ 140f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (y == 1 && step >= ((((mp_digit)1)<<DIGIT_BIT) - kstep)) { 141f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project continue; 142f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 143f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 144f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* is this prime? */ 145f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project for (x = 0; x < t; x++) { 146f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_set(&b, ltm_prime_tab[t]); 147f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((err = mp_prime_miller_rabin(a, &b, &res)) != MP_OKAY) { 148f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto LBL_ERR; 149f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 150f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (res == MP_NO) { 151f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project break; 152f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 153f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 154f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 155f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (res == MP_YES) { 156f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project break; 157f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 158f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 159f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 160f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project err = MP_OKAY; 161f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectLBL_ERR: 162f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_clear(&b); 163f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return err; 164f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project} 165f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 166f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project#endif 167f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 168f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project/* $Source: /cvs/libtom/libtommath/bn_mp_prime_next_prime.c,v $ */ 169f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project/* $Revision: 1.3 $ */ 170f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project/* $Date: 2006/03/31 14:18:44 $ */ 171