Riemann proof effect on factoring composites

Click For Summary

Discussion Overview

The discussion revolves around the potential implications of proving the Riemann hypothesis (RH) on the efficiency of factoring large composite numbers. Participants explore how complete knowledge of prime numbers might influence the operations required for factorization, considering both current algorithms and theoretical advancements.

Discussion Character

  • Exploratory
  • Technical explanation
  • Debate/contested
  • Mathematical reasoning

Main Points Raised

  • Some participants question the extent to which proving the RH would aid in factoring large composites, suggesting it might not significantly improve existing methods.
  • One participant mentions that certain algorithms could transition from probabilistic to deterministic if the generalized Riemann hypothesis (GRH) is proven, although the relevance of this to factoring remains unclear.
  • There is a discussion about the quadratic sieve and its reliance on finding square roots modulo primes, with uncertainty expressed about how the Shanks-Tonelli algorithm fits into this context.
  • Participants raise questions about the asymptotic time complexity of finding square roots modulo primes, indicating that this could be a significant factor in the efficiency of factoring algorithms.

Areas of Agreement / Disagreement

Participants do not reach a consensus on the impact of the RH or GRH on factoring algorithms. There are competing views regarding the effectiveness of current methods and the role of specific algorithms in this context.

Contextual Notes

Limitations include the dependence on the definitions of algorithms discussed, the distinction between RH and GRH, and the unresolved nature of how certain algorithms interact with the principles of prime factorization.

Loren Booda
Messages
3,115
Reaction score
4
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?
 
Physics news on Phys.org
Loren Booda said:
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?
 
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.
 
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.
 
Dragonfall said:
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.
 
Ya I can't figure it out either. Might have to initiate a discussion the talk page.
 
CRGreathouse said:
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?
 
Hurkyl said:
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?
 
CRGreathouse said:
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.
 

Similar threads

Undergrad Fundamental theorem of arithmetic from Jordan-Hölder theorem
  • · Replies 5 ·
Replies
5
Views
3K
Insights The History and Importance of the Riemann Hypothesis
  • · Replies 0 ·
Replies
0
Views
3K
  • Poll Poll
Why do we spend so little time learning grammar in college?
  • · Replies 142 ·
5
Replies
142
Views
7K
Undergrad I think I've hit upon a very easy proof of impossibility of quintic
  • · Replies 2 ·
Replies
2
Views
2K
Graduate Is the Riemann Hypothesis Finally Proven?
  • · Replies 4 ·
Replies
4
Views
3K
Undergrad Splitting ring of polynomials - why is this result unfindable?
  • · Replies 9 ·
Replies
9
Views
2K
Graduate Extended Goldbach: every odd number the sum of 5 primes
  • · Replies 1 ·
Replies
1
Views
4K
Graduate Help with Mobius Inversion in Riemann's Zeta Function by Edwards (J to Prime Pi)
  • · Replies 2 ·
Replies
2
Views
7K
Undergrad Factors that influence depth of field
  • · Replies 77 ·
3
Replies
77
Views
7K
Graduate Can't understand this statement about factor rings
  • · Replies 1 ·
Replies
1
Views
2K