Chapter 31: Number-Theoretic Algorithms: Modular Arithmetic, GCD, and RSA

Welcome to Last Minute Lecture!

This free chapter overview is designed to help students review and understand key concepts.

These summaries supplement not replaced the original textbook and may not be redistributed or resold.

For complete coverage, always consult the official text.

Okay, so, you know, today we're diving into something that's, well, kind of like the secret engine behind a whole lot of our digital lives.

Yeah, I mean, it's the stuff most people never even think about.

Exactly, number theory.

But it's really the math that makes things like secure websites and, you know, encrypted messages, all that stuff actually work.

Right, right.

Like without it, well, online security would be a whole different story.

Definitely.

So our mission today is to kind of unpack a whole chapter on number theoretic algorithms.

It's like a crash course in the core ideas of this, well, pretty vital field.

Yeah, and we're going to try and highlight the stuff that really matters, not get too bogged down in the weeds, you know.

Exactly, keep it clear and interesting, of course.

Absolutely.

So to kick things off, the chapter starts with some, like, really fundamental concepts.

The first one is divisibility.

Yeah, divisibility.

It's kind of like the building block of a lot of this stuff.

Right, and at its heart, it's, well, it's pretty simple.

When we say a number,

call it dollars, divides another number, say O, we write that as no remainder left over.

Exactly.

So, you know, three divides nine because nine's a multiple of three.

Right, right.

And from there, we get the idea of divisors, which are, you know, the numbers that divide a given number.

And importantly, divisors are always non -negative.

Uh -huh, uh -huh.

And then there are factors which are basically the divisors that are, well, not just one and the number itself.

Right, the more interesting divisors, I guess you could say.

Exactly.

So with divisibility, we can, like, start categorizing numbers into two main types, prime and composite.

Prime numbers, those are the cool ones, the building blocks almost.

Right, a prime number is any number greater than one that's only divisible by one in itself.

So, you know, two, three, five, seven, those are all prime.

They can't be broken down any further.

And a composite number is any number greater than one that's, well, not prime.

So it can be formed by multiplying smaller positive integers.

Yeah, like four, six, eight, nine, those are all composites.

And then there's the number one.

It's kind of a special case.

Right, it's called a unit.

And it's, well, it's neither prime nor composite.

It's in a category of its own.

Okay, so prime numbers,

they're kind of fascinating because, well, there's an infinite number of them.

They just keep going forever.

Yeah, it's mind -blowing, isn't it?

And the chapter actually lists out the first few primes just to give you a sense of how they look.

Now, building on divisibility, we get the division theorem, which is something we probably all use without even really thinking about it.

Right, it basically says that if you divide any whole number, let's say, ah, by another positive whole number,

one dollar, you're always going to get a unique whole number quotient, Madden -Malls, and a unique remainder, twordollar, that's smaller than dollar, but not negative.

And we often write that remainder using the notation, a may -mod band.

Yeah, it's basically saying, like, what's left over after you've divided as many times as you can.

Okay, and that remainder, that a plemedelon, is really important for understanding modular equivalence.

Modular equivalence, this is where things start to get a bit more, well, abstract, I guess.

Right.

Two numbers, eleven dollars, are considered equivalent modular dollar if they have the same remainder when divided by a dollar.

So we write that as a equiv b -nullin.

Yeah, and another way to think about it is that their b -nullin is perfectly divisible by a dollar.

Right, and this whole idea of modular equivalence, it groups numbers into sets called equivalence classes.

Okay, can you give an example of that?

Sure, sure.

Imagine you're sorting all the integers based on their remainder when you divide them by, let's say, five.

Okay, so you'd have a group for remainder zero, a group for remainder one, and so on, up to remainder four.

Exactly.

And the set of all those possible remainders, one, two, three, four in this case, that's often denoted as z -null.

Okay, that makes sense.

Now we're moving towards something a bit more, well, powerful, I guess.

The greatest common divisor, or GCD.

Ah, the GCD.

It's a real workhorse in number theory.

