1.0  Basic Propositions on Symmetric Pseudoprimes

 

1.1  Nomenclature and Definitions

 

Let Z[x] denote the set of polynomials (of finite degree) with integer coefficients.  For any given monic polynomial f(x) Î Z[x] of degree d, let Z[x]f denote the elements of Z[x] modulo f.  This signifies that two elements u(x), v(x) of  Z[x]  are equivalent in  Z[x]f  if and only if  u(x) - v(x)  is divisible by f(x). 

 

Proposition 1:  Each element of Z[q]f has a unique expression of degree d-1.

 

Proof:  Letting the modulus polynomial f(x) be

 

 

we see that any power of x greater than or equal to d can be expressed in terms of lower powers of x while preserving equivalence in  Z[x]f  by making the substitution

 

 

Thus, every element of Z[x]f can be reduced to a polyomial of degree £ d-1.  The reduced polynomial is unique because if any two (distinct) such polynomials were equivalent, it would imply that their difference, a non-vanishing polynomial of degree d-1, is divisible by f(x), which is impossible. à

 

Thus each element of Z[x]f can be expressed in the form

 

 

where ai Î Z.  If the coefficients ak are considered as elements of Zn (that is, the integers modulo n), then the set of polynomials of this form is denoted as Zn(x)f .  For any  u,v Î Z[x]  and n Î Z, the notation u = v (mod f,n) signifies that u(x) and v(x) are equivalent elements of Zn[x]f .

 

The following generalization of Fermat's Little Theorem is the basis for the definition of a symmetric pseudoprime:

 

Proposition 2:  If p is a prime, then f(xp) = 0 (mod f,p).

 

Proof:  Raising both sides of the congruence f(x) = 0 (mod f,p) to the power p, noting that all cross-product coefficients in the multinomial expansion are divisible by p, and that cjp = cj (mod p), we have the result. à

 

Definition 1:  A positive composite integer N such that f(xN) = 0 (mod f;N) is called a symmetric pseudoprime relative to f.

 

An alternative definition in terms of symmetric functions is discussed in Section 1.3.

 

 

1.2  Basis Sequence Computations

 

For any non-negative integer n there is a unique set of integers bk(n) such that

 

 

For each k the sequence of integers bk(n) (n = 0,1,2,...) is called a basis sequence of f.  Each basis sequence satisfies the fundamental recurrence relation of f

 

 

with the initial values

 

for j = 0, 1,.., d-1.

 

Proposition 3:  For any non-negative integers n1, n2,..., nj and r, and for k = 0, 1,.., d-1, we have the identity

 

 

where summation from 0 through d-1 is implied over each ai.

 

Proof:  By direct multiplication of the basis representations of each power of x we have

 

 

where Bg equals the sum of all products of the form

 

 

with a1 + a2 + ... + aj = g. Substituting the representation for each power of x on the right side of the previous expression, the coefficient of xk in the representation of  is given by

 

 

Clearly, this equality still holds if the argument of the left hand side and of the first term in the summation are both increased by any integer r. à

 

Notation:  Throughout this paper, whenever a Greek symbol appears both as a sequence index and in a sequence argument in a single product, summation over that symbol from 0 through d-1 is implied.  Similarly, whenever a Latin symbol appears both as an index and an argument in a given product, summation over that symbol from 0 through d is implied (except when other summation limits are explicitly specified).

 

For computational purposes, a useful special case of (2) can be expressed using the index-argument convention as

 

 

By applying this formula log2N times, with r equal to either 0 or 1 at each step according to the binary bits of N, we can efficiently compute the basis elements bj(N) (j = 0, 1,.., d-1).  The quantities bj(a+b+r) are fixed constants for any given recurrence, so the only full multiplications required in each evaluation of (3) are the d(d+1)/2 distinct products of the form ba(n)bb(n).

 

Once the basis elements bj(N) have been determined, the basis representations of x2N, x3N,.., xdN can be found by applying the formula

 

 

with k = 2, 3,.., d.  With these we can determine whether N satisfies the congruence f(xN) = 0 (mod f,N), which is equivalent to the set of congruences

 

 

If N satisfies (4), then either N is a prime or N is a symmetric pseudoprime relative to f.

 

 

1.3  Elementary Symmetric Functions

 

