Line data    Source code

       1             : #include "tommath_private.h"
       2             : #ifdef BN_MP_PRIME_NEXT_PRIME_C
       3             : /* LibTomMath, multiple-precision integer library -- Tom St Denis */
       4             : /* SPDX-License-Identifier: Unlicense */
       5             : 
       6             : /* finds the next prime after the number "a" using "t" trials
       7             :  * of Miller-Rabin.
       8             :  *
       9             :  * bbs_style = 1 means the prime must be congruent to 3 mod 4
      10             :  */
      11           0 : mp_err mp_prime_next_prime(mp_int *a, int t, int bbs_style)
      12             : {
      13           0 :    int      x, y;
      14           0 :    mp_ord   cmp;
      15           0 :    mp_err   err;
      16           0 :    mp_bool  res = MP_NO;
      17           0 :    mp_digit res_tab[PRIVATE_MP_PRIME_TAB_SIZE], step, kstep;
      18           0 :    mp_int   b;
      19             : 
      20             :    /* force positive */
      21           0 :    a->sign = MP_ZPOS;
      22             : 
      23             :    /* simple algo if a is less than the largest prime in the table */
      24           0 :    if (mp_cmp_d(a, s_mp_prime_tab[PRIVATE_MP_PRIME_TAB_SIZE-1]) == MP_LT) {
      25             :       /* find which prime it is bigger than "a" */
      26           0 :       for (x = 0; x < PRIVATE_MP_PRIME_TAB_SIZE; x++) {
      27           0 :          cmp = mp_cmp_d(a, s_mp_prime_tab[x]);
      28           0 :          if (cmp == MP_EQ) {
      29           0 :             continue;
      30             :          }
      31           0 :          if (cmp != MP_GT) {
      32           0 :             if ((bbs_style == 1) && ((s_mp_prime_tab[x] & 3u) != 3u)) {
      33             :                /* try again until we get a prime congruent to 3 mod 4 */
      34           0 :                continue;
      35             :             } else {
      36           0 :                mp_set(a, s_mp_prime_tab[x]);
      37           0 :                return MP_OKAY;
      38             :             }
      39             :          }
      40             :       }
      41             :       /* fall through to the sieve */
      42             :    }
      43             : 
      44             :    /* generate a prime congruent to 3 mod 4 or 1/3 mod 4? */
      45           0 :    if (bbs_style == 1) {
      46           0 :       kstep   = 4;
      47             :    } else {
      48           0 :       kstep   = 2;
      49             :    }
      50             : 
      51             :    /* at this point we will use a combination of a sieve and Miller-Rabin */
      52             : 
      53           0 :    if (bbs_style == 1) {
      54             :       /* if a mod 4 != 3 subtract the correct value to make it so */
      55           0 :       if ((a->dp[0] & 3u) != 3u) {
      56           0 :          if ((err = mp_sub_d(a, (a->dp[0] & 3u) + 1u, a)) != MP_OKAY) {
      57           0 :             return err;
      58             :          }
      59             :       }
      60             :    } else {
      61           0 :       if (MP_IS_EVEN(a)) {
      62             :          /* force odd */
      63           0 :          if ((err = mp_sub_d(a, 1uL, a)) != MP_OKAY) {
      64           0 :             return err;
      65             :          }
      66             :       }
      67             :    }
      68             : 
      69             :    /* generate the restable */
      70           0 :    for (x = 1; x < PRIVATE_MP_PRIME_TAB_SIZE; x++) {
      71           0 :       if ((err = mp_mod_d(a, s_mp_prime_tab[x], res_tab + x)) != MP_OKAY) {
      72           0 :          return err;
      73             :       }
      74             :    }
      75             : 
      76             :    /* init temp used for Miller-Rabin Testing */
      77           0 :    if ((err = mp_init(&b)) != MP_OKAY) {
      78           0 :       return err;
      79             :    }
      80             : 
      81           0 :    for (;;) {
      82             :       /* skip to the next non-trivially divisible candidate */
      83           0 :       step = 0;
      84           0 :       do {
      85             :          /* y == 1 if any residue was zero [e.g. cannot be prime] */
      86           0 :          y     =  0;
      87             : 
      88             :          /* increase step to next candidate */
      89           0 :          step += kstep;
      90             : 
      91             :          /* compute the new residue without using division */
      92           0 :          for (x = 1; x < PRIVATE_MP_PRIME_TAB_SIZE; x++) {
      93             :             /* add the step to each residue */
      94           0 :             res_tab[x] += kstep;
      95             : 
      96             :             /* subtract the modulus [instead of using division] */
      97           0 :             if (res_tab[x] >= s_mp_prime_tab[x]) {
      98           0 :                res_tab[x]  -= s_mp_prime_tab[x];
      99             :             }
     100             : 
     101             :             /* set flag if zero */
     102           0 :             if (res_tab[x] == 0u) {
     103           0 :                y = 1;
     104             :             }
     105             :          }
     106           0 :       } while ((y == 1) && (step < (((mp_digit)1 << MP_DIGIT_BIT) - kstep)));
     107             : 
     108             :       /* add the step */
     109           0 :       if ((err = mp_add_d(a, step, a)) != MP_OKAY) {
     110           0 :          goto LBL_ERR;
     111             :       }
     112             : 
     113             :       /* if didn't pass sieve and step == MP_MAX then skip test */
     114           0 :       if ((y == 1) && (step >= (((mp_digit)1 << MP_DIGIT_BIT) - kstep))) {
     115           0 :          continue;
     116             :       }
     117             : 
     118           0 :       if ((err = mp_prime_is_prime(a, t, &res)) != MP_OKAY) {
     119           0 :          goto LBL_ERR;
     120             :       }
     121           0 :       if (res == MP_YES) {
     122           0 :          break;
     123             :       }
     124             :    }
     125             : 
     126           0 :    err = MP_OKAY;
     127           0 : LBL_ERR:
     128           0 :    mp_clear(&b);
     129           0 :    return err;
     130             : }
     131             : 
     132             : #endif