Re: Factorisation algorithms

On Oct 17, 12:29 am, i...@xxxxxxxxx (Randy Hudson) wrote:
In article <1192564600.554428.131...@xxxxxxxxxxxxxxxxxxxxxxxxxxx>,

<matt271829-n...@xxxxxxxxxxx> wrote:
Has anyone ever proved any theoretical bounds on the efficiency of a
general integer factorisation algorithm? Is it still, as far as anyone
knows, possible that a really spectacular advance might be made in
this field?

Upper bounds:

Knuth cites John Douglas Dixon for an algorithm with a running time proven
to be O( N^f(N) ) with f(N) approaching zero as N increases: specifically,
f(N) approaches sqrt( ln(ln(N)) * 8 / ln(N) ). Knuth gives the publication
date as 1978, but I don't see a full cite to the paper.

He also cites Shamir, _Inf. Proc. Letters_ 8 (1979), pp 28-31, for a
demonstration that, if the processing time for an arithmetic operation is
independent of the size of the numbers involved, then N can be factored in
at most O( ln(N) ^2 ) times that processing time.

I have a feeling that this might be a very stupid question, but, even
allowing for the fact that in reality arithmetic takes longer for
larger numbers, isn't O( ln(N) ^2 ) still very much better than any
known algorithm? I'm assuming that the numbers involved are at worst
O(N).


.

Relevant Pages

  • Re: Factorisation algorithms
    ... general integer factorisation algorithm? ... Knuth cites John Douglas Dixon for an algorithm with a running time proven ... if the processing time for an arithmetic operation is ... -- Microsoft voice recognition live demonstration ...
    (sci.math)
  • Re: how to measure time in TI C64xx DSP?
    ... Which function in TI C64xx DSP can return the current system time/ ... I am measure the processing time of an algorithm, ...
    (comp.dsp)
  • Re: GA ver. Parallel tempering
    ... the bulk of processing time will be spent in evaluating potential ... algorithm itself [of course this may not be supportable for search spaces ... sense that evaluations are of necessity performed serially. ... numbers of strings in those regions. ...
    (comp.ai.genetic)
  • Re: Factorisation algorithms
    ... general integer factorisation algorithm? ... Knuth cites John Douglas Dixon for an algorithm with a running time proven ... if the processing time for an arithmetic operation is ...
    (sci.math)
  • Re: Factorisation algorithms
    ... if the processing time for an arithmetic operation is ... running time of an algorithm as a function of of the "size" ...
    (sci.math)