Let q1, q2,... qd denote the complex roots of f, let fn denote the monic polynomial whose roots are the nth powers of the roots of f, and let cj(n) denote the coefficient of xd-j in fn(x).  The jth elementary symmetric function of the roots of fn is defined as the sum of all products of the roots taken j at a time, and is denoted by sj(n).  (For convenience we define s0(n) = 1 for all n.)  It follows that

 

 

Hereafter, whenever s(n) is written without subscript, it is understood to signify the first symmetric function, i.e., the sum of the kth powers of the roots of fn.

 

The index-argument summation convention previously defined for basis sequences also applies to both of the sequences sj(n) and cj(n), and to combinations of these sequences.  For example, s(a)ba(n) signifies the sum

 

 

Proposition 4:  The integer N is a prime or a symmetric pseudoprime relative to f if and only if sj(N) = sj(1) (mod N) for j = 0, 1, .., d.

 

Proof:  The condition sj(N) = sj(1) (mod N) for j = 0, 1,.., d implies that the coefficients of f and fN are congruent (mod N).  Therefore, since each xN is a root of fN, we also have f(xN) = 0 (mod f,N), proving that N is a symmetric pseudoprime relative to f.  Conversely, if N is a symmetric pseudoprime relative to f, we have f(qiN) = 0 (mod f,N) for each root qiN of fN, which implies that the coefficients of f are congruent to the coefficients of fN (mod N). à

 

In view of Proposition 4 we have the following alternative definition of symmetric pseudoprimes:

 

Definition 1':  Given a monic polynomial f of degree d with integer coefficients, a symmetric pseudoprime relative to f is defined as a positive composite integer N such that every elementary symmetric function of the Nth powers of the roots of f is congruent (mod N) to the same function of the first powers.

 

We will occassionally compare symmetric pseudoprimes with "ordinary" pseudoprimes, defined as follows:

 

Definition 2:  Given a monic polynomial f of degree d with integer coefficients, an ordinary pseudoprime relative to f is defined as a positive composite integer N such that the sum of the Nth powers of the roots of f is congruent (mod N) to sum of the first powers.

 

For example, if q1, q2, q3 are the roots of a cubic polynomial f, then an ordinary pseudoprime relative to f is a composite integer N co-prime to 6 and such that

 

 

whereas a symmetric pseudoprime relative to the same cubic f is a composite integer N such that

 

 

Proposition 5:  If N is a prime or a symmetric pseudoprime relative to f, we have sj(kN) = sj(k) (mod N) (j = 0, 1, .., d) for every positive integer k.

 

Proof:  The elementary symmetric functions of qik (i = 1, 2,.., d) can be expressed as polynomials in the elementary symmetric functions of the values qi.  Similarly, the elementary symmetric functions of qiNk (k = 1, 2,.., d) can be expressed by the same polynomials in the elementary symmetric functions of the values qiN.  By Proposition 4 each elementary symmetric function of the qi is congruent (mod N) to the same function of the qiN, so the elementary symmetric functions of the values qik are all congruent (mod N) to the same functions of the values qiNk. à

 

Proposition 6:  A positive composite integer N co-prime to d! is a symmetric pseudoprime relative to f  if and only if s(kN) = s(k) (mod N) for k = 1, 2,.., d.

 

Proof:  The necessity of the condition follows immediately from Proposition 5.  To prove sufficiency, consider "Newton's relations"

 

 

for any integer n.  Given the set of values s(n), s(2n),... s(dn) modulo some positive integer M, these relations uniquely determine the coefficients of fn (mod M), provided that M is co-prime to d! (to ensure that all the divisions by j are unique modulo M).  Therefore, if s(kN) = s(k) (mod N) for k = 1, 2,.., d, it follows that the coefficients of f are congruent (mod N) to the coefficients of fN, which proves that for any u Î Z[x] we have f(u) = fN(u) (mod f,N).  In particular,  f(qN) = fN(qN) = 0  (mod f,N), so N is a symmetric pseudoprime relative to f. à

 

 

1.4  Reversible Sequences

 

If the constant coefficient cd of f equals +1 or -1, then the values of c1(k) are integers for all integers k, positive and negative.  In this case, the sequence c1(k) and the polynomial f are both called reversible.

 

Proposition 7:  If N is a prime or a symmetric pseudoprime relative to f, and the coefficient cd of f is co-prime to N, then sj(kN) = sj(k) (mod N) (j = 0, 1,.., d) for every integer k, positive and negative.

 