So for any two integers a -n dollars, or at least one of them isn't zero, their GCD written as text a -e -b -a -b is simply the largest positive integer that divides both a -n dollars without leaving a remainder.

Right, so for example, the GCD of, let's say, 12 and 18 is six.

Yeah, because six is the largest number that divides both 12 and 18 evenly.

Exactly.

And there are some handy shortcuts for finding the GCD.

The text a -b is the same as text a -b, and it's also the same as text a -b.

And the GCD of any number a -dollars is just the absolute value of day.

Right, right.

But here's a really interesting part, and this comes from theorem 31 .2.

The GCD of two numbers isn't just the largest common divisor, it's also the smallest positive number you can get by adding or subtracting multiples of those two numbers.

Okay, so you're saying that the GCD is also the smallest positive number that can be expressed in the form x plus bi, where 60 dollars are integers.

Exactly.

And this might seem a bit abstract, but it actually has some really important consequences later on.

Okay, I'm intrigued.

Now that brings us to relatively prime integers.

Relatively prime integers.

So that's when two numbers in a bollars have a GCD of one.

Meaning they don't share any common factors other than one.

Right.

And there's this really important theorem, theorem 31 .6, that talks about what happens when a prime number divides the product of two integers.

Okay, so if a prime number divides eight dollars, then payo must divide either a dollar or a bi dollar, or maybe even both.

Exactly.

And this property is, well, it's kind of crucial for the next big idea,

unique prime factorization.

Right, unique prime factorization.

This is a big one.

It's often called the fundamental theorem of arithmetic.

It's like the cornerstone of number theory almost.

So theorem 31 .8 states that every composite number can be written in a unique way as a product of prime numbers raised to specific powers.

Like you can think of it as every composite number having its own special recipe of prime ingredients.

Right, and that recipe is unique.

There's only one way to break it down into its prime factors.

Exactly.

And that uniqueness is, well, it's really important for a lot of the proofs and algorithms we use in number theory.

Okay, so now that we've covered

those foundational concepts, the chapter shifts to how we actually calculate the GCD.

And the classic super -efficient method is Euclid's algorithm.

Euclid's algorithm, that's a pretty famous one.

It's really elegant, actually.

It works by using this recursive

relationship.

Text GCD, B, AB, AAB.

So you keep applying that rule, replacing the larger number with the remainder you get when you divide it by the smaller number.

And you do that until the second number becomes zero.

And then the first number is your GCD.

It's amazing how such a simple process can be so powerful and so efficient.

Right, the number of steps it takes is related to the Fibonacci sequence, believe it or not.

Really, that's pretty cool.

Yeah, and thanks to May's theorem, we know that Euclid's algorithm is really fast, even for very large numbers.

Now, building on Euclid's algorithm, we have the extended Euclid's algorithm.

This is where things get, well, even more useful, especially for cryptography.

So the extended Euclid's algorithm, it doesn't just find the GCD of two numbers, i and a dollar.

It also finds two other integers, let's call them six and dollars, such that the GCD can be

plus by all.

So it gives us a way to write the GCD as a combination of the original two numbers.

Exactly, and that's really important for finding something called modular inverses, which are crucial for a lot of the cryptographic operations we'll be talking about later.

Okay, so we've got the basic arithmetic tools down.

Now the chapter starts to formalize things a bit by introducing the concept of groups.

Groups, they're a way to describe the structure of a group.

Right, and a group is basically a set of elements along with an operation that combines any two elements to produce another element in the set.

And that operation has to follow a few rules, like closure, which means the result is always within the set.

And there has to be an identity element, kind of like zero for addition or one for multiplication.

Right, and the operation has to be associative, which means the grouping doesn't matter when you combine multiple elements.

And every element needs to have an inverse, something that, like, undoes it.

Exactly.

Now, if the order in which you perform the operation doesn't matter, it's called an abelian group.

And if the set has a finite number of elements, well, it's a finite group, pretty straightforward.

Right, and the chapter then shows us how modular arithmetic actually creates these group structures.

First, we have the additive group modular, $1, written as zin plus $n.

So here, the said zinness is just the set of integers from zero to $9.

