Каким алгоритмом можно проверить Большое число на простоту?
Расклад примерно такой. Пусть n -- длина числа, т.е. обычный перебор работает за 2^{c * n}.
1) Вероятностный тест Рабина-Миллера можно реализовать за O(k n^2 log n), где k -- число попыток. Вероятность ложноположительной ошибки 4^-k. При k=100 это значение настолько безумно мало, что скорее в вашей программе найдется критический баг, процессор сделает ошибку в вычислениях и взломщик выиграет в лотерею и все  это одновременно, чем число окажется составным.
2) Детерминированный AKS (en.wikipedia.org/wiki/AKS_primality_test). Работает за O(n^{6 + eps}). Интересен скорее теоретически.
3) Эллиптический тест на простоту (en.wikipedia.org/wiki/Elliptic_curve_primality). Эмпирически работает за O(n^5). Интересен тем, что в случае успеха возвращает сертификат простоты.
Быстро это сделать не выйдет. Не спроста же большие простые числа используют в криптографии. Даже если принять во внимание тот факт, что вы не пытаетесь разложить это добро на множители.