Proof:  Since cd is co-prime to N, the fundamental recurrence relations can be solved uniquely for s(n-d) and s(N(n-d)) respectively, and the corresponding coefficients remain congruent (mod N).  Therefore, since the two sequences have congruent initial values and congruent recurrence coefficients (mod N), the sequences are entirely congruent (mod N) in both directions, positive and negative.  It follows from equation (5) that the coefficients of the polynomials fn and fNn are congruent for all n, positive and negative. à

 

In particular, Proposition 7 applies to every reversible sequence for any prime or symmetric pseudoprime N, because cd = ±1 is obviously co-prime to N.

 

Proposition 8:  If f is reversible, then an odd positive composite integer N co-prime to (d-1)! is a symmetric pseudoprime relative to f if and only if s(kN) = s(k) (mod N) for k = 1, 2,.., d-1.

 

Proof:  The necessity follows from Proposition 7.  To prove sufficiency, note that the d-1 specified congruences, together with the trivial congruence s(0N) = s(0), provide a complete set of congruent "initial values" for the two sequences s(kN) and s(k).  Also, by the same argument used to prove Proposition 6, "Newton's relations" uniquely determine the coefficients c1( ) through cd-1( ) of the two recurrence relations.  In addition, since cd = ±1, we have cd(k) = cd(Nk) for every odd integer N.  Thus, a complete set of initial values and all the recurrence coefficients of the two sequences are congruent (mod N), so we have s(k) = s(kN) (mod N) for every integer k.  By Proposition 6, it follows that N is a symmetric pseudoprime relative to f. à

 

In the following proposition and proof we use the symbol {x} signify the greatest integer less than or equal to x.

 

Proposition 9:  If f is reversible, then an odd positive composite integer N co-prime to {d/2}! is a symmetric pseudoprime relative to f if and only if s(kN) = s(k) (mod N) for k = ±1, ±2,.., e{d/2}, where e = ±1 if d is odd and +1 if d is even.

 

Proof:  The coefficient cd(n) of fn is related to the roots of f by

 

 

Substituting (-1)dcd for (q1q2...qd) gives

 

 

Now, observing that the roots of  f -n  are just the inverses of the roots of  fn, we have

 

 

Given the values of s(kN) (mod N) for k = ±1, ±2,.., e{d/2}, equation (5) uniquely determines the values (mod N) of cj(N) and cj(-N) for j = 1, 2,.., {d/2}, provided that N is co-prime to {d/2}! (to make the divisions by j unique (mod N)).  Then by equation (6) we can use the cj(-kN) to compute the values of cj(kN) (mod N) for j = {d/2} + 1, .., d.  Thus, the two sequences s(k) and s(kN) have a set of d consecutive values congruent (mod N) (including the equality with k = 0), and their recurrence coefficients are all congruent, so the entire sequences are congruent (mod N). à

 

For reversible sequences, the basis sequence formulas described in Section 1.2 can be extended to apply all integer arguments, positive and negative.

 

 

1.5  Coefficient Sequences

 

Although the basis sequence relations described in Section 1.2 provide an efficient and convenient means of evaluating the elements of the c1(k) sequence for any given polynomial f, it is sometimes useful to have formulas expressed entirely in terms of the c1(k) (or s(k)) sequence elements themselves.  The fundamental recurrence for fn can be written as

 

 

Since the value of k is arbitrary, we can set k = m + (r/n) for any integers m and r to give

 

 

Thus, the recurrence relation of fn applies not only to the sequence c1(nk) (k = 0, 1, 2,...), but also to the sequences c1(nk+r) for any integer r.  Furthermore, the coefficients of this recurrence relation can be expressed in terms of the c1(nk) sequence elements by solving equation (5) explicitly for the cj(n), which gives

 

 

