View source for Special number field sieve (First Category Integer Factoring Integer Factoring)

== Time Complexity == 

$O(exp(({1}+o({1})$)({32}n/{9})^{({1}/{3})}(log n)^{({2}/{3})}) heuristically?

== Space Complexity == 

$O(n^{2/3})$ bits

(http://www.ams.org/notices/199612/pomerance.pdf)

== Description == 

For integers of the form $r^e \pm s$, for r and s relatively small

== Approximate? == 

Exact

== Randomized? == 

No, deterministic

== Model of Computation == 



== Year == 

1940

== Reference ==