The book introduces new techniques which imply rigorous lower bounds on the complexity of some number theoretic and cryptographic problems. These functions are considered over the residue ring modulo p and over the residue ring modulo an arbitrary divisor d of p - 1.