Beefy Boxes and Bandwidth Generously Provided by pair Networks
The stupid question is the question not asked
 
PerlMonks  

Re: Re: Factors

by gumby (Scribe)
on Jun 12, 2002 at 21:45 UTC ( #174027=note: print w/ replies, xml ) Need Help??


in reply to Re: Factors
in thread Vampire Numbers

The Quadratic Sieve has running time

O(e^(sqrt(1.125ln(n)ln(ln(n)))))

But with certain improvements (such as using Wiedemann's Gaussian Elimination algorithm over GF(2)), it's running time is given by

O(e^(sqrt(ln(n)ln(ln(n)))))

The Number Field Sieve is better for numbers over 100-digits and has running time

O(e^(1.9223((ln(n))^1/3(ln(ln(n))))^2/3))

Excuse my notation (but TeX would be overkill).

Note: O(stuff) means the magnitude of the running time is < A * stuff for some constant A and all values of n.


Comment on Re: Re: Factors

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://174027]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others cooling their heels in the Monastery: (5)
As of 2015-07-29 07:22 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (260 votes), past polls