Chebyshev polynomials and higher order Lucas Lehmer algorithm

MaRDI QIDQ6350638zbMATH OpenFDO

Authors Kok Seng Chua

Publication date 6 October 2020

Mathematics Subject Classification ID

Number theory (11-XX)

Abstract: We extend the necessity part of Lucas Lehmer iteration for testing Mersenne prime to all base and uniformly for both generalized Mersenne and Wagstaff numbers(the later correspond to negative base). The role of the quadratic iteration

x i g h t a r r o w x^{2} - 2

is extended by Chebyshev polynomial

T_{n} (x)

with an implied iteration algorithm because of the compositional identity

T_{n} (T_{m} (x)) = T_{n m} (x)

. This results from a Chebyshev polynomial primality test based essentially on the Lucas pair

(o m e g a_{a}, o v e r l i n e {o m e g a}_{a})

,

o m e g a_{a} = a + s q r t a^{2} - 1

, where

a e q 0 p m 1

. It seems interesting that the arithmetic are all coded in the Chebyshev polynomials

T_{n} (x)

.

This page was built for publication: Chebyshev polynomials and higher order Lucas Lehmer algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6350638)