Re: Factorisation algorithms

In article <1192584825.140877.253980@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
<matt271829-news@xxxxxxxxxxx> wrote:

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).

The numbers involved are O( N! ); that's O( (N/e)^N ) .

--
Randy Hudson
.

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 ...
    (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)
  • 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)