12
$\begingroup$

What is the most efficient (in time complexity) algorithm known nowadays for the Divisibity Decision Problem: given two integers, say $a$ and $b$, does $a$ divide $b$? Let it be clear that what I ask for is not (necessarily) an algorithm for Remainder Calculation. I just want to know whether $a$ divides $b$ or not.

Thanks and regards, Leandro

  • 0
    Thanks, Hurkyl, but it's not clear for me, reading the gmp documentation, what algorithm they use, nor it's clear its time complexity. My question is whether exists or not some recent algorithm for Divisibility with time complexity less than $O(m\log m\log\log m)$, where $m$ is the number of bits of $\max\{a,b\}$.2012-12-18

0 Answers 0