We give a general reduction of lengths-of-proofs lower bounds forconstant depth Frege systems in DeMorgan language augmented bya connective counting modulo a prime p (the so called AC0[p] Frege systems)to computational complexitylower bounds for search tasks involving search trees branching uponvalues of linear maps on the vector space oflow degree polynomials over the finite field with p elements.