And the operation is addition, followed by taking the remainder when you divide by $.

Right, so it's like addition, but within this modular world.

Exactly.

And it turns out, this forms a finite abelian group.

The identity is zero, and the inverse of any element on it is just none -a -modulo, none -dollars.

Okay, that makes sense.

Then we have the multiplicative group modular, no -dollar, which is written as zinkiti.

No, this one's a bit more restricted.

The set zin only includes integers that are relatively primed to nonar.

So they're GCD with numbers of dollars.

Right.

And the operation is multiplication, again, followed by taking the remainder modular of $.

And this also forms a finite abelian group.

The identity here is one.

And what's really important is that the multiplicative inverse of an element only exists if the GCD of a dollar and dollars is $.

And we can actually find that inverse using the extended Euclid's algorithm, which we talked about earlier.

Exactly.

It all ties together.

Now, to understand the size of this multiplicative group, the chapter introduces Euler's phi function written as sick dollar.

Right, and sick dollar just counts how many positive integers less than or equal to dollars are relatively primed to dollars.

And there's a formula for calculating it based on the prime factorization of knowledge.

Yeah, which can be pretty handy.

Okay, so building on the idea of groups, we then get to subgroups.

A subgroup is basically a subset of a group that also forms a group under the same operation.

Right, so it's like a group within a group.

Exactly.

And theorem 31 .14 gives us a way to easily check if a subset is a subgroup.

If it's non -empty and closed under the group's operation, meaning combining any two elements in the subset gives you another element in the subset, then it's automatically a subgroup.

Okay, that's a handy rule.

And then we have Lagrange's theorem, which is a really important result.

Lagrange's theorem says that the number of elements in any subgroup of a finite group has to divide the number of elements in the original group perfectly.

So it's like the size of the subgroup has to fit neatly into the size of the larger group.

Exactly.

And that has some some far -reaching consequences in group theory.

Now the chapter also talks about subgroups that are generated by a single element.

So if you take an element from a group zoller and you repeatedly apply the group's operation to it, like kalav and all combined with the sol and so on, the set of all the distinct elements you get forms a subgroup.

And that subgroup is denoted as Langelangela.

Right.

And the order of an element is the smallest number of times you have to apply the operation to get back to the identity element.

And theorem 31 .7 Sena tells us that the order of an element is equal to the number of elements in the subgroup it generates.

Exactly.

And there's a really interesting consequence of Lagrange's theorem, corollary 31 .19.

It says that if you take any element in a finite group and apply the operation to it with itself a number of times equal to the size of the group, you always end up back at the identity element.

Okay.

So you're saying that like the power of the size of the group is always equal to the identity.

Exactly.

And this might seem a bit abstract, but it's actually really important for understanding things like Euler's theorem, which we'll get to later.

Okay.

So we've got this this group theory framework.

Now, how do we actually use it to solve problems?

Well, one application is in solving modular equations, which are equations of the form ACK and X equiv BPM mod.

So we're looking for values of $6 that satisfy that equation.

Right.

And it turns out these equations can have zero, one or multiple solutions.

And corollary 31 .22 gives us a condition for when they have solutions.

If the GCD of eight and non divides baller, then the equation has solutions.

Otherwise, it doesn't.

Exactly.

And if it does have solutions, corollary 31 .22 tells us exactly how many solutions there are.

It's equal to the GCD of $10.

Okay.

So how do we actually find those solutions?

Theorem 31 .24 gives us a method for doing that.

It involves using the extended Euclid's algorithm to find a particular solution first, and then you can generate all the other solutions from there.

Okay.

So the extended Euclid's algorithm is really coming in handy here.

It is.

It is.

And corollaries 31 .25 and 31 .26 tell us that if non are relatively prime, then there's only one solution, which is the multiplicative inverse of a modulo dollars.

Okay.

So that inverse is pretty important.

Now let's move on to the Chinese Remainger Theorem or CRT.

Ah, the CRT.

This is a really elegant and powerful result, especially when you're working with modular arithmetic involving multiple moduli.

Multiple moduli.

Yeah.

