5
$\begingroup$

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.

Improve this question
$\endgroup$
9
  • $\begingroup$ The general number field sieve runs in time $N^{o(1)}$, and therefore in space $N^{o(1)}$. $\endgroup$
    – Emil Jeřábek
    Commented Jan 7, 2018 at 7:49
  • $\begingroup$ @EmilJeřábek The sieve algorithms are not deterministic. $\endgroup$
    – Aurel
    Commented Jan 7, 2018 at 9:19
  • $\begingroup$ @Aurel but it uses at most $N^{o(1)}$ random bits. Hence there exists a deterministic algorithm that uses $N^{o(1)}$ space that finding suitable "random" bits and so, solving the problem (since it is easy to verify here that the result of an algorithm (factorization) is right). $\endgroup$
    – Alexey Milovanov
    Commented Jan 8, 2018 at 15:04
  • $\begingroup$ @AlexeyMilovanov Good point! But even then, as far as I am aware, the analysis of the number field sieve is based on heuristics, so that would still not give a theorem. Or am I misremembering? $\endgroup$
    – Aurel
    Commented Jan 8, 2018 at 16:36
  • 1
    $\begingroup$ @AlexeyMilovanov, wait, the deterministic algorithm that uses $N^{o(1)}$ space you're describing also uses $2^{N^{o(1)}}$ time, since it has to find a suitable combination of "random" bits, right? I think Dixon's method is not of interest unless there is some way to choose the candidate squares deterministically. $\endgroup$
    – Dan Brumleve
    Commented Jan 8, 2018 at 20:14

1 Answer 1

Reset to default
5
$\begingroup$

Lehman's algorithm uses $O(N^{\frac{1}{3}})$ time $O(\log N)$ space. The algoritm is the following.

0) Check that $n$ is odd and $n > 8$.

1) Check that every $a = 2, \ldots, [n^{\frac{1}{3}}]$ is not a divisor of $n$.

2) For every $k=2, \ldots, [n^{\frac{1}{3}}]$ and for every $d= 0,1 \ldots, [n^{\frac{1}{6}} / (4 \sqrt{k})]$ check is the number $$([\sqrt{4kn}]+d)^2- 4kn $$ a square of an integer. If this is the case then consider $A:=[\sqrt{4kn}]+d$ and $B:= \sqrt{A^2 - 4kn}$. Note that $$A^2 \equiv B^2 (\text{mod } n ).$$ Check: $1 < \text{gcd}(A \pm B, N) < N$.

If we have this inequality then of course we can factorize $N$. Otherwise $N$ is prime by a theorem in the paper.

Improve this answer
$\endgroup$
1

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .