AKS is an example of a deterministic algorithm which works out whether a number is prime or composite and runs in polynomial time in the number of bits in the number.

https://en.wikipedia.org/wiki/AKS_primality_test

I'm not sure why you would expect this to break all (or any) cryptographic protocols.