A useful thing to find would be a CUDA (or, ideally, an OpenCL, which runs on both nVidia and AMD) program that performs fast modular exponentiation of large numbers (i.e. larger than 64 bits; the numbers needed are on the order of 256 bits or larger). Modular exponentiation is at the heart of both the Fermat Primality Test and the various forms of the Euler Lagrange Lichfitz Test.
This is spot on. Both luke-jr and I have both had success replacing Openssl's default big number exponentiation function with the one from GMP. I recommend perhaps people look there
That's enough hints for now!
Will
Far from enough hints
People from Tsukuba University already implemented GMP on CUDA:
http://www.hpcs.cs.tsukuba.ac.jp/~nakayama/cump/index.php?The%20CUDA%20Multiple%20Precision%20Arithmetic%20Library
If someone wants to roll his own implementation here's where he can start:
http://individual.utoronto.ca/haojunliu/courses/ECE1724_Report.pdf
If somebody already implemented primecoin client on GPU he should not have that advantage for too long or he can kill a coin mining. From some comparisons I've seen advantage can be even bigger than in BTC case.