Probabilistic primality test using Chebyshev polynomials of the first ki

Predrag Terzic on Wed, 26 Aug 2020 10:34:41 +0200

[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Probabilistic primality test using Chebyshev polynomials of the first kind

To: "pari-users@pari.math.u-bordeaux.fr" <pari-users@pari.math.u-bordeaux.fr>
Subject: Probabilistic primality test using Chebyshev polynomials of the first kind
From: Predrag Terzic <pedja.terzic@hotmail.com>
Date: Wed, 26 Aug 2020 08:34:38 +0000
Accept-language: en-US
Arc-authentication-results: i=1; mx.microsoft.com 1; spf=none; dmarc=none; dkim=none; arc=none
Arc-message-signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=Y8z+4tB9p9A4vFhB+U8LK81lQNsXA7z+iRa0TqWydz8=; b=X3viF1AxkLrMMKiputEjMU0ANo9EXmU5KMgn/OdrXuP9Fk2WBnyd+aLiYtda63+kBIXWY6xiaTK9a1rVjDbU9Cta7CDXmqwIBpohQntmGdE6UDFXBiUSwYKyFDs40BifjckFRLH1kAfz9s50tz+wHMcQynRFRKAW0o2Zd9AawXVSVoW6PxEFLu0oes52VE6YJbo9hFmNsXSYLA2bp22wtc43HNbmcTtHf7y3AZMVKAXrlO2tBjzncfrmZ+iYU/14CxCpM3Gom08/Lw5+A5uBFtYTWKkijm+bkUfb0pHtcGFMUaopxkdthL4mZPgN6mouNqDA/kEnGhSbUXKGExPfTg==
Arc-seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=icQvTeIYsXnhPwJaUlWXzkHWmJjW5utsFt8/h+VSseg3zniYqftmlOFCOwso++moz21/MeiL0ikGYCQetrrvnGIdLoVvfhHRNgfNgt/AdjKyed6z3Dz/bs9NmmMHERy1NdJk5O5FBCL+9orj/BdK0zThmhZuAEv5o627C+3L3qkESoIyYc+H00NK99SCj35vumzNYfpZUswk42iHhhuwfRTrbz8EvSNWDOy/IuHMohXzESw2B6MW0JF1KJqqXA2gAKOotV0VBOp4W1gzgRqcnXON2q5I5aXWzj8YFFlTmWAK+qfKqtxYqpqjxkxfnf2PCGJ73is2CSRuMLFz5kc6VQ==
Delivery-date: Wed, 26 Aug 2020 10:34:41 +0200
Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=hotmail.com; s=selector1; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=Y8z+4tB9p9A4vFhB+U8LK81lQNsXA7z+iRa0TqWydz8=; b=gUnNhpvtjetCmay7Z7/FztyxBT6lZE5/vY4LaOVjaJ6w4iZ4YG0G/p32HF/iTdrD90cmHplHO3c9yvoJw6q95e6hjPZYX+itUzKdfaLLmkaHWZ/7XFKNEa7bPU9BW0AzGIUTSX6tEvzRcp4WlE98CPfNgGJGA3aB7imrknJbITQ5vQERt9uHtoiPXx1qgwPyKSO1KjUeOvYiHT5Bim2DDPn6xM11F+L4VQS67mh9Z3YJY32+8DJ8vP1X0CM+GwEdAVRhVqLry+XEpqsrKtUCRJ0PsqHQblbdrAFMisS738KD7RtTEAeINHy31RXlBd34I2F1uyDo92fP7XOF7Eqy8w==
Thread-index: AQHWe38hpfZk76azo0CI1zjVOfbJTQ==
Thread-topic: Probabilistic primality test using Chebyshev polynomials of the first kind

Is it possible to implement the following probabilistic primality test in PARI/GP?

input: An odd natural number n

If n is a perfect square output: composite
Find the smallest odd prime number c such that jacobisymbol(c,n)=-1
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. Note that T_n(x) denotes Chebyshev polynomial of the first kind.

Best regards,

Pedja

Follow-Ups:
- Re: Probabilistic primality test using Chebyshev polynomials of the first kind
  - From: Karim Belabas <Karim.Belabas@math.u-bordeaux.fr>

Prev by Date: Re: Question about a clean exit from a gp script
Next by Date: Re: Probabilistic primality test using Chebyshev polynomials of the first kind
Previous by thread: Re: Question about a clean exit from a gp script
Next by thread: Re: Probabilistic primality test using Chebyshev polynomials of the first kind
Index(es):
- Date
- Thread