Probabilistic verification of signature schemes like RSA? I was wondering if there were any verification algorithm in the literature that enables a "probabilistic" verification of well-known signature schemes?

For RSA signature verification for example, is there any way to verify $s^e = H(m) \mod N$ in a fast way but with a certain "error" probability ?

If not for RSA, for any other schemes ?
Every signature scheme has some nonzero forgery probability: if there are $n$ distinct possible signatures, this forgery probability is always at least $1/n$, because a forger could just try signatures uniformly at random.  But sometimes $n$ is so large that $1/n$ is smaller than it needs to be for confidence, say $1/2^{2048}$ when all you really need is $1/2^{100}$, and we can exploit this to trade off forgery probability for performance.  Here's an example of how, with RSA.

Suppose a signature is not an integer $s$ such that $s^e \equiv H(m) \pmod N$, but rather a pair of integers $(s, k)$ with $s &lt; N$ and $k &lt; N^{e - 1}$ such that $$s^e = H(m) + kN.$$  Then the verifier can verify this equation modulo a secret uniform random $v$-bit prime $r$, $$s^e \equiv H(m) + kN \pmod r.$$  There are $\pi(2^v) - \pi(2^{v-1})$ such primes, and $s^e - h - kN$ has at most $\lceil(\log_2 N^e)/v\rceil$ $v$-bit prime factors, so the probability that $r \mid s^e - h - kN$ is at most $$\frac{\lceil(\log_2 N^e)/v\rceil}{\pi(2^v) - \pi(2^{v-1})}$$ for any fixed $(s, k)$, $h$, and $N$ unless $s^e = h + kN$.  Of course, while the forger can try about $t$ messages to find one whose hash $h$ has a desired property occurring with probability $1/t$, only about $1/2^{2048}$ of them satisfy $s^e = h + kN$ if $N \approx 2^{2048}$, so the forger has no hope of finding those.

For $v = 128$, we have $$\pi(2^v) - \pi(2^{v - 1}) \approx \frac{2^{128}}{\log 2^{128}} - \frac{2^{127}}{\log 2^{127}} \approx 2^{120},$$ and for $e = 3$ and $N \approx 2^{2048}$, we have $\lceil(\log_2 N^e)/v\rceil = 48$, so the forgery probability is at most about $1/2^{114}$.

Obviously, the verifier can choose independent primes $r_1, r_2, r_3, \dots$ to lower the forgery probability further; the verifier can also reuse the primes for multiple verifications to save effort, as long as they remain secret.

This scheme is not particularly attractive unless $e$ is very small: even for $e = 3$, it triples the size of the signature.  It is most attractive for Rabin-type signatures with $e = 2$, which are, of course, qualitatively different from RSA-type signatures (and largely better all around except in being deployed anywhere!).

To my knowledge, this idea was first published by Bernstein in 1997, and is mentioned in his summary paper on modular root signature schemes discussing many variations on the themes of RSA and Rabin–Williams signatures.