Parallel determination of primitive root of n-th Euclid prime

par2.gp

check(En, n, phi, g, i)={
  parfor(i=1, n, lift(Mod(g, En)^(phi / prime(i))) == 1, r, if(r, return(0)));
  1
}

euclid_prime_find_root(n) = {
  my(En = vecprod(primes(n)) + 1, phi = En - 1);

  for(g=2, En-1,
    if(lift(kronecker(g, En))==-1,
      if(check(En, n, phi, g, i), return(g));
    );
  );
}

Demonstration on 457th Euclid prime,
and demonstration of huge speedup over GP znprimroot() (which has to factor N-1 first)
and sequential seq.gp gist below:

hermann@7950x:~$ gp -q par2.gp 
? #
   timer = 1 (on)
? euclid_prime_find_root(457)
cpu time = 14,400 ms, real time = 1,216 ms.
31
? #digits(prime(457)#+1)
1368
? 

hermann@7950x:~$ gp -q seq.gp 
? #
   timer = 1 (on)
? euclid_prime_find_root(457)
cpu time = 8,368 ms, real time = 8,370 ms.
31
? lift(znprimroot(prime(457)#+1))
cpu time = 1min, 34,734 ms, real time = 1min, 34,744 ms.
31
?