What's the most efficient algorithm for Divisibility?

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

-
How are your integers stored? –  Phira Dec 18 '12 at 16:05
mpz_divisible_p –  Hurkyl Dec 18 '12 at 16:51
Phira, my integers are stored like binary strings. –  Leandro Zatesko Dec 18 '12 at 18:09
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\}$. –  Leandro Zatesko Dec 18 '12 at 18:32