void Traverse_w_div_e_fullsigned()

in src/compression/dlog.c [254:312]

• 53 lines of code
• 14 McCabe index (conditional complexity)

void Traverse_w_div_e_fullsigned(const f2elm_t r, int j, int k, int z, const unsigned int *P, const felm_t *CT, int *D, 
                                 int Dlen, int ellw, int w)
{// Traverse a Pohlig-Hellman optimal strategy to solve a discrete log in a group of order ell^e
 // The leaves of the tree will be used to recover the signed digits which are numbers from +/-{0,1... Ceil((ell^w-1)/2)}
 // Assume the integer w divides the exponent e
    f2elm_t rp = {0}, alpha = {0};
    
    if (z > 1) {
        int t = P[z];
        fp2copy(r, rp);
        for (int i = 0; i < z-t; i++) {
            if ((ellw & 1) == 0) {
                for (int ii = 0; ii < w; ii++)
                    sqr_Fp2_cycl(rp, (digit_t*)&Montgomery_one);
            } else {
                for (int ii = 0; ii < w; ii++)
                    cube_Fp2_cycl(rp, (digit_t*)&Montgomery_one);
            }
        }
        
        Traverse_w_div_e_fullsigned(rp, j + (z - t), k, t, P, CT, D, Dlen, ellw, w);  
        
        fp2copy(r, rp);
        for (int h = k; h < k + t; h++) {
            if (D[h] != 0) {
                if(D[h] < 0) {
                    fp2copy(CT + 2*((j + h)*(ellw/2) + (-D[h]-1)), alpha);
                    fpneg(alpha[1]);
                    fp2mul_mont(rp, alpha, rp);
                } else {
                    fp2mul_mont(rp, CT + 2*((j + h)*(ellw/2) + (D[h]-1)), rp);
                }   
            }
        }
        Traverse_w_div_e_fullsigned(rp, j, k + t, z - t, P, CT, D, Dlen, ellw, w);
    } else {     
        fp2copy(r, rp);
        fp2correction(rp);

        if (is_felm_zero(rp[1]) && memcmp(rp[0],&Montgomery_one,NBITS_TO_NBYTES(NBITS_FIELD)) == 0) {
            D[k] = 0;
        } else {
            for (int t = 1; t <= ellw/2; t++) {
                if (memcmp(rp, CT[2*((Dlen - 1)*(ellw/2) + (t-1))], 2*NBITS_TO_NBYTES(NBITS_FIELD)) == 0) {
                    D[k] = -t;
                    break;
                } else {                    
                    fp2copy(CT + 2*((Dlen - 1)*(ellw/2) + (t-1)), alpha);
                    fpneg(alpha[1]);
                    fpcorrection(alpha[1]);
                    if (memcmp(rp, alpha, 2*NBITS_TO_NBYTES(NBITS_FIELD)) == 0) {
                        D[k] = t;
                        break;
                    }
                }               
            }
        }
    }
}