Factoring a large number $x$ by trial division is a lot of work, but if you succeed, you get two factors, which anyone can easily multiply together to make $x$: an easily checked proof that $x$ is in fact composite.
Is there any test for primes that produces a similar artifact? That is: having done the work—trial division or the Lucas-Lehmer test or any other test—and determined that some large $x$ is prime, is there any way to use that work to produce a proof that others can verify without basically doing all the work over again?
(I think this can be made precise, as a complexity question—is there any $S \subseteq \mathbb N$ such that prime testing on $S$ is a harder problem than checking a certain kind of proof—but it's a bit beyond me.)