ISSN:
1432-0622
Keywords:
Lucas sequences
;
Dickson polynomials
;
Dickson pseudoprimes
;
probabilistic prime number test
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
,
Technology
Notes:
Abstract It is known that the Lucas sequenceV n(ξ,c)=an + bn,a, b being the roots ofx 2 − ξx + c=0 equals the Dickson polynomial $$g_n (\xi ,c) = \sum\limits_{i = 0}^{[n/2]} {\frac{n}{{n - 1}}} \left( {\begin{array}{*{20}c} {n - 1} \\ i \\ \end{array} } \right)( - c)^i $$ .ξn−2i Lidl, Müller and Oswald recently defined a number bεℤ to be a strong Dickson pseudoprime to the parameterc (shortlysDpp(c)) if [itgn(b, c)≡b modn for all bεℤ. These numbers seem to be very appropriate for a fast probabilistic prime number test. In generalizing results of the above mentioned authors a criterion is derived for an odd composite number to be ansDpp(c) for fixedc. Furthermore the optimal parameterc for the prime number test is determined.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01387195
Permalink