Line data    Source code

       1             : #include "tommath_private.h"
       2             : #ifdef BN_MP_IS_SQUARE_C
       3             : /* LibTomMath, multiple-precision integer library -- Tom St Denis */
       4             : /* SPDX-License-Identifier: Unlicense */
       5             : 
       6             : /* Check if remainders are possible squares - fast exclude non-squares */
       7             : static const char rem_128[128] = {
       8             :    0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1,
       9             :    0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1,
      10             :    1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1,
      11             :    1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1,
      12             :    0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1,
      13             :    1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1,
      14             :    1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1,
      15             :    1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1
      16             : };
      17             : 
      18             : static const char rem_105[105] = {
      19             :    0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1,
      20             :    0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1,
      21             :    0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1,
      22             :    1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1,
      23             :    0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1,
      24             :    1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1,
      25             :    1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1
      26             : };
      27             : 
      28             : /* Store non-zero to ret if arg is square, and zero if not */
      29           0 : mp_err mp_is_square(const mp_int *arg, mp_bool *ret)
      30             : {
      31           0 :    mp_err        err;
      32           0 :    mp_digit      c;
      33           0 :    mp_int        t;
      34           0 :    unsigned long r;
      35             : 
      36             :    /* Default to Non-square :) */
      37           0 :    *ret = MP_NO;
      38             : 
      39           0 :    if (arg->sign == MP_NEG) {
      40           0 :       return MP_VAL;
      41             :    }
      42             : 
      43           0 :    if (MP_IS_ZERO(arg)) {
      44           0 :       return MP_OKAY;
      45             :    }
      46             : 
      47             :    /* First check mod 128 (suppose that MP_DIGIT_BIT is at least 7) */
      48           0 :    if (rem_128[127u & arg->dp[0]] == (char)1) {
      49           0 :       return MP_OKAY;
      50             :    }
      51             : 
      52             :    /* Next check mod 105 (3*5*7) */
      53           0 :    if ((err = mp_mod_d(arg, 105uL, &c)) != MP_OKAY) {
      54           0 :       return err;
      55             :    }
      56           0 :    if (rem_105[c] == (char)1) {
      57           0 :       return MP_OKAY;
      58             :    }
      59             : 
      60             : 
      61           0 :    if ((err = mp_init_u32(&t, 11u*13u*17u*19u*23u*29u*31u)) != MP_OKAY) {
      62           0 :       return err;
      63             :    }
      64           0 :    if ((err = mp_mod(arg, &t, &t)) != MP_OKAY) {
      65           0 :       goto LBL_ERR;
      66             :    }
      67           0 :    r = mp_get_u32(&t);
      68             :    /* Check for other prime modules, note it's not an ERROR but we must
      69             :     * free "t" so the easiest way is to goto LBL_ERR.  We know that err
      70             :     * is already equal to MP_OKAY from the mp_mod call
      71             :     */
      72           0 :    if (((1uL<<(r%11uL)) & 0x5C4uL) != 0uL)         goto LBL_ERR;
      73           0 :    if (((1uL<<(r%13uL)) & 0x9E4uL) != 0uL)         goto LBL_ERR;
      74           0 :    if (((1uL<<(r%17uL)) & 0x5CE8uL) != 0uL)        goto LBL_ERR;
      75           0 :    if (((1uL<<(r%19uL)) & 0x4F50CuL) != 0uL)       goto LBL_ERR;
      76           0 :    if (((1uL<<(r%23uL)) & 0x7ACCA0uL) != 0uL)      goto LBL_ERR;
      77           0 :    if (((1uL<<(r%29uL)) & 0xC2EDD0CuL) != 0uL)     goto LBL_ERR;
      78           0 :    if (((1uL<<(r%31uL)) & 0x6DE2B848uL) != 0uL)    goto LBL_ERR;
      79             : 
      80             :    /* Final check - is sqr(sqrt(arg)) == arg ? */
      81           0 :    if ((err = mp_sqrt(arg, &t)) != MP_OKAY) {
      82           0 :       goto LBL_ERR;
      83             :    }
      84           0 :    if ((err = mp_sqr(&t, &t)) != MP_OKAY) {
      85           0 :       goto LBL_ERR;
      86             :    }
      87             : 
      88           0 :    *ret = (mp_cmp_mag(&t, arg) == MP_EQ) ? MP_YES : MP_NO;
      89           0 : LBL_ERR:
      90           0 :    mp_clear(&t);
      91           0 :    return err;
      92             : }
      93             : #endif