Riemann proof effect on factoring composites

**Loren Booda** · Jun14-09, 12:17 AM

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** · Jun14-09, 01:05 AM

Originally Posted by 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?

Not at all.

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

**Loren Booda** · Jun14-09, 02:48 AM

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** · Jun14-09, 09:56 AM

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** · Jun14-09, 12:20 PM

Originally Posted by 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.

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** · Jun14-09, 06:38 PM

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

**Hurkyl** · Jun15-09, 10:28 AM

Originally Posted by CRGreathouse

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** · Jun15-09, 01:08 PM

Originally Posted by Hurkyl

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** · Jun15-09, 11:20 PM

Originally Posted by CRGreathouse

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.