Therefore, taking the average with respect to the induced distribution on yi, the average-case complexity of f is the same (within polynomial factors) as the worst-case randomized complexity of f. One special case of note is when each random instance yi is distributed uniformly over the entire set of elements in the domain of f that have a length of |x|.
The field of cryptography utilizes the fact that certain number-theoretic functions are randomly self-reducible.
This includes probabilistic encryption and cryptographically strong pseudorandom number generation.
Given a generator g of a cyclic group G = { gi | 0 ≤ i < |G| }, and an x ∈ G, the discrete log of x to the base g is the integer k (0 ≤ k < |G|) with x = gk.
Clearly, p(0) is equal to the permanent of M. Suppose we know a program that computes the correct value of PERM(A) for most n-by-n matrices with entries from Fp---specifically, 1 − 1/(3n) of them.
If we do so, we run the risk of being wrong 1/3 of the time, but by picking multiple random Xs and repeating the above procedure many times, and only providing the majority winner as an answer, we can drive the error rate down very low.