# Riemann proof effect on factoring composites

1. Jun 13, 2009

### Loren Booda

To what degree would proving the Riemann hypothesis facilitate the factoring of large composites? In other words, how much would a complete (as opposed to "hit-or-miss") knowledge of primes help to reduce the operations needed to factor large composites?

2. Jun 14, 2009

### CRGreathouse

Not at all.

It might improve one or two obscure sieving algorithms, though. Maybe the pseudosquare sieve?

3. Jun 14, 2009

### Loren Booda

Consider all primes being initially unknown against a complete knowledge of primes. By what parameter does that knowledge reduce the number of operations to factorize composites.

4. Jun 14, 2009

### Dragonfall

If memory serves, there are some algorithms which are right now probabilistic, but become deterministic if the generalized RH is true.

EDIT: There we go.

5. Jun 14, 2009

### CRGreathouse

Yes, but the question was about the RH not the GRH. And even under the GRH, the article mentions only one factoring algorithm: the quadratic sieve via Shanks-Tonelli. I'm not even sure how Shanks-Tonelli helps the quadratic sieve, since it needs x^2 = a^2 (mod n) and Shanks-Tonelli finds x^2 = b (mod p) for prime p.

6. Jun 14, 2009

### Dragonfall

Ya I can't figure it out either. Might have to initiate a discussion the talk page.

7. Jun 15, 2009

### Hurkyl

Staff Emeritus
One of the steps in the QS requires you to find square roots mod p, doesn't it?

8. Jun 15, 2009

### CRGreathouse

How much time does that take, asymptotically?

9. Jun 15, 2009

### Hurkyl

Staff Emeritus
Well, you have to solve x²=N (mod p) for every prime p below the smoothness bound. Sounds like a lot.