Primality proving for 'near-powers'

[CRGreathouse]

Is there a method for proving the primality of large numbers of the form
a^b+c
where a and c are of similar size? I'm looking for something faster than a general primality prover like PRIMO, or a comment like "I know of no such method".

[Hurkyl]

That's exactly what the special number field sieve (http://en.wikipedia.org/wiki/Special_number_field_sieve) was designed to do.

[CRGreathouse]

I'm looking to prove primality, not factor. I'm looking for an analogue of SNFS for primality.

[Hurkyl]

Good point. Sorry 'bout that.

[CRGreathouse]

Good point. Sorry 'bout that.

:uhh: Frankly, I did *exactly* the same thing myself: I said "that's a perfect SNFS form!" and Googled to find a good client... until I realized that I was searching for the wrong thing.

Can you verify that you know of no algorithm/program/whatever to do this quickly? That way, if I resort to some standard method like ECPP, I won't feel like I'm doing it an unreasonably hard way.