most recent 30 from http://mathoverflow.net 2013-05-25T15:36:45Z http://mathoverflow.net/feeds/user/13405 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/38245/what-is-the-easiest-randomized-algorithm-to-motivate-to-the-layperson/57342#57342 none 2011-03-04T11:14:45Z 2011-03-04T11:14:45Z

<p>Nobody has mentioned the Solovay-Strassen primality test? It's easy to explain (at least with handwaving) that the Jacobi symbol and the modular exponential are straightforward to compute. Then for odd prime n, $a^{(n-1)/2}\equiv \big({a\over n}\big)$ for all bases a, but for composite n, the equality doesn't hold for at least half the bases. So you choose bases at random until you find a compositeness witness or satisfy yourself that you're not going to find one (probability $\le 2^{-k}$ after k tests). I think this was one of the earliest ones? It's very easy to motivate and understand IMHO.</p>