Number Theory Glossary

Abelian Group

An abelian group is a group whose operation is commutative, ie a*b=b*a. An example of an abelian group is the integers with the usual addition operation. An example of a group which is not abelian is the rotations of a cube (try it out). When dealing with an abelian group is it conventional to denote the group operation as addition (+), rather than multiplication (*) and to denote the unit element as 0 rather than 1.

Carmichael Number

A Carmichael Number is a composite number which passes the Fermat pseudoprime test for all bases. There are an infinite number of Carmichael numbers - the smallest is 561=11*17*3.

Composite

A composite number has non-trivial factors (ie factors other than itself and 1). Thus 13 is prime but 15=3*5 is composite. A number which is not composite is called prime. A polynomial which has non-trivial factors is called reducible.

Euler Pseudoprime Test

A more effective pseudoprime test than the simpler Fermat test. A number N is called an Euler pseudoprime to base b if b^(N-1)/2 =(b/N) (mod N). (Here (b/N) is the Jacobi symbol.) This test is also called the Solovay-Strassen test for its original proposers. If an integer is an Euler pseudoprime it is also a Fermat pseudoprime.

Extension

A field F2 is called an extension of another field F if F is contained in F2 as a subfield. Examples include the Galois fields, as they are all extensions of the integers modulo a prime p.

Factor

To separate a number (or a polynomial) into a product of other numbers (also called factors). Thus 15 is factored as 15=3*5. A non-trivial factorization has no factors of 1.

Fermat's Little Theorem

If p is prime and b<p then b^(p-1) =1(mod p). Rephrased, this says that the order of b in the group of integers modulo p divides (p-1).

Fermat Pseudoprime Test

The simplest (and least effective) pseudoprime test. A number N is called an Fermat pseudoprime to base b if b^(N-1)=1(mod N). A Fermat pseudoprime is more commonly just called a pseudoprime. (The name "Fermat pseudoprime" is used as this test is equivalent to Fermat's Little Theorem.)

Field

A field is an algebraic structure with two operators (commonly called addition (+) and multiplication (*)) which satisfies the following conditions:

1. The elements of the field form an Abelian group under addition

Fields with a finite number of elements are called Galois fields.

Galois Fields

A Galois Field is a field with finite number of elements. Galois fields take one of two forms:

• Z_p - The integers modulo some prime p.
• F_p^n - The polynomials with coefficients modulo some prime p with operations modulo some irreducible degree n polynomial r(x).

In either case, the Galois field with q=pⁿ elements is commonly denoted GFq or F_q.

Gaussian Integers

The ring of Gaussian Integers is the extension of the integers with a symbol i which is the root of the equation x²=-1. Thus this ring consists of elements of the form (n+m*i) with the additional condition that i²=-1. (For example, (2+i)*(2-i)=5, showing that 5 is not prime in the Gaussian Integers.)

Group

A field is an algebraic structure with one operator (commonly called multiplication (*)) which satisfies the following conditions:

1. There is a distinguished unit element (commonly denoted 1, such that for any element a we have a*1=1*a=a.
2. Any element a has an inverse (denoted a^(-1)) such that a^(-1)*a= a*a^(-1)=1.

A group whose operation is also commutative (ie a*b=b*a) is called Abelian.

Irreducible

An irreducible polynomial has no factors other than 1 (called non-trivial factors). Thus x+1 is prime but x²-1=(x-1)(x+1) is not prime. A polynomial which is not irreducible is called composite. A number which has no factors other than 1 is called prime.

Jacobi Symbol

The Jacobi symbol, denoted (a/n), is a function which is defined in terms of the Jacobi symbol. If the prime factorization of n is n=p1^e1 *...*pk^ek then the Jacobi symbol is defined as (a/n) =(a/p1)^e1 *...*(a/pk)^ek.

Legendre Symbol

The Legendre symbol, denoted (a/p), is a function which is defined if p is prime. Its value is:

• 0 if p divides a.
• 1 if a is a quadratic residue (ie there is some integer b such that p=b²(mod p))
• -1 if a is not a quadratic residue.

A more general function which is defined for non-prime values of p is the Jacobi symbol.

Lucas Pseudoprime Test

The simplest (and least effective) pseudoprime test. A number N is called an Fermat pseudoprime to base b if b^(N-1)=1(mod N). A Fermat pseudoprime is more commonly just called a pseudoprime.

Miller-Rabin test

Also called the strong pseudoprime test, this test was originally proposed by M. O. Rabin in Algorithms and Complexity, J. F. Traub (Ed), Academic Press, 1976, pp 35-36., based on ideas of G. L. Miller.

Order

Order has two related meanings:

1. The order of a group is the number of elements in the group.
2. The order of some element b is the smallest exponent e such that b^e=1.

For example, Fermat's Little Theorem states that the order of any element b in the group of integers modulo a prime p divides (p-1)

Prime

A prime number is a number which has no factors other than 1 (called non-trivial factors). Thus 13 is prime but 15=3*5 is not prime. A number which is not prime is called composite. A polynomial which has no factors other than 1 is called irreducible.

Primitive

Primitivity has two meanings, a primary meaning and a derived meaning used only in non-prime Galois fields:

• A primitive element in a group is an element whose powers exhaust the entire group. Thus 3 is primitive in the group of units mod 7 as 1=3⁶, 2=3², 3=3¹, 4=3⁴, 5=3⁵, and 6=3³, but 2 is not primitive in this group as there is no exponent e such that 3=2^e (mod 7). More commonly we say that 3 is primitive mod 7 but 2 is not.
• We say that the polynomial p(x) is primitive (mod some finite base field F) if the element x is primitive (in the previous sense) in the group of units of the polynomials mod p(x). Thus we say that the polynomial x²+x+1 is primitive mod 2 as x=x¹, x+1=x², and 1=x³. However, the same polynomial is not primitive mod 5 as 1=x³(mod p).

Pseudoprime

A pseudoprime is any number which passes a pseudoprime test for some base. Thus any prime number is a pseudoprime for any base. Some pseudoprimes are not prime though. (For example the composite number 341=11*31 is an Fermat pseudoprime for base 2 as 2^(341-1)=1 (mod 341).) Pseudoprimality tests (also called compositeness tests) include:

• Fermat test
• Euler test (also called Solovay-Strassen test)
• Strong Pseudoprime test (also called the Miller-Rabin test)
• Lucas test

Ring

Solovay-Strassen test

Also called the Euler pseudoprime test, this test was originally proposed by Solovay and Strassen in SIAM J. Computing, 6 (1977), 84-85 and 7 (1978), 118.

Strong Pseudoprime Test

A pseudoprime test. Let N-1 = 2^sq. If there is some r in the range 0<r<s such that b^{(N-1)/2^r}=-1(mod N) and b^{(N-1)/2^(r-1)}=1(mod N) then N is called an strong pseudoprime to base b. This test is also called the Miller-Rabin test for its originators. If an integer is a strong pseudoprime it is also a Fermat pseudoprime and an Euler pseudoprime.