That makes me think that their probable prime implementation isn't that great or else that they're losing a ton of efficiency to the Javascript interpreter.

That makes me think that their probable prime implementation isn't that great or else that they're losing a ton of efficiency to the Javascript interpreter. $ time python -c 'import gmpy; gmpy.next_prime(2**2500)' real 0m0.443s Was it taking a lot longer than that for you? Edit: I can see that there is an element of luck in terms of how many candidates you have to look at, but I'm still seeing everything in this size range take under 2 seconds. Maybe it's a question of what probability of error you're accepting from the test?