We present very fast and practical methods for generating randomly distributed pairs of the form $(x,g^x \bmod p)$ or $(x,x^e \bmod n)$ using pre-computation. These generation schemes can be used in various public-key schemes with a smooth memory-speed tradeoff and the cost of exponentiating is reduced to approximately 16 modular multiplications. We show, modulo some hardness assumptions, that we {\em preserve} the security in the sense that if a public-key scheme is broken when one uses our generation scheme, then one can break the original scheme. A scheme for speed-up that does not admit such analysis may introduce insecurity and actually get broken later (e.g. \cite{schnorr91,dr-break-schnorr93}).