Riemann proof effect on factoring composites

[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?

 

[CRGreathouse]

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?

Not at all.

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

 

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

 

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

 

[CRGreathouse]

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.

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.

 

[Dragonfall]

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

 

[Hurkyl]

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.

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

 

[CRGreathouse]

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

How much time does that take, asymptotically?

 

[Hurkyl]

How much time does that take, asymptotically?

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