void Traverse_w_notdiv_e_fullsigned()

in src/compression/dlog.c [315:401]

• 78 lines of code
• 20 McCabe index (conditional complexity)

void Traverse_w_notdiv_e_fullsigned(const f2elm_t r, int j, int k, int z, const unsigned int *P, const felm_t *CT1, const felm_t *CT2, 
                                    int *D, int Dlen, int ell, int ellw, int ell_emodw, int w, int e)
{ // Traverse a Pohlig-Hellman optimal strategy to solve a discrete log in a group of order ell^e
 // Leaves are used to recover the digits which are numbers from 0 to ell^w-1 except by the last leaf that gives a digit between 0 and ell^(e mod w)
 // Assume w does not divide the exponent e
    f2elm_t rp = {0}, alpha = {0};            
    
    if (z > 1) {
        int t = P[z], goleft;
        fp2copy(r, rp);
        
        goleft = (j > 0) ? w*(z-t) : (e % w) + w*(z-t-1);
        for (int i = 0; i < goleft; i++) {
            if ((ell & 1) == 0)
                sqr_Fp2_cycl(rp, (digit_t*)&Montgomery_one);
            else
                cube_Fp2_cycl(rp, (digit_t*)&Montgomery_one);
        }

        Traverse_w_notdiv_e_fullsigned(rp, j + (z - t), k, t, P, CT1, CT2, D, Dlen, ell, ellw, ell_emodw, w, e);  
        
        fp2copy(r, rp);
        for (int h = k; h < k + t; h++) {
            if (D[h] != 0) {
                if (j > 0) {
                    if (D[h] < 0) {
                        fp2copy(CT2 + 2*(j + h)*(ellw/2)+2*(-D[h]-1), alpha);
                        fpneg(alpha[1]);                        
                        fp2mul_mont(rp, alpha, rp);
                    } else {
                        fp2mul_mont(rp, CT2 + 2*((j + h)*(ellw/2) + (D[h]-1)), rp);
                    }
                } else {
                    if (D[h] < 0) {
                        fp2copy(CT1 + 2*((j + h)*(ellw/2) + (-D[h]-1)), alpha);
                        fpneg(alpha[1]);
                        fp2mul_mont(rp, alpha, rp);                
                    } else {
                        fp2mul_mont(rp, CT1 + 2*((j + h)*(ellw/2) + (D[h]-1)), rp);
                    }
                }
            }             
        }
        
        Traverse_w_notdiv_e_fullsigned(rp, j, k + t, z - t, P, CT1, CT2, D, Dlen, ell, ellw, ell_emodw, w, e);
    } 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 {            
            if (!(j == 0 && k == Dlen - 1)) {
                for (int t = 1; t <= (ellw/2); t++) {
                    if (memcmp(CT2[2*(ellw/2)*(Dlen-1) + 2*(t-1)], rp, 2*NBITS_TO_NBYTES(NBITS_FIELD)) == 0) {
                        D[k] = -t;
                        break;             
                    } else {
                        fp2copy(CT2 + 2*((ellw/2)*(Dlen-1) + (t-1)), alpha);
                        fpneg(alpha[1]);
                        fpcorrection(alpha[1]);
                        if (memcmp(rp, alpha, 2*NBITS_TO_NBYTES(NBITS_FIELD)) == 0) {
                            D[k] = t;
                            break;
                        }
                    }                           
                }
            } else {            
                for (int t = 1; t <= ell_emodw/2; t++) {     
                    if (memcmp(CT1[2*(ellw/2)*(Dlen - 1) + 2*(t-1)], rp, 2*NBITS_TO_NBYTES(NBITS_FIELD)) == 0) { 
                        D[k] = -t;
                        break;                
                    } else {
                        fp2copy(CT1 + 2*((ellw/2)*(Dlen-1) + (t-1)), alpha);
                        fpneg(alpha[1]);
                        fpcorrection(alpha[1]);
                        if (memcmp(rp, alpha, 2*NBITS_TO_NBYTES(NBITS_FIELD)) == 0) {
                            D[k] = t;
                            break;
                        }                        
                    }

                }
            }   
        }
    }
}