Quadratic Residue / Primality Testing - MathOverflow [closed] most recent 30 from http://mathoverflow.net 2013-05-24T02:55:05Z http://mathoverflow.net/feeds/question/60402 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/60402/quadratic-residue-primality-testing Quadratic Residue / Primality Testing LowerBounds 2011-04-03T02:49:31Z 2011-04-03T05:13:44Z <p>How do I prove the following?</p> <p>N is odd, composite. A is uniformly selected from $\{ x | 0 &lt; x &lt; N, gcd(x, N) = 1\}$. Then probability $\left( \frac{N}{A} \right) = A^{1/2 (N-1)} \mod N$ &lt; 0.5</p> <p>The context is Page 128, Chapter 7 of Arora/Borak. It talks about randomized primality testing. It cites Shoup 05 (which is available online); however I don't see the above proved anywhere in chapter 4 (quadratic resudies) or chapter 12 (jacobi symbol).</p> <p>I understand the following:</p> <p>(1) Quadratic Reprocity (for primes, and composites) (2) Euler Criteron (for primes)</p> <p>Thanks!</p> <p>Question resolved:</p> <p>A Fast Monte-Carlo Test for Primality (Solovay / Strassen)</p>