# How to compute GCD efficiently?

I want to compute $A= \langle \text{GCD}(a,j),j=2,3,..,k-1\rangle$ and assume that each value of $j$ is less than $a$. I can compute GCD(a,j), $j=2,3,..,k-1$ and $a \le j$ for single fixed value of $j$ in $\Omega(\log j)$ airthmetic operations.

Easily we can compute set $A$ in $O(k \log k )$ airthmetic operations.

Question : How to compute set $A$ in $O(k)$ many arithmetic operations?

• Is this homework? – Emil Jeřábek supports Monica Jan 25 '18 at 20:51
• @ Emil Jeřábek No I am currently reading a research paper (finite abelian group isomorphism in linear time) in which they have claimed this result. – new Jan 26 '18 at 4:26

you can factor every number in range $j=2,3,..,k-1$ in linear time.
From there, you get an array with some prime divisor (the least for example) of each number in the range. Using that you can solve your problem by filling $A$ in order, and for each new number $j$ you just use the prime divisor of it, find it's greater exponent in $a$, and $j$, and use the previously calculated results in $A$ to get your answer. I'm not totally sure this last part it runs in linear time, but it should be possible.
• Reynaldo is saying that all integers from $2$ to $n$ can be labeled with their smallest prime divisor in time $O(n)$ using a simple sieving algorithm. This is quite different from factoring a given integer in time linear in its bit size. – Sasho Nikolov Jan 26 '18 at 1:40