3
$\begingroup$

Given $a,b\in\Bbb N$ where each $a,b$ is $n$-bits, we can compute $\mathsf{gcd}(a,b)$ in $cn^{1+\epsilon}$ bit operations for some fixed $c\geq1$.

My query is given $N,a,b$ where $a,b$ is $n$-bits and $N$ is $n^{1/\alpha}$ bits with $\alpha\geq2$, is it possible to compute $\mathsf{gcd}(a,b)\bmod N$ in $cn$ bit operations for some fixed $c\geq1$?

Improve this question
$\endgroup$
2
  • $\begingroup$ I haven't had my coffee yet but reducing $a, b$ modulo $N$ and calculating over $\mathbb{N}$ we get complexity $O(N) = O(n^{1/\alpha})$, no? Am I missing something? $\endgroup$
    – Vít Tuček
    Jun 14, 2016 at 6:52
  • 1
    $\begingroup$ @VítTuček First, mod $N$ does not distribute over gcd. Second, division is not known to be doable in linear time. Already reducing one $n$-bit number modulo $N$ will take time $O(\frac{n}{n^{1/\alpha}}M(n^{1/\alpha}))$, where $M(n)$ is the complexity of multiplication of two $n$-bit integers. The best known (for theoretical purposes) multiplication algorithms have $M(n)=n\log n\,2^{O(\log^*n)}$, which is still more than linear. $\endgroup$
    – Emil Jeřábek
    Jun 14, 2016 at 9:02

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.