Re: Factorisation algorithms

matt271829-news@xxxxxxxxxxx wrote:
On Oct 17, 5:23 am, i...@xxxxxxxxx (Randy Hudson) wrote:
In article <1192584825.140877.253...@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,

<matt271829-n...@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 ) .

I'm not sure if you're saying the same thing as Phil Carmody. What is
N? Is it the actual number to be factorised, or is it the "length" of
the number (i.e. the number of decimal digits, or bits)?


While it depends on context, one generally measures the
running time of an algorithm as a function of of the "size"
of the input, i.e., the number of bits it takes to represent the
input. In short, Phil is right, as usual.


Regards,

Rick
.

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 ... the number (i.e. the number of decimal digits, ... While it depends on context, ...
    (sci.math)
  • Re: Factorisation algorithms
    ... if the processing time for an arithmetic operation is ... known algorithm? ... Randy Hudson ...
    (sci.math)
  • Re: Factorisation algorithms
    ... if the processing time for an arithmetic operation is ... I'm not sure if you're saying the same thing as Phil Carmody. ...
    (sci.math)
  • Re: Factorisation algorithms
    ... if the processing time for an arithmetic operation is ... I'm not sure if you're saying the same thing as Phil Carmody. ... the number (i.e. the number of decimal digits, ...
    (sci.math)
Loading