Is it deterministically checked whether a large number is simple or compound?

Question

I am looking for an algorithm to test the simplicity of large (e.g. ^10,200 ) numbers. Are there any good algorithms?

Ideally, I would prefer an algorithm that is not likely.

Note. Numbers have more than 50 and less than 200 digits.

Answer 1

If you are looking for a non-random test, you can check the AKS authentication testing algorithm , which runs at approximately 0 (log ⁶ n). For the number of digits you have, this is possible.

However, probabilistic primitiveness tests are extremely good, and many of them have exponentially small error rates. I would suggest using one of them if there is no good reason not to.

EDIT : I just found this page containing several CKS AKS implementations . I have no idea if they work correctly or not, but they can be a good starting point.

Hope this helps!

Answer 2

Usually we would use a likely simple test. I recommend the BPSW , which you can follow the Frobenius test and / or some random Miller-Rabin tests if you want more confidence. This will be fast and perhaps more confident than doing some evidence-based implementations.

Suppose you say that is not enough. Then you really want to use ECPP and get a certificate. Reasonable implementations of Primo or ecpp-dj . They can prove the correctness of 200-digit numbers in a second and return a certificate that can be independently verified.

APR-CL is another smart method. The disadvantage is that it does not return a certificate, so you trust the implementation - you get a yes or no result, which is deterministic if the implementation was correct. Pari / GP uses APR-CL with the isprime command, and David Cleaver has a great open source implementation: mpz_aprcl . These implementations had some code review and daily use in various software, so it should be fine.

AKS is a terrible method that can be used in practice. It does not return a certificate, and it is not difficult to find broken implementations that completely defeat the point of using the proof method against good probable simple tests in the first place. It is also terribly slow. 200-bit digits have already passed the practical moment for any implementation that I know of. The aforementioned ecpp-dj software is “fast”, so you can try it, and there are quite a few other implementations that you can find.

For some idea of ​​speed, here are a few implementation examples. I do not know any implementations of AKS, APR-CL or BPSW, which are faster than shown (comment if you know one). Primo starts up a bit slower than ecpp-dj shows, but the numbers are 500 or so faster and it has a better slope. This is the program of choice for large inputs (2,000-30,000 digits).