So imagine you have a system of congruences where each congruence is modulo a different number.

Okay.

So like six carvel, a, t, e, t, two, a, two, t, e, two, a, two, and so on.

Exactly.

Now the CRT says that if those moduli, the nine dollars, are pairwise relatively prime, meaning no two of them share a common factor other than one, then there's a one -to -one correspondence between an integer modulo, the product of all those modulo, and the tuple of its remainders when divided by each individual modulus.

Okay.

So if you know the remainders of a number when divided by each of those nine dollars, you can uniquely determine the number modulo, the product of all of them.

Exactly.

And what's really cool is that you can perform arithmetic operations on these tuples of remainders component wise, and it's equivalent to performing the same operation on the original number modulo, the large product.

So it's like you can break down a problem into smaller, more manageable pieces.

Exactly.

And the CRT also gives us a way to reconstruct the original number from its remainders, which can be really useful.

Okay.

So the CRT is a pretty powerful tool.

Now the chapter briefly touches on raising an element to powers modulo $1.

Yeah.

So we're talking about sequences like Adelard, Adler -Doors, Adler, and so on, modulo theorem, where Adel is an element of the multiplicative group zennel.

And this leads us to two very important theorems, Euler's theorem and Fermat's theorem.

Right.

Euler's theorem, which is theorem 3130, states that for any integer come greater than one, and any integer that's relatively primed to $1 to the power of besia is congruent to one modulo $1.

So O will equivalent one PMAC.

Exactly.

And remember, AJ is Euler's totient function, which counts how many positive integers less than or equal to $1 are relatively primed to $1.

Right.

And then there's Fermat's theorem, also known as Fermat's little theorem.

Fermat's little theorem is actually a special case of Euler's theorem, where serum is a prime number.

So in that case is simply P the $1.

Right.

Because all positive integers less than a prime number are relatively primed to it.

So Fermat's little theorem states that if P Euler's is prime and eight is not divisible by a pay, then eight to the power of peon is congruent to one modulo peon.

Exactly.

So I P one, equif one of pores.

And both of these theorems are incredibly useful in number theory, especially in cryptography.

Okay.

So those are some pretty powerful theorems.

Now the chapter talks about primitive roots.

Primitive roots.

So if you have an element doubler and zen and it's order modulo non, which is the smallest positive integer, such that Tyloidal letters is congruent to one modulo ma is equal to the size of zen, which is SAFE one, then the always is called a primitive root.

Okay.

So it's like a special element that generates the entire multiplicative group.

Exactly.

And if such a primitive root exists, then the group zen is said to be cyclic.

And theorem 31 132 gives us the specific values of $ for which zen is cyclic.

Right.

And for those values of un and if you have primitive root del r dollar, then for every element h or dollar, there's a unique exponent $6 such that intro is congruent to a modular now.

And that exponent six all is called the discrete logarithm of a base del and modular.

Exactly.

And finding this discrete logarithm is generally thought to be a really hard problem computationally speaking, which makes it really useful for cryptography.

Okay.

So discrete logarithms are important for security.

Now the chapter briefly discusses square roots of one modulo dollar.

Right.

So theorem 31 .34 tells us that if paddle is an odd prime and a law is a positive integer,

then the equation sex by all equivalent P model only has two solutions.

Sex equivalent P mod pin and $6 equivalent P mod pin.

Okay.

So those are the trivial square roots of one.

Exactly.

And a non -trivial square root of one modulo law is a solution to that equation where $6 is not congruent to one or minus one modulo dollar.

And corollary 31 .35 says that if you find a non -trivial square root of one, then muddle must be composite.

Right.

It's a way to show that a number is not prime.

Okay.

So now let's move on to some actual algorithms.

The chapter describes a method for modular exponentiation.

Modular exponentiation.

This is a really important operation in a lot of cryptographic systems.

Right.

And the algorithm the chapter describes is called modular exponentiation.

It's a really clever algorithm that uses repeated squaring to compute every modulo much faster than just multiplying a dollar by itself power time.

Okay.

So it's a way to speed up that calculation.

