Deterministically checking whether a large number is prime or composite?

Question

I'm searching for an algorithm to primality test large (like 10²⁰⁰) numbers. Are there any good algorithms?

Ideally, I'd prefer an algorithm that isn't probabalistic.

Note: Numbers have over 50 and less then 200 digits.

Answer 1

If you're looking for a non-probabalistic test, you may want to check out the AKS primality testing algorithm, which runs in roughly O(log⁶ n) time. For the number of digits you have, this is probably feasible.

That said, probabalistic primality tests are extremely good and many have exponentially small error rates. I would suggest using one of those unless there's a good reason not to.

EDIT: I just found this page containing several C++ implementations of AKS. I have no idea whether they work correctly or not, but they might be a good starting point.

Hope this helps!