Skip to main content
added 4 characters in body
Source Link
kodlu
  • 10.4k
  • 2
  • 36
  • 55

For a number $n$ that has $b=1+\log_2 n=O(\ln n)$ bits NFS has complexity of the order $$ \exp\left\{(c+o(1)) (\ln n)^{1/3} (\ln \ln n)^{2/3}\right\} $$

which is subexponential when compared to the input size in bits. An exponential algorithm would have complexity of the order $$ \exp(c b)=\exp(c \ln n). $$

If the unusual term factorial time means an algorithm takes time asymptotic to $b!$$\ln b!$ for the input size $b$ the answers to your questions are both yes.

For a number $n$ that has $b=1+\log_2 n=O(\ln n)$ bits NFS has complexity of the order $$ \exp\left\{(c+o(1)) (\ln n)^{1/3} (\ln \ln n)^{2/3}\right\} $$

which is subexponential when compared to the input size in bits. An exponential algorithm would have complexity of the order $$ \exp(c b)=\exp(c \ln n). $$

If the unusual term factorial time means an algorithm takes time asymptotic to $b!$ for the input size $b$ the answers to your questions are both yes.

For a number $n$ that has $b=1+\log_2 n=O(\ln n)$ bits NFS has complexity of the order $$ \exp\left\{(c+o(1)) (\ln n)^{1/3} (\ln \ln n)^{2/3}\right\} $$

which is subexponential when compared to the input size in bits. An exponential algorithm would have complexity of the order $$ \exp(c b)=\exp(c \ln n). $$

If the unusual term factorial time means an algorithm takes time asymptotic to $\ln b!$ for the input size $b$ the answers to your questions are both yes.

Source Link
kodlu
  • 10.4k
  • 2
  • 36
  • 55

For a number $n$ that has $b=1+\log_2 n=O(\ln n)$ bits NFS has complexity of the order $$ \exp\left\{(c+o(1)) (\ln n)^{1/3} (\ln \ln n)^{2/3}\right\} $$

which is subexponential when compared to the input size in bits. An exponential algorithm would have complexity of the order $$ \exp(c b)=\exp(c \ln n). $$

If the unusual term factorial time means an algorithm takes time asymptotic to $b!$ for the input size $b$ the answers to your questions are both yes.