Скорость работы вероятностного алгоритма - примерно C*L^2*log(L), где L - длина проверяемого числа, C - количество тестов (вероятность false positive будет не больше 4^(-C)). Это если использовать сверхбыстрые алгоритмы умножения. Для миллиона знаков время получится несколько триллионов - и там всё зависит от константы. Будут это часы, или дни - сказать трудно.
Если тестируемое число равно произведению нескольких известных простых чисел + 1, то проверка может дать гарантированный результат, но в этом случае C равно количеству чисел, входящих в произведение.