Exactly.

And the number of steps it takes is proportional to the logarithm of the exponent, which makes it really efficient.

Okay.

And that brings us to one of the most well -known applications of number theory,

the RSA public key cryptosystem.

Ah, RSA.

It's a classic.

And its security depends on the fact that it's really hard to factor the product of two large prime numbers.

Right.

That's the whole basis of RSA.

So how does it actually work?

Well, first you need to generate the keys.

You pick two large prime numbers, houses and dollars, and compute their product, no dollar.

And no dollar is part of both the public and private keys.

Right.

Then you calculate Euler's totient function for nine dollar, which is P one Q dash one dollar.

Okay.

So you need those prime factors to calculate two dollar.

Exactly.

Then you choose a small odd integer dollar that's relatively prime to two dollars.

This is your public exponent.

And finally, you calculate dollars, the multiplicative inverse of a D modulo dollars.

This is your private exponent.

Right.

So your public key is the pair of dollar, and your secret key is the pair eight N dollars.

Okay.

So how do you actually encrypt a message with RSA?

Let's say you have a message lie dollar represented as an integer between zero and N dollars.

To encrypt it, you compute D dollar a May.

And C of dollars is the cipher text, the encrypted message.

Right.

And to decrypt it, you compute one dollar C die.

So only someone with the private key D dollar can decrypt the message.

Exactly.

And RSA can also be used for digital signatures.

In that case, you use your private key to create a signature for a message, and anyone with a public key can verify it.

And theorem 31 .36 in the chapter proves that all of this works correctly based on Euler's theorem and the CRT.

Right.

The security of RSA really hinges on the difficulty of factoring that large number dollar.

And that's why choosing large enough prime numbers is so important.

Exactly.

And in practice, there are other considerations for implementing RSA securely, like using hybrid encryption schemes and hash functions.

Okay.

So the last topic the chapter covers is primality testing.

Primality testing.

This is all about figuring out whether a large number is prime or not, which is crucial for generating keys for RSA and other cryptographic systems.

Right.

Because you need those large prime numbers to start with.

Exactly.

Now the prime number theorem, theorem 31 .37, tells us that prime numbers are actually fairly common, even though they get less frequent as numbers get larger.

But finding them is the tricky part.

It is.

It is.

One way to check if a number is prime is to use trial division, where you try dividing it by all integers up to its square root.

But for very large numbers, that's just not efficient.

Right.

So we need other methods like pseudo -primality testing, which is based on Fermat's little theorem.

So if a number doesn't satisfy Fermat's little theorem for some base worth, then we know it's composite.

Exactly.

But there's a catch.

There are composite numbers called Carmichael numbers that pass the Fermat test for all bases that are relatively prime to them.

So the basic Fermat test isn't foolproof.

Right.

That's why we use more robust tests like the Miller -Rabin test.

And the Miller -Rabin test uses multiple random bases and for non -trivial square roots of 1 during the computation.

Exactly.

And theorem 31 .40 gives us a probabilistic guarantee.

If we run the Miller -Rabin test enough times, the probability of it being wrong is extremely small.

So we can be very confident about whether a number is prime or not.

Right.

And with that, I think we've covered, well, pretty much the entire chapter on number theoretic algorithms.

Yeah.

We've gone through the basics of divisibility and prime numbers, looked at Euclid's algorithm and the extended Euclidean algorithm, delved into group theory and modular arithmetic, and finally explored applications in cryptography like RSA and primality testing.

It's been quite a journey.

It has.

It has.

And hopefully our listeners now have a better understanding of how these seemingly abstract mathematical ideas are actually the foundation for a lot of the technology we use every day.

Exactly.

And it's kind of amazing to think about how these concepts are constantly being pushed further in research.

Right.

Like the search for even more efficient primality tests and the challenge of factoring really large numbers.

It makes you wonder what the future holds for cryptography and online security.

Absolutely.

It's a fascinating area to keep an eye on.

So on that note, I think we can confidently say that we've summarized all the major points, theories, findings, and examples from this chapter on number theoretic algorithms.

We have indeed.