Re: Factorisation algorithms

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

On Oct 19, 12:52 am, Gerry Myerson <ge...@xxxxxxxxxxxxxxxxxxxxxxxxx>
wrote:
In article <1192733534.602928.281...@xxxxxxxxxxxxxxxxxxxxxxxxxxx>,





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

My understanding is that the Shamir proposal factors N
by doing arithmetic with numbers on the order of N-factorial,
which is to say numbers with roughly N log N digits.

I'm sorry to keep banging on about this, but I still don't understand
it. The original claim for the algorithm was that factorisation is
O(log(N)^2) if arithmetic operations are independent of the size of
the numbers involved. However, we need to do arithmetic on numbers
with O(N*log(N)) digits. Let's say we can do arithmetic on n-digit
numbers in O(n^2). Then we seem to essentially have factorisation in
O(log(N)^2 *(N*log(N))^2).

If N is the size of the input (i.e. essentially the logarithm of the
number being factorised), as everyone seems to be saying, then this
algorithm still seems much better than anything available. Are you
sure N isn't the actual number to be factorised?

If by "you" you mean me, then look at what I wrote:
"the Shamir proposal factors N"
so not only am I sure that N is the number to be factored
(insofar as I'm sure of anything on this topic),
but I said exactly that.

--
Gerry Myerson (gerry@xxxxxxxxxxxxxxx) (i -> u for email)
.

Relevant Pages

  • Re: Factorisation algorithms
    ... if the processing time for an arithmetic operation ... which is to say numbers with roughly N log N digits. ... The original claim for the algorithm was that factorisation is ...
    (sci.math)
  • Re: Factorisation algorithms
    ... if the processing time for an arithmetic ... which is to say numbers with roughly N log N digits. ... The original claim for the algorithm was that factorisation is ...
    (sci.math)
  • Re: Factorisation algorithms
    ... if the processing time for an arithmetic ... which is to say numbers with roughly N log N digits. ... The original claim for the algorithm was that factorisation is ...
    (sci.math)
  • Re: Factorisation algorithms
    ... if the processing time for an arithmetic ... which is to say numbers with roughly N log N digits. ... The original claim for the algorithm was that factorisation is ...
    (sci.math)
  • Re: Congruence based factoring algorithm, revised
    ... Here is the corrected algorithm. ... You missed a trick here James. ... 500 trials, 0 misfactors found. ... Average a's tried per factorisation: ...
    (comp.theory)