Первое, что приходит в голову -- быстро поделить одно целое число на другое, если известно, что оно делится нацело. Или, еще лучше, корень извлечь, какой-нибудь там кубический (в тех же предположениях существования целочисленного корня). Не знаю, насколько эффективны такие p-адические (2-адические? 10-адические?) алгоритмы, но, по крайней мере, кажется, что они должны быть эффективнее аналогичных вещественных.