Glossary

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 $x_i$ 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 $x$ and $y$, the extended Euclidian algorithm also determines the coefficients $a$ and $b$ such that $ax+by = \gcd(x,y)$.

Floor: greatest integer less than or equal to a given number. Symbol: $\lfloor x \rfloor$

Greatest Common Divisor: largest integer that divides a pair or group of integers. Symbol: $gcd(x,y)$

Modular Arithmetic: two numbers are considered equal (congruent) if heir difference is divisible by the base. Thus, $3 \equiv 10 \pmod 7$. Numbers are represented by integers between $0$ and $N-1$, where $N$ 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$\ N)$

Modulo: operation related to division that returns the remainder:

$\frac{73}{11} = 6\frac{7}{11}$, so $73$ modulo $11 = 7$. Symbol: $\%$ or $($mod$\ N)$

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, $9$ is a perfect square because $3^2 = 9$.

Pseudo-square: the denominator of an $x_i$ in the continued fraction expansion, denoted $Q_i$. When $Q_0 = 1$, $(-1)^iQ_i$ is a quadratic residue and in general $-Q_iQ_{i-1}$ is a quadratic residue.

Quadratic Reciprocity Law (Gauss): determines which numbers are quadratic residues of a prime:

Symbol: $(\frac{a}{p}) = 1$ if $x^2 \equiv a \pmod p$ has a solution, $-1$ if it does not, and $0$ if $p \mid a$.

Theorem: For $p$ and $q$ distinct primes:

$$(\frac{p}{q})(\frac{q}{p}) = (-1)^{(p-1)(q-1)/4}$$

$$(\frac{2}{p}) = (-1)^{(p^2-1)/8}$$

$$(\frac{-1}{p}) = (-1)^{(p-1)/2}$$

Quadratic Residue: a perfect square modulo some base $N$. $2$ is a quadratic residue of $7$ because $3^2 \equiv 2 \pmod 7$.

Relatively Prime: having no common divisors. Thus, $8$ and $15$ are relatively prime, even though they are not prime by the normal definition.

Residue: integer that remains in the numerator after $b_i$ has been subtracted from $x_i$ 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.