Vague idea for factorization in time N^(1/5+o(1))
- View SourceCrandall & 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
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.