# Example of Extended Euclidean Algorithm

CRT: Uniqueness

What if x, y are both solutions to the equations ?

• x ≡ y (mod mi)  => mi | (x − y), for i = 1, . . . , n

Claim:

• so x ≡ y (mod M)

Theorem 10:
If are pairwise relatively
prime and mi | b for i = 1, . . . , n, then | b.

Proof: By induction on n.

• For n = 1 the statement is trivial.

Suppose statement holds for n = N.

• Suppose relatively prime, mi | b for
i = 1, . . . ,N + 1.

• by IH, c for some c

• By as sumption , | b, so

(since mi’s pairwise relatively
prime => no common factors )

• by Corollary 3,

• so

• so .

An Application of CRT: Computer
Arithmetic with Large Integers

Suppose we want to perform arithmetic operations (addition,
multiplication) with extremely large integers

• too large to be re presented easily in a computer
Idea:

• Step 1: Find suitable moduli so that mi’s
are relatively prime and is bigger than the

• Step 2: Perform all the operations mod mj, j =
1, . . . , n.

o This means we’re working with much smaller numbers
(no bigger than mj)

o The ope rations are much faster

o Can do this in parallel

• Suppose the answer mod mj is aj:

o Use CRT to find x such that x ≡ aj (mod mj)

o The unique x such that 0 < x < is the

Example: The fol lowing are pairwise relatively prime:

We can add and multiply positive integers up to

Fermat’s Little Theorem

Theorem 11 (Fermat’s Little Theorem):

(a) If p prime and gcd(p, a) = 1, then (mod p).

(b) For all (mod p).

Proof. Let

A = {1, 2, . . . , p − 1}

B = {1a mod p, 2a mod p, . . . , (p − 1)a mod p}

Claim: A = B.

• 0 B, since , so B A.

• If i ≠ j, then ia mod p ≠ ja mod p

since

Thus |B| = p − 1, so A = B.

Therefore,

(mod p)

[since gcd(p, (p − 1)!) = 1]
(mod p)

It follows that ap ≡ a (mod p)

• This is true even if gcd(p, a) ≠ 1; i.e., if p | a

Why is this being taught in a CS course?

Private Key Crypto graphy

Alice (aka A) wants to send an encrypted message to Bob
(aka B).

• A and B might share a private key known only to
them.

• The same key serves for encryption and decryption.

• Example: Caesar’s cipher f(m) = m + 3 mod 26
(shift each letter by three)

o WKH EXWOHU GLG LW

o THE BUTLER DID IT

This particular crypto system is very easy to solve

• Idea: look for common letters (E, A, T, S)

Some private key systems are completely immune to cryptanalysis:

• A and B share the only two copies of a long list of
random integers si for i = 1, . . . ,N.

• A sends B the message encrypted as:

ci = (mi + si) mod 26

• B decrypts A’s message by computing ci−si mod 26.

The good news: bulletproof cryptography
The bad news: horrible for e-commerce

• How do random users ex change the pad ?

Public Key Cryptography

Idea of public key cryptography (Diffie-Hellman)

• Everyone’s encryption scheme is posted publically

o e.g. in a “telephone book”

• If A wants to send an encoded message to B, she looks
up B’s public key (i.e., B’s encryption algorithm) in
the telephone book

• But only B has the decryption key corresponding to
his public key

BIG advantage: A need not know nor trust B.

There seems to be a problem though:

• If we publish the encryption key, won’t everyone be
able to decrypt?

Key observation: decrypting might be too hard, unless
you know the key

• Computing f -1 could be much harder than computing
f

Now the problem is to find an appropriate (f, f -1) pair
for which this is true

Number theory to the rescue

RSA: Key Generation

Generating encryption/decryption keys

• Choose two very large (hundreds of digits) primes p, q.

o This is done using probabilistic primality testing

o Choose a random large number and check if it is
prime

o By the prime number theorem, there are lots of
primes out there

• Let n = pq.

• Choose e ∈ N relatively prime to (p − 1)(q − 1).
Here’s how:

o One must be relatively prime to (p − 1)(q − 1)

* Otherwise | (p − 1)(q − 1)

Find out which one using Euclid’s algorithm

• Compute d, the inverse of e modulo (p − 1)(q − 1).

o Can do this using using Euclidean algorithm

• Publish n and e (that’s your public key)

• Keep the decryption key d to yourself.

RSA: Sending encrypted messages

How does someone send you a message?

• The message is divided into blocks each represented
as a numberM between 0 and n. To encryptM, send

C = Me mod n.

Need to use fast exponentiation (2 log (n) multiplications)
to do this efficiently

Example: Encrypt “stop” using e = 13 and n = 2537:

• s t o p 18 19 14 15 \$ 1819 1415

• 181913 mod 2537 = 2081 and

141513 mod 2537 = 2182 so

• 2081 2182 is the encrypted message.

• We did not need to know p = 43, q = 59 for that.

 Prev Next

Start solving your Algebra Problems in next 5 minutes!

2Checkout.com is an authorized reseller
of goods provided by Sofmath

Attention: We are currently running a special promotional offer for Algebra-Answer.com visitors -- if you order Algebra Helper by midnight of February 25th you will pay only \$39.99 instead of our regular price of \$74.99 -- this is \$35 in savings ! In order to take advantage of this offer, you need to order by clicking on one of the buttons on the left, not through our regular order page.

If you order now you will also receive 30 minute live session from tutor.com for a 1\$!

You Will Learn Algebra Better - Guaranteed!

Just take a look how incredibly simple Algebra Helper is:

Step 1 : Enter your homework problem in an easy WYSIWYG (What you see is what you get) algebra editor:

Step 2 : Let Algebra Helper solve it:

Step 3 : Ask for an explanation for the steps you don't understand:

Algebra Helper can solve problems in all the following areas:

• simplification of algebraic expressions (operations with polynomials (simplifying, degree, synthetic division...), exponential expressions, fractions and roots (radicals), absolute values)
• factoring and expanding expressions
• finding LCM and GCF
• (simplifying, rationalizing complex denominators...)
• solving linear, quadratic and many other equations and inequalities (including basic logarithmic and exponential equations)
• solving a system of two and three linear equations (including Cramer's rule)
• graphing curves (lines, parabolas, hyperbolas, circles, ellipses, equation and inequality solutions)
• graphing general functions
• operations with functions (composition, inverse, range, domain...)
• simplifying logarithms
• basic geometry and trigonometry (similarity, calculating trig functions, right triangle...)
• arithmetic and other pre-algebra topics (ratios, proportions, measurements...)

ORDER NOW!