Conjugate: changes the sign of a certain term in an expression, traditionally the part of an expression that is either irrational or imaginary. For this research, it applies to changing the sign of a residue, the integer part of the numerator of an in the continued fraction expansion.
Cryptography: set of methods for encrypting information to prevent it from being read by anyone who intercepts the messege. Used in variety of civil and military applications.
Euclid's Algorithm: fast algorithm for determining the greatest common divisor of two integers. Given and , the extended Euclidian algorithm also determines the coefficients and such that .
Floor: greatest integer less than or equal to a given number. Symbol:
Greatest Common Divisor: largest integer that divides a pair or group of integers. Symbol:
Modular Arithmetic: two numbers are considered equal (congruent) if heir difference is divisible by the base. Thus, . Numbers are represented by integers between and , where is the base. Multiplication, addition, and subtraction are normal, except that the results are reduced. Division is performed by reducing fractions to least terms, applying an extended Euclid's algorithm to find the inverse of the denominator, and then performing multiplication. Symbol: mod
Modulo: operation related to division that returns the remainder:
, so modulo . Symbol: or mod
NUCOMP-NUDUPL: algorithms designed by Daniel Shanks to perform composition of quadratic forms quickly.
Perfect Square: integer that is the square of another integer. Thus, is a perfect square because .
Pseudo-square: the denominator of an in the continued fraction expansion, denoted . When , is a quadratic residue and in general is a quadratic residue.
Quadratic Reciprocity Law (Gauss): determines which numbers are quadratic residues of a prime:
Symbol: if has a solution, if it does not, and if .
Theorem: For and distinct primes:
Quadratic Residue: a perfect square modulo some base . is a quadratic residue of because .
Relatively Prime: having no common divisors. Thus, and are relatively prime, even though they are not prime by the normal definition.
Residue: integer that remains in the numerator after has been subtracted from in the continued fraction expansion.
RSA: cryptology algorithm named after Rivest, Shamir, and Adleman. It was earlier developed by Clifford Cooks of GCHQ, but this was only recently declassified. Its security is dependent on the difficulty of factorization [E].
SQUFOF: Square Forms Factorization, developed by Daniel Shanks in 1982.