Somer–Lucas pseudoprime
   HOME

TheInfoList



Click Here for Items Related To - Somer–Lucas pseudoprime
OR:
Somer–Lucas pseudoprime on:   [Wikipedia]   [Google]   [Amazon]

In mathematics, in particular
number theory Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and integer-valued functions. German mathematician Carl Friedrich Gauss (1777–1855) said, "Mat ...
, an
odd Odd means unpaired, occasional, strange or unusual, or a person who is viewed as eccentric. Odd may also refer to: Acronym * ODD (Text Encoding Initiative) ("One Document Does it all"), an abstracted literate-programming format for describing X ...
composite number A composite number is a positive integer that can be formed by multiplying two smaller positive integers. Equivalently, it is a positive integer that has at least one divisor other than 1 and itself. Every positive integer is composite, prime, ...
''N'' is a Somer–Lucas ''d''-
pseudoprime A pseudoprime is a probable prime (an integer that shares a property common to all prime numbers) that is not actually prime. Pseudoprimes are classified according to which property of primes they satisfy. Some sources use the term pseudoprime to ...
(with given ''d'' ≥ 1) if there exists a nondegenerate
Lucas sequence In mathematics, the Lucas sequences U_n(P,Q) and V_n(P, Q) are certain constant-recursive integer sequences that satisfy the recurrence relation : x_n = P \cdot x_ - Q \cdot x_ where P and Q are fixed integers. Any sequence satisfying this rec ...
U(P,Q) with the discriminant D=P^2-4Q, such that \gcd(N,D)=1 and the rank appearance of ''N'' in the sequence ''U''(''P'', ''Q'') is :\frac\left(N-\left(\frac\right)\right), where \left(\frac\right) is the
Jacobi symbol Jacobi symbol for various ''k'' (along top) and ''n'' (along left side). Only are shown, since due to rule (2) below any other ''k'' can be reduced modulo ''n''. Quadratic residues are highlighted in yellow — note that no entry with a ...
.


Applications

Unlike the standard
Lucas pseudoprime Lucas pseudoprimes and Fibonacci pseudoprimes are composite integers that pass certain tests which all primes and very few composite numbers pass: in this case, criteria relative to some Lucas sequence. Baillie-Wagstaff-Lucas pseudoprimes Baill ...
s, there is no known efficient primality test using the Lucas ''d''-pseudoprimes. Hence they are not generally used for computation.


See also

Lawrence Somer, in his 1985 thesis, also defined the Somer d-pseudoprimes. They are described in brief on page 117 of Ribenbaum 1996.


References

* * * * {{DEFAULTSORT:Somer-Lucas Pseudoprime Pseudoprimes