The book introduces new techniques that imply rigorous lower bounds on the com­ plexity 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.