cryptography The practice of altering the form of a
message by codes and ciphers to conceal its meaning to
those who intercept it, but not to those who receive it,
is called cryptography. If letters of the alphabet and
punctuation marks are replaced by numbers, then
mathematics can be used to create effective codes.
In 1977 three mathematicians, Ron Rivest, Adi
Shamir, and Leonard Adleman, developed a public-key
cryptography method in which the method of encoding
a message can be public to all without compromising the
security of the message. The RSA encryption method, as
it is known today, is based on the mathematics of the
MODULAR ARITHMETIC
and relies on the fact that it is
extraordinarily difficult to find the two factors that pro-
duce a given large product. It is the primary encryption
method used today by financial institutions to transmit
sensitive information across the globe.
The RSA encryption method is based on the fol-
lowing result from modular arithmetic:
Suppose pand qare distinct
PRIME
numbers. If
nis a number with neither pnor qa factor,
then n(p–1)(q–1) ≡1(mod pq). Moreover, we have
nm(p–1)(q–1)+1 ≡n(mod pq) for any two natural
numbers nand m, even if nis a multiple of p
or q.
(We prove this result at the end of this entry.) One pro-
ceeds as follows:
1. Encode your message as a string Mof numbers.
2. Choose two large prime numbers pand qso that their
product N= pq is larger than M. Let k= (p– 1)(q– 1)
and choose a number ewith no common factor to k.
The numbers Nand ecan be made public.
3. Raise the number Mto the eth power, modulo N.
This gives the encoded message M′:
M′≡Me(mod N)
4. Since the
GREATEST COMMON DIVISOR
of kand eis
one, the E
UCLIDEAN ALGORITHM
shows that we can
find numbers dand mso that 1 = de – mk. In partic-
ular there is a number dsuch that ed ≡1(mod k).
Keep the number dsecret.
5. To decode the message, raise M′to the dth power.
By the result stated above, this does indeed return
the original message M:
M′d= Med = Mkm+1 = Mm(p–1)(q–1)+1
≡M(mod N)
If one works with very large prime numbers, say,
10,000-digit primes, it is virtually impossible to factor
the public number Nand find kand d. Thus the RSA
system is extremely secure. (This use of large primes
also explains the current excitement over the discovery
of larger and larger prime numbers.) On the other
hand, multiplying and raising large numbers to powers
is easy for computers to do, and so the RSA method is
also very easy to implement.
Proof of Result
Suppose first that nis not a multiple of pand consider
the numbers 1,2,…,p– 1. Multiply each by n. If, for
two numbers xand yin the list, we have nx ≡ny(mod
p), then n(x– y) is a multiple of p. This can only hap-
pen if xand yare the same number. Thus, up to multi-
ples of p, the products n·1,n·2,…,n·(p– 1) are distinct
and so must represent a rearrangement of the original
list, modulo p. Consequently, n·1·n·2·…·n(p– 1) ≡
1·2·…·(p– 1) (mod p), and the factor np–1 in the left
must be congruent to 1 modulo p: np–1 ≡1(mod p).
Similarly, we have nq–1 ≡1(mod q) if nis not a multiple
of q. It follows from these two results that if nis not a
multiple of por q, then:
n(p–1)(q–1) = (np–1)q–1 ≡1(mod p)
n(p–1)(q–1) = (nq–1)p–1 ≡1(mod q)
which shows that n(p–1)(q–1) – 1 is divisible by both p
and q, and hence by pq. This proves the first claim
made. The second follows by noting that nm(p–1) (q–1)+1 =
n·(np–1)m(q–1) ≡n(mod p) is a true statement even if nis
a multiple of p, and nm(p–1)(q–1)+1 ≡n(mod q) is also
true for all values of n. Any quantity nm(p–1)(q–1)+1 – nis
thus always divisible by both pand q.
cube (hexahedron) The third P
LATONIC SOLID
, the
cube, is the solid figure bounded by six identical square
faces that meet at right angles. It has eight vertices and
12 edges. Because the
VOLUME
of a cube of side-length
ais given by a3, any number raised to the third power
is sometimes called a cube. The “cubic numbers” are
the cubes of the counting numbers: 0, 1, 8, 27, 64,
125,…
It is possible to subdivide a large cube into 27
smaller cubes with six planar cuts. This number of cuts
cannot be improved upon even if one is permitted to
cube 111