Divisibility Problem: Fast Algorithm for Large Integers A and B

[mhill]

given two integers A and B that are very big is there any 'fast' algorithm to calculate the remainder of the division \frac{A}{B} or in other similar words to say if B divides or not A thanks.

 

[CRGreathouse]

How big? Are the numbers likely to have small prime factors?
For numbers under 100 digits, any reasonable program can do the calculation 'in the blink of an eye'.

Newton's method can be used to divide two numbers in time O(n^{1.585}) using Karatsuba multiplication.

For truly huge numbers (10,000 to 100,000 or more digits), FFT-based multiplication algorithms like Strassen's algorithm or the new Furer's algorithm provide quasilinear division using Newton's method.

I don't know of the success, in general, of higher-order methods for division, but I can't imagine any can outdo the O(n\log n\log\log n) of the FFT methods I mentioned.