Here's a puzzling quote (from this article) considering primality testing is known to be in P (even though it's like n13 or something, last I heard):
Even so, it is mathematics that will gain the most [if the Riemann hypothesis were to be proved]. "Right now, when we tackle problems without knowing the truth of the Riemann hypothesis, it's as if we have a screwdriver," says Sarnak. "But when we have it, it'll be more like a bulldozer." For example, it should lead to an efficient way of deciding whether a given large number is prime. No existing algorithms designed to do this are guaranteed to terminate in a finite number of steps.