Re: Factorisation algorithms
- From: ime@xxxxxxxxx (Randy Hudson)
- Date: Tue, 16 Oct 2007 23:29:14 +0000 (UTC)
In article <1192564600.554428.131190@xxxxxxxxxxxxxxxxxxxxxxxxxxx>,
<matt271829-news@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.
--
Randy Hudson
.
- Follow-Ups:
- Re: Factorisation algorithms
- From: matt271829-news
- Re: Factorisation algorithms
- References:
- Factorisation algorithms
- From: matt271829-news
- Factorisation algorithms
- Prev by Date: Re: Heuristic probability quickie.
- Next by Date: Re: negative base raised to fractional exponent
- Previous by thread: Re: Factorisation algorithms
- Next by thread: Re: Factorisation algorithms
- Index(es):
Relevant Pages
|
