Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Riemann proof effect on factoring composites

  1. Jun 13, 2009 #1
    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. jcsd
  3. Jun 14, 2009 #2

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    Not at all.

    It might improve one or two obscure sieving algorithms, though. Maybe the pseudosquare sieve?
     
  4. Jun 14, 2009 #3
    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.
     
  5. Jun 14, 2009 #4
    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.
     
  6. Jun 14, 2009 #5

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  7. Jun 14, 2009 #6
    Ya I can't figure it out either. Might have to initiate a discussion the talk page.
     
  8. Jun 15, 2009 #7

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    One of the steps in the QS requires you to find square roots mod p, doesn't it?
     
  9. Jun 15, 2009 #8

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    How much time does that take, asymptotically?
     
  10. Jun 15, 2009 #9

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Well, you have to solve x²=N (mod p) for every prime p below the smoothness bound. Sounds like a lot.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Riemann proof effect on factoring composites
  1. Proof of composites (Replies: 3)

Loading...