Re: riemann hypothesis needed to factor numbers?

Michael Jørgensen wrote:
Anyway, the text mentioned the Goldbach conjecture and the Riemann hypothesis (BTW, what is the difference between hypothesis and conjecture?).

If you go on to derive conclusions under the assumption that it's true, then it's a hypothesis; if you don't, then it's a conjecture. That's how I think of it, anyway.

The text continued by mentioning that if one day the Riemann hypothesis could be proved then it could be used to factor numbers more quickly.

As others have said, I don't think RH implies the existence of a fast factoring algorithm. I think there are fast primality testing algorithms which depend on RH, but we already have fast-enough algorithms that don't. (Fast enough, that is, for the only useful application of primality testing, which is in cryptography.)

I mean, we could just assume that the RH is true, and develop an algorithm based on that assumption. Then either the algorithm works (i.e. is fast) or it doesn't.

I think that such algorithms would tend to be fast in practice for the same reason that the nontrivial zeros of the zeta function are on the critical line "in practice". A proof of RH would only be useful for proving an asymptotic efficiency bound.

-- Ben
.

Relevant Pages

  • Re: Provability
    ... for the Poincare conjecture which has been proven. ... we can write down an algorithm which does ... If some algorithm A_t is a polynomial-time algorithm for ... but in principal the Levin ...
    (sci.math)
  • Re: Important Paper for Anti-Relativityists
    ... discrete system of interacting particles by an algorithm. ... The conjecture is explained in two ... Newton's physics and modern physics." ...
    (sci.physics)
  • Re: Important Paper for Anti-Relativityists
    ... discrete system of interacting particles by an algorithm. ... method of predicting measurements from the model. ... The conjecture is explained in two ... Newton's physics and modern physics." ...
    (sci.physics)
  • Re: RC4 on AMD64
    ... > Look how long it took to find some of the (easy to avoid) ... > the complexity of the algorithm. ... Tom's conjecture: Anyone can come up with wild conclusions. ... look how easy it was to prove security against LC/DC and so ...
    (sci.crypt)
  • Re: "Sorting" assignment
    ... If you only learn the beautiful side of programming, ... but won't work in practice'", Kant replied to certain of his critics ... elegance and beauty from the fact that we developed this algorithm ... edumocational theory in which the students shall try, ...
    (comp.programming)