Re: Probabilistic primality test using Chebyshev polynomials of the first kind

[Karim Belabas <Karim.Belabas@math.u-bordeaux.fr>]

* Predrag Terzic [2020-08-26 10:34]:
> Is it possible to implement  the following probabilistic primality test in PARI/GP?
> 
> input: An odd natural number n
> 
>   1.  If n is a perfect square output: composite
>   2.  Find the smallest odd prime number c such that jacobisymbol(c,n)=-1
>   3.  If T_n(1+sqrt(c))==1-sqrt(c) (mod n) then output: probably prime , else output: composite
> 
> The first two steps are not a problem, the third step is problematic. I
> don't know how to implement a congruence that involves square roots.

Use sqrtc = Mod(x, Mod(x^2-c, n));

There is another issue since polchebyshev is only implemented for n < 2^64.
You will have to implement the two-term recurrence relation as well in order
to evaluate T_n(1 + sqrt(c))). 

Cheers,

    K.B.
--
Karim Belabas, IMB (UMR 5251)  Tel: (+33) (0)5 40 00 26 17
Universite de Bordeaux         Fax: (+33) (0)5 40 00 21 23
351, cours de la Liberation    http://www.math.u-bordeaux.fr/~kbelabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux.fr/  [PARI/GP]
`