Primes of the form $a^{p^{n+1}} \pmod {p^n}$

Question

If $F(n) = a^{p^{n-1}} \pmod {p^n}$

where $1 < a < p-1$ be an integer and $p > 5$ a prime, then $F(n)$ has primes of the form $a^{p^{n-1}} \pmod {p^n}$ with $n > 0$. Fortunately, the GP code can find primes of this form as well:

v=[]; for(n=1, 100, if(ispseudoprime(a^(p^(n-1))%p^n), v=concat(v, n)));

However, as $n$ increases the computations take longer, which is fine, but for any particular $a$ and $p$, this would give an error at some point when $n$ is still very small. For example $2^{5^{n-1}} \pmod {5^n}$ is prime for $n = 1, 2, 6, 18, 19, 248$ up to $n = 500$. However running the program gives an error:

v=[]; for(n=1, 100, if(ispseudoprime(a^(p^(n-1))%p^n), v=concat(v, n)));
  ***   at top-level: ...=1,500,if(ispseudoprime(2^(5^(n-1))%5^n),v=co
  ***                                             ^--------------------
  *** _^_: the PARI stack overflows !
  current stack size: 16000000 (3.815 Mbytes)
  [hint] you can increase GP stack with allocatemem()

Is anyone able to create a program (using PARI/GP) which can find primes of the form $F(n) = a^{p^{n-1}} \pmod {p^n}$ for sligtly larger $n$ (say no more than $n=100000$ or $200000$) and verify my claim about $2^{5^{n-1}} \pmod {5^n}$ is prime for $n = 1, 2, 6, 18, 19, 248$ up to $n = 500$. Thanks.

Answer 1

Here is a simplified version of code that virtually does what you want:

[a,p] = [2,5]
v=vector(500, n, ispseudoprime(lift(Mod(a,p^n)^(p^(n-1)))))
select(x->x==1,v,1)

The problem with your code is that it computes $a^{p^{n-1}}$ and then reduces it modulo $p^n$. With $a = 2$, $p = 5$ and $n = 11$, you are computing an integer with more than two million digits AND THEN reducing it modulo $p^n = 48828125$.

My code first tells PARI that $a$ will be an element of $\frac{\mathbb{Z}}{\mathbb{p^nZ}}$ (by saying Mod(a,p^n)). And then we lift the result as an element of $\mathbb{Z}$ using lift.

I also included functions like vector and select, whose documentation you can access by writing ?vector or ?select.