Beefy Boxes and Bandwidth Generously Provided by pair Networks
XP is just a number

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


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


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


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.