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? W. quote When \!\(TraditionalForm\`n\) is larger than the value of the option SmallPrime, ProvablePrimeQ uses the Atkin\[Hyphen]Morain test as described above. This primality proving algorithm is suboptimal if the number is within the range of efficient factoring algorithms. When this is the case, a method of V.\[NonBreakingSpace]Pratt is preferable: V.\[NonBreakingSpace]Pratt, \[OpenCurlyDoubleQuote]Every Prime Has a Succinct Certificate,\[CloseCurlyDoubleQuote] SIAM Journal of Computation 4 (1975), pages 214\[Dash]220. An implementation of this algorithm in Mathematica is described in S. Wagon, Mathematica in Action, W. H. Freeman, 1991, Section\[NonBreakingSpace]8.7. end quote