## Return to Question

3 edited tags
Post Closed as "too localized" by Andres Caicedo, LowerBounds, Will Jagy, Felipe Voloch, Zev Chonoles
2 added 84 characters in body

How do I prove the following?

N is odd, composite. A is uniformly selected from $\{ x | 0 < x < N, gcd(x, N) = 1\}$. Then probability $\left( \frac{N}{A} \right) = A^{1/2 (N-1)} \mod N$ < 0.5

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).

I understand the following:

(1) Quadratic Reprocity (for primes, and composites) (2) Euler Criteron (for primes)

Thanks!

Question resolved:

A Fast Monte-Carlo Test for Primality (Solovay / Strassen)

1