Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
2  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.