Return to Question

Strassen's factoring algorithm shows that $\text{FACTORING} \in \text{DTIME}(N^{\frac{1}{4}+o(1)})$, but if I'm not mistaken in my analysis it also uses a similar amount of space. By making a trade-off I think it is possible to show $\text{FACTORING} \in \text{DTISP}(N^{k+o(1)}, N^{\frac{1}{2}-k+o(1)})$ for $\frac{1}{4} \leq k \leq \frac{1}{2}$.

On the other hand, trial division up to $\sqrt{N}$ demonstrates $\text{FACTORING} \in \text{DTISP}(N^{\frac{1}{2}+o(1)}, \log(N)^{O(1)})$. The only extra space we need is to keep a counter and perform the divisibility test.

Is there any deterministic factoring algorithm known to be in $\text{DTISP}(N^{k + o(1)}, N^{o(1)})$ for $k \lt \frac{1}{2}$?

I know that there is an $N^{\frac{1}{3}+o(1)}$-time algorithm due to Michael Rubinstein but I can't tell what the space usage would be. This would qualify as an example if the space can be made subexponential.

Otherwise, is trial division the best we can do in $N^{o(1)}$ space?

Strassen's factoring algorithm shows that $\text{FACTORING} \in \text{DTIME}(N^{\frac{1}{4}+o(1)})$, but if I'm not mistaken in my analysis it also uses a similar amount of space. By making a trade-off I think it is possible to show $\text{FACTORING} \in \text{DTISP}(N^{k+o(1)}, N^{\frac{1}{2}-k+o(1)})$ for $\frac{1}{4} \leq k \leq \frac{1}{2}$.

On the other hand, trial division up to $\sqrt{N}$ demonstrates $\text{FACTORING} \in \text{DTISP}(N^{\frac{1}{2}+o(1)}, \log(N)^{O(1)})$. The only extra space we need is to keep a counter and perform the divisibility test.

Is there any deterministic factoring algorithm known to be in $\text{DTISP}(N^{k + o(1)}, N^{o(1)})$ for $k \lt \frac{1}{2}$?

I know that there is an $N^{\frac{1}{3}+o(1)}$-time algorithm due to Michael Rubinstein but I can't tell what the space usage would be. This would qualify as an example if the space can be made subexponential.

Otherwise, is trial division the best we can do in $N^{o(1)}$ space?

We won't be able to prove $\text{FACTORING} \notin \text{DTISP}(\log(N)^{O(1)}, O(\log(N))) = \text{L}$, since that would imply $\text{NP} \neq \text{L}$, an open problem.

Strassen's factoring algorithm shows that $\text{FACTORING} \in \text{DTIME}(N^{\frac{1}{4}+o(1)})$, but if I'm not mistaken in my analysis it also uses a similar amount of space. By making a trade-off I think we can use this to show $\text{FACTORING} \in \text{DTISP}(N^{k+o(1)}, N^{\frac{1}{2}-k+o(1)})$ for $\frac{1}{4} \leq k \leq \frac{1}{2}$.

On the other hand, trial division up to $\sqrt{N}$ demonstrates $\text{FACTORING} \in \text{DTISP}(N^{\frac{1}{2}+o(1)}, \log(N)^{O(1)})$. The only extra space we need is to keep a counter and perform the divisibility test.

Is there any deterministic factoring algorithm known to be in $\text{DTISP}(N^{k + o(1)}, N^{o(1)})$ for $k \lt \frac{1}{2}$?

I know that there is an $N^{\frac{1}{3}+o(1)}$-time algorithm due to Michael Rubinstein but I can't tell what the space usage would be. This would qualify as an example if the space can be made subexponential.

Otherwise, is trial division the best we can do in $N^{o(1)}$ space?

Strassen's factoring algorithm shows that $\text{FACTORING} \in \text{DTIME}(N^{\frac{1}{4}+o(1)})$, but if I'm not mistaken in my analysis it also uses a similar amount of space. By making a trade-off I think it is possible to show $\text{FACTORING} \in \text{DTISP}(N^{k+o(1)}, N^{\frac{1}{2}-k+o(1)})$ for $\frac{1}{4} \leq k \leq \frac{1}{2}$.

On the other hand, trial division up to $\sqrt{N}$ demonstrates $\text{FACTORING} \in \text{DTISP}(N^{\frac{1}{2}+o(1)}, \log(N)^{O(1)})$. The only extra space we need is to keep a counter and perform the divisibility test.

Is there any deterministic factoring algorithm known to be in $\text{DTISP}(N^{k + o(1)}, N^{o(1)})$ for $k \lt \frac{1}{2}$?

I know that there is an $N^{\frac{1}{3}+o(1)}$-time algorithm due to Michael Rubinstein but I can't tell what the space usage would be. This would qualify as an example if the space can be made subexponential.

Otherwise, is trial division the best we can do in $N^{o(1)}$ space?

Strassen's factoring algorithm shows that $\text{FACTORING} \in \text{DTIME}(N^{\frac{1}{4}+o(1)})$, but if I'm not mistaken in my analysis it also uses a similar amount of space.

On the other hand, trial division up to $\sqrt{N}$ demonstrates $\text{FACTORING} \in \text{DTISP}(N^{\frac{1}{2}+o(1)}, \log(N)^{O(1)})$. The only extra space we need is to keep a counter and perform the divisibility test.

Is there any deterministic factoring algorithm known to be in $\text{DTISP}(N^{k + o(1)}, N^{o(1)})$ for $k \lt \frac{1}{2}$?

I know that there is an $N^{\frac{1}{3}+o(1)}$-time algorithm due to Michael Rubinstein but I can't tell what the space usage would be. This would qualify as an example if the space can be made subexponential.

Otherwise, is trial division the best we can do in $N^{o(1)}$ space?

Strassen's factoring algorithm shows that $\text{FACTORING} \in \text{DTIME}(N^{\frac{1}{4}+o(1)})$, but if I'm not mistaken in my analysis it also uses a similar amount of space. By making a trade-off I think we can use this to show $\text{FACTORING} \in \text{DTISP}(N^{k+o(1)}, N^{\frac{1}{2}-k+o(1)})$ for $\frac{1}{4} \leq k \leq \frac{1}{2}$.

On the other hand, trial division up to $\sqrt{N}$ demonstrates $\text{FACTORING} \in \text{DTISP}(N^{\frac{1}{2}+o(1)}, \log(N)^{O(1)})$. The only extra space we need is to keep a counter and perform the divisibility test.

Is there any deterministic factoring algorithm known to be in $\text{DTISP}(N^{k + o(1)}, N^{o(1)})$ for $k \lt \frac{1}{2}$?

I know that there is an $N^{\frac{1}{3}+o(1)}$-time algorithm due to Michael Rubinstein but I can't tell what the space usage would be. This would qualify as an example if the space can be made subexponential.

Otherwise, is trial division the best we can do in $N^{o(1)}$ space?