Loading ...
Sorry, an error occurred while loading the content.

Vague idea for factorization in time N^(1/5+o(1))

Expand Messages
  • WarrenS
    Crandall & Pomerance s book in addition to explaining how N^(1/4+o(1)) is the fastest known time bound for a rigorous deterministic factoring algorithm, also
    Message 1 of 1 , Dec 17, 2011
    View Source
    • 0 Attachment
      Crandall & Pomerance's book in addition to explaining how N^(1/4+o(1))
      is the fastest known time bound for a rigorous deterministic factoring algorithm,
      also explains that there is another deterministic algorithm, invented
      by D.Shanks and based on the theory of "class numbers,"
      which runs in time N^(1/5+o(1))
      PROVIDED the extended Riemann hypothesis is true.

      [This was turned into an N^(1/5+o(1)) EXPECTED time randomized algorithm
      not needing to assume the ERH, by
      Anitha Srinivasan: Computations of class numbers of real quadratic fields,
      Mathematics of Computation 67,223 (1998) 1285-1308
      http://www.ams.org/journals/mcom/1998-67-223/S0025-5718-98-00965-X/S0025-5718-98-00965-X.pdf .]

      D.Shanks: Class number, a theory of factorization, and genera, Proc. Symp. Pure Math.,
      Amer. Math. Soc. 20 (1971) 415-440.
      R. A. Mollin & H. Williams: Computation of the class number of real quadratic fields,
      Utilitas Math., 41 (1992) 259-308.
      H. W. Lenstra, J:, On the calculation of regulators and class numbers of quadratic fields,
      Lond. Math. Soc. Lect. Note Ser, 56 (1982) 123-150.
      R. J. Schoof: Quadratic fields and factorization, Computational methods in number theory,
      (H. W. Lenstra, Jr., and R.Tijdeman, eds.), Math.Centrum, Number 155, part II, Amsterdam
      1 (1983) 235-286.

      Anyhow, I have an idea.
      It seems plausibly likely to me that one can prove a Shanks-like algorithm will factor N in
      N^(1/5+o(1)) time under the assumption the ERH is FALSE.

      This combined with Shanks' result on the assumption ERH is true,
      will yield an unconditional rigorous deterministic N^(1/5+o(1))-time
      factoring algorithm, a new record, which will work on two paths simultaneously, one assuming ERH true, other assuming it false.

      These authors employ certain sums and products representing Dirichlet L-functions
      which they evaluate approximately. Given the ERH, they don't have to work too hard to get the approximation good enough. However, it seems to me if the ERH is false, then
      these sums will also be well-behaved, just in a different sense.

      I warn you this whole approach does not look attractive from the standpoint of
      producing a factoring program you'd want to program & use (even if it is valid).
      It probably would be purely of theoretical interest.
    Your message has been successfully submitted and would be delivered to recipients shortly.