# Is there a log-space algorithm for divisibility?

Is there an algorithm to test divisibility in space $O(\log n)$, or even in space $O(\log(n)^k)$ for some $k$? Given a pair of integers $(a, b)$, the algorithm should return TRUE if $b$ is divisible by $a$, and FALSE otherwise. I understand that there is no proof that divisibility is not in $L$ since that would imply $P \ne L$ which is open. Also I understand that if there is a nondeterministic algorithm in $O(\log(n)^k)$ then there is a deterministic algorithm in $O(\log(n)^{2k})$, by Savitch's theorem. I believe I've figured out an $L$ algorithm to verify $a*b=c$, and also an $FL$ algorithm to compute $c$ (essentially the method I was taught in grade school, reusing ink when possible), but I haven't been able to adapt it to divisibility. Is such an algorithm for divisibility known?

-
Isn't the euclidean algorithm log space and with the identity $a | b$ iff $\gcd(a,b)=a$, wouldn't this give you a logspace algorithm? – JSchlather Oct 25 '11 at 6:08

1
If so, yes, but I don't know how to make the Euclidean algorithm log-space either. The way I would ordinarily implement it is O(n) space. Note that n ~ log(b) here, so log-space means O(log(log(b))) space. – Dan Brumleve Oct 25 '11 at 6:13

1
The euclidean algorithm is most certainly an overkill; if b divides a, it will be discovered in the first step of the algorithm (where we divide a by b and take the remainder)... – Gadi A Oct 25 '11 at 7:53

1
– Dan Brumleve Oct 25 '11 at 8:40

1
Integer division is known to be in L. Page 22 of the slides “My Favorite Ten Complexity Theorems of the Past Decade II” by Lance Fortnow refers to Chiu 1995, although I cannot locate this reference right now. If you can access Chiu, Davida, and Litow 2001, I am sure that it contains the reference to it. – Tsuyoshi Ito Oct 25 '11 at 13:46
show 5 more comments

## 2 Answers

(This is an updated version of my comment on the question.)

Beame, Cook, and Hoover [BCH86] showed that integer divisibility is in L. More recently, Chiu, Davida, and Litow [CDL01] showed that integer division is also in L.

### References

[BCH86] Paul W. Beame, Stephen A. Cook, and H. James Hoover. Log depth circuits for division and related problems. SIAM Journal on Computing, 15(4):994–1003, Nov. 1986. DOI: 10.1137/0215070

[CDL01] Andrew Chiu, George Davida, and Bruce Litow. Division in logspace-uniform NC1. Theoretical Informatics and Applications, 35(3):259–275, May 2001. DOI: 10.1051/ita:2001119.

-

1
By the way, according to the introduction of [BCH86], there seems to be a folklore O((log n)^2)-space algorithm. – Tsuyoshi Ito Oct 26 '11 at 23:13

2
– Tsuyoshi Ito Oct 26 '11 at 23:41

1
– Kaveh Nov 2 '11 at 16:59

1
@Kaveh: That is true. I did not mention that result in the answer because I wanted to keep the answer simple by focusing on space complexity by a Turing machine. – Tsuyoshi Ito Nov 10 '11 at 21:40

Edited to add: As Gadi points out in a comment, this answer is wrong.

If you have a logspace algorithm to verify $x \times y = z$, then since you're not concerned with running time, you can simply check, for all $c$ with $1 < c \le b$, whether $a \times c = b$.

-

2
I believe he meant that the algorithm is logspace in the sum of lengths of x,y,z. What you suggest is not logspace since writing c takes up space on the work tape. – Gadi A Oct 25 '11 at 12:32
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 20, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9184472560882568, "perplexity_flag": "middle"}