the elliptic curve method in Mathematica's (NumberTheory`PrimeQ`) package says after 20 seconds that 15085130035827878542455979623747888891433345604817588712723282399687865427853871 is prime. An 80 digit number. Should I expect such timing, or does this large integer have special properties that make it easy to get a certificate?
Yes, that integer has a special property that makes it easy: it's small. The technique is often used on numbers having hundreds of digits, maybe even a thousand.
Where angels fear to tread.
I gave it to PARI to factor and it instantaneously said that it was prime. R.
Angels might indeed fear. I expect that PARI's factor uses factorint when given an integer. That "factors the integer n into a product of pseudoprimes... Use isprime on the result if you want to guarantee primality." But isprime has been found to be buggy, in some versions of PARI. I don't know about the latest version. (See http://groups.google.com/groups?selm=3F037240.6ADC5A06%40nk.ca ) -- Don Reble djr@nk.ca