In general, we have (Waring's formula)

 

 

where the summation is evaluated over all sets of m non-negative integers aj such that

 

 

These equations can be used to implement a log2N algorithm for computing c1(N).  For example, we can compute the recurrence coefficients ck(n) for n = 1, 2, 4, 8,.., 2s, where s = [log2n], in a "bootstrap" procedure, and then use these coefficients to compute c1(N).  Algorithms such as this can be applied to polynomials of any degree, but they generally involve more full multiplications per step, and more elaborate bookkeeping, than the basis sequence algorithm described in Section 1.2.

 

However, in some special cases it's possible to devise a coefficient sequence algorithm that is as efficient as a basis sequence algorithm.  If the sequence is reversible, then the terms of cj(n) in (7) can be replaced by ±cd-j(-n) as given by equation (6).  Thus, (7) can be expressed entirely in terms of the coefficient sequences cj(±n) (or symmetric functions sj(±n)) with j £ (d/2).  This is particularly convenient for the case of a reversible cubic (see Section 1.3).

 

 

1.6  Relations Between Basis Sequences and Symmetric Functions

 

Given any sequence of values A(k) (k = 0, 1, 2,...) that satisfies the fundamental recurrence relation of f, we have

 

 

In particular,

 

Another expression for the first symmetric function s(n) is given by a "contraction" of the basis sequences

 

 

If we define the sequence of square matrices Bn (n = 0,1,2,..) with components given by Bn(i,j) = bj(n+i), then s(n) can also be regarded as the trace of Bn.

 

It follows directly from (8) that

 

 

If the symbols a and b are permuted in the arguments, we have the slightly less obvious identity

 

 

Equations (9) and (10) are just two special cases of the following proposition.

 

Proposition 10:  Let {i,j,..,k} be a permutation of {1,2,..,q} composed of the cyclic components C1, C2, .., Ct.  Then

 

 

where  signifies the sum of all the nr such that r is in the cycle Cu.

 

Proof:  Proposition 3 gives both

 

 

and

 

Substituting from (11) into (12) (with k = n or m) gives

 

 

which is just the rule of multiplication for the components of matrices.  Thus, equation (12) is equivalent to the matrix product Bn+m = BnBm = BmBn.  Setting a = b in (12) gives, by contraction, equation (9).  Repeated substitutions of either (11) or (12) leads to the general result. à

 

For example, the quantity

 

 

corresponds to the permutation [a,b,m] ® [m,b,a], the cyclic  components of which are [a,m] ® [m,a] and [b] ® [b].  Thus, Proposition 10 gives the identity

 

 

 

1.7  Prime Types Relative to f(x)

 

We will classify each prime p relative to the polynomial  f  according to how  f  factors in Zp[x].  The type of each prime p will be denoted by a symbol of the form , signifying that in the ring Zp the polynomial f is the product of k1 irreducible factors of degree 1, and k2 irreducible factors of degree 2, and so on.  If a subscript is zero, the term will normally be omited from the symbol.  For example, if f is the product of one irreducible cubic factor and two linear factors in Zp[x] we will say that p is a prime of type {1231} relative to f.

 

The type of the prime p relative to f is also related to the general period of the characteristic recurrence of f (mod p), defined as the least positive integer n such that bj(n) = bj(0) (mod p) (j = 0, 1,.., d-1).  We will use the symbol tp to signify the general period of f (mod p).

 

Recall that Proposition 2 gives f(xp) = 0 (mod f,p).  By iterating the method of proof, this result can be extended to

 

 

for any non-negative integer k.  Thus, each number  is a root of f in Zp[x]f.

 

Proposition 11:  If f is irreducible in Zp[x], then the sequence of values  (mod f,p) has a period of d, i.e.,

 

 

Proof:  If p is a prime, then Zp[x]f is isomorphic to the finite field of order pd.  It is well known that if f is irreducible in Zp, then the proposition follows. à

 

Since f is irreducible in Zp[x], it follows that the ring of polynomials  Zp[x]f  possesses unique factorization, and therefore f has exactly d distinct factors in Zp(q)[x].

 

Dividing (13) by x gives

 

 

This shows that tp must divide pd-1.  For some common special cases this can be further refined by noting that the values of  (k = 0, 1,.., d-1) are the d roots of f in Zp[x]f.  For example, since the product of the roots equals cd, it follows that if cd = (-1)d, then tp divides 1 + p + .. + pd-1 = (pd - 1)/(p - 1).  On the other hand, if cd = -(-1)d, then , so tp divides 2(pd - 1)/(p - 1).

 

If f is reducible in Zp[x], then the general period of its recurrence divides the least common multiple of the periods of the irreducible factors.  For example, if p is a prime of type {2,3} relative to f, then tp divides lcm[(p2 - 1), (p3 - 1)].  Since p2 - 1 and p3 - 1 have the common factor p - 1, it follows that tp divides

 

 

In general, the sequence  has a period that divides the least common multiple of the degrees of the irreducible factors of f in Zp[x].  Thus, we can write

 

 

where kp is a divisor associated with the prime p.

 

The number of distinct roots of f in Zp[x]f can exceed the degree of f if f is reducible, because then unique factorization does not hold.  For example, if p is of the type {21,31} relative to f, then each of the six values  is a distinct root of f in Zp[x]f .  However, in related rings these six roots are not distinct.  We have monic irreducible polynomials g and h of degree 2 and 3 respectively such that f = gh (mod p), and we find that the sequence   has period 2 in the ring Zp[x]g and period 3 in the ring Zp[x]h.  Specifically we have

 

 

and

 

Letting a1,a2 denote the roots of g, and b1,b2,b3 denote the roots of h, we can say the prime p induces the permutation [a1,a2,b1,b2,b3] ® [a2,a1,b2,b3,b1] on the roots of f.  This permutation has two cyclic components, ai and bi, with periods 2 and 3 respectively.  The periods of the cyclic components of the permutation induced by a prime p determines the "type" of p (relative to f).  Furthermore, the cyclic structure corresponding to each type determines the asymptotic proportion of primes of that type.  If each of the d! possible permutations of the d roots of f is equally likely to be induced by any given prime, we can see immediately the expected asymptotic proportion of primes of each type, based on the proportion of the permutations that possess each of the cyclic structures, corresponding to the partitions of d.  For example, with d = 5 there are seven possible cyclic structures: 5, 4+1, 3+2, 3+1+1, 2+2+1, 2+1+1+1, and 1+1+1+1+1.  The cyclic structure corresponding to "5" is just a single cycle of length 5, so the first element can go to one of four places, then one of three, then one of two, and then the one remaining place before it repeats.  Hence there are 4! permutations with this cyclic structure, which implies that 4!/5! = 1/5 of all primes will be of type {51}.  At the other extreme, the cyclic structure "1+1+1+1+1" is given by only one permutation, so only 1/5! = 1/120 of all primes would be splitting primes.  In general, assuming each of the d! permutations is equally likely, the number of permutations for the prime type  is given by the multinomial coefficient

 

 

so the asymptotic density of each type is just 1 over the denominator.

 

However, for many polynomials of degree d the set of possible permutations of the roots is more restricted.  The most general polynomial of degree d allows all d! permutations, in which case we say the (Galois) group of the polynomial is the fully symmetric group Sd , but there are also polynomials of degree d whose Galois group is a subgroup of Sd.  For example, a quintic that is the product of 5 linear factors in Z[x] will obviously split completely in every ring Zp[x].  In this case the basic Galois group is just the trivial identity group, I, with only one element, so every prime will be of the type {15}.  On the other hand, some polynomials have Galois groups G that are intermediate between the identity group I and the fully symmetric group Sd.  In those cases we can compute the asymptotic density of each "type" simply by computing the fraction of the permutations contained in G that have the cyclic structure of the respective type.

 

 

1.8  Recurrences Modulo Composites

 

Given the general period of the recurrence of f for each prime in the factorization of , the general period of the recurrence (mod n) is given by

 

 

where "lcm" signifies the least common multiple.  For example, given the prime periods

 

 

relative to the polynomial f(x) = x3 - x - 1, the general period of the composite integer 360 = (2)3(3)2(5) equals the least common multiple of 22(7), 31(13), and 50(24).  Therefore, t360 = 2184.

 

Using the equation above, we can determine highly "resonant" composite moduli relative to a given polynomial.  For example, relative to x3 - x - 1 we have t449 = 224 = 25(7), so the general period of the recurrence modulo 26(449) equals the least common multiple of 25(7) and 25(7), which is just 224.  This shows that all the elements of any given sequence satisfying the recurrence An = An-2 + An-3 fall into no more than 224 of the residue classes modulo 28736, which is less than 1% of all the residue classes.

 

To construct another example, we can begin with the fact that

 

 

and search for other primes whose periods divide this number.  We find the following values

 

 

 

 

Therefore, all the elements of any given sequence satisfying the recurrence An = An-2 + An-3 fall into no more than 591360 distinct residue classes when evaluated modulo the number

 

 

which equals

 

In other words, the values of the sequence can fall into only 1 in (7.223)1029 of all the residue classes.

 

Return to Table of Contents