This paper presents a unified way to study the limitations of the generic quantum and classical algorithms to solve cryptographic problems over algebraic structures. Our main new lower bounds for the discrete logarithm (DL) and integer factoring problems are as follows. All lower bounds match the known algorithms, resolving many open problems suggested by Hhan, Yamakawa, and Yun (CRYPTO’24). The central tool of the proofs is the so-called compression lemma. Using this tool, we give alternative and simple proofs for the known lower bounds. We also prove the classical lower bounds for the (basic) index calculus method in the smooth GGM (SGGM). Our use of the compression lemma may be of independent interest. Along the way, we establish new generic models to prove the lower bounds: the QGRM and SGGM, which capture quantum factoring algorithms by Shor and Regev (or slight variations) and the basic index calculus, respectively. Thus, our lower bounds indicate the limitations of those strategies for the DL and factoring problems.