bool CG21_check_sqrt_exist()

in src/cg21/cg21_utilities.c [1086:1156]

• 45 lines of code
• 3 McCabe index (conditional complexity)

bool CG21_check_sqrt_exist(BIG_1024_58 a[FFLEN_2048], BIG_1024_58 p[HFLEN_2048]){
    BIG_1024_58 t[HFLEN_2048];
    BIG_1024_58 t2[HFLEN_2048];
    BIG_1024_58 t3[HFLEN_2048];
    BIG_1024_58 t4[FFLEN_2048];
    BIG_1024_58 t5[FFLEN_2048];
    BIG_1024_58 p_[FFLEN_2048];

    // Check p = 3 mod 4
    FF_2048_init(t3,4,FFLEN_2048);
    FF_2048_zero(t,FFLEN_2048);
    FF_2048_copy(t,p,FFLEN_2048);
    FF_2048_mod(t, t3,FFLEN_2048);

    BIG_1024_58_dec(*t,3);
    BIG_1024_58_norm(*t);

    int rc = BIG_1024_58_iszilch(*t);
    if (rc==0) {
        return false;
    }

    FF_2048_zero(p_,FFLEN_2048);
    FF_2048_copy(p_,p,HFLEN_2048);


    /* ---------STEP 1: compute t ----------
     * t = (p-1)/2 mod p
    */

    FF_2048_zero(t,HFLEN_2048);
    FF_2048_copy(t,p,HFLEN_2048); // t <- p
    BIG_1024_58_dec(*t,1); // t = p - 1
    BIG_1024_58_norm(*t);

    FF_2048_init(t3,2,HFLEN_2048);
    FF_2048_invmodp(t3,t3,p,HFLEN_2048); // inverse of 2 mod p
    FF_2048_mul(t4,t3,t,HFLEN_2048); // (p-1)/2
    FF_2048_mod(t4,p_,FFLEN_2048); // (p-1)/2 mod p
    FF_2048_copy(t, t4, HFLEN_2048); // t <- (p-1)/2 mod p


    /* ---------STEP 2: compute t2 ----------
     * t5 = a mod p
     * t2 = a^{(p-1)/2} mod p
    */

    FF_2048_copy(t5, a, FFLEN_2048);
    FF_2048_mod(t5,p_,FFLEN_2048); // t5 <- a mod p
    FF_2048_copy(t3, t5, HFLEN_2048); // t5 <- t3

    FF_2048_ct_pow(t2,t3,t,p,HFLEN_2048,HFLEN_2048); // a^{(p-1)/2} mod p

    // n^{(p-1)/2} mod p = 1 then a has a square root
    BIG_1024_58_dec(*t2,1);     // t2 <- n^{(p-1)/2} - 1
    rc = BIG_1024_58_iszilch(*t2);  // rc=(t2==0)

    // clean up
    FF_2048_zero(t,HFLEN_2048);
    FF_2048_zero(t2,HFLEN_2048);
    FF_2048_zero(t3,HFLEN_2048);
    FF_2048_zero(t4,FFLEN_2048);
    FF_2048_zero(t5,FFLEN_2048);
    FF_2048_zero(p_,FFLEN_2048);


    if (rc==1)
        return true;
    else
        return false;
}