you
we'll continue our discussion of number
theory by introducing the notion of a
group this is actually a very
fundamental and important notion both
for mathematics in general as well as
for applications to cryptography roughly
speaking the notion of a group provides
a way of reasoning about different
objects that share the same underlying
mathematical structure and hopefully
this will become more clear when we see
the definition and then see a couple of
examples now one thing I will say is
that an understanding of groups and a
little rudimentary group theory is
strictly speaking not necessary to
understand crypto or cryptographic
applications but in my opinion just a
little bit of knowledge about the
concept of a group does make things
conceptually easier it puts things in an
appropriate framework and I think makes
it easier to grasp what's really going
on under the hood and since that part of
what you're interested in learning from
this class I do think it's important to
spend some time on basic group theory so
let's jump in and look at the definition
we're only going to be interested here
in abelian groups and so that's what I'm
going to define so an abelian group is a
set G a set of elements along with a
binary operation that for this slide
we're going to denote by this little
circle defined on the elements of G this
means that for every two elements of G
you can compute a circle B and then get
back as a result some other element of
the same set and this has to satisfy
certain conditions and the conditions
are the following so first of all we
require that there exists some element
in G that acts as an identity and on
this slide we'll denote that element by
E and the property of this element E the
fact that it acts as an identity means
that Y dot G is equal to G for every
element in the set capital G we're also
going to require that every element in
has an inverse H say such that H dot G
is equal to this identity element we
require also the notion of associativity
which should be familiar to you from
basic arithmetic and this just requires
that for every three elements FG and H
in the set G if we first compute G H and
then compute F dot the result then that
gives the same answer as if we first
compute F G and then take that
intermediate result and take that dot H
so it doesn't matter in some sense what
order we do the operations we're only
going to consider as I mentioned earlier
abelian groups and abelian groups have
the extra property that for all G and H
in the set G G H is the same as H G and
one more piece of notation the order of
a finite group G and we're only ever
going to consider finite groups in this
course the order of a group G is the
number of elements in the set G so let's
look at a piece of notation so just to
simplify matters rather than writing
this little circle to represent the
group operation it's very common to
instead use either additive notation or
multiplicative notation to denote the
group operation so under additive
notation we write G Plus H to denote the
group operation on G and H and under
multiplicative notation we write either
G H or G with a little dot instead of a
little circle H analogous to the way you
would write multiplication of integers
in grade school arithmetic now it's
important to keep in mind that just
because we're writing things in this way
does not mean that the group operation
corresponds to integer addition or
multiplication for the most part in all
the examples we talk about in this class
ultimately things are going to be based
on integer addition or multiplication
though they will not be identical to
integer addition or multiplication but
it's also very easy to consider examples
where
addition and multiplication of integers
is nowhere to be seen and you define the
group operation completely abstractly
but you nevertheless might write it
using this additive or multiplicative
notation just a few more pieces of
notation to represent the identity
element it's convenient to use zero or
one zero
in the case of additive notation and a
one in the case of multiplicative
notation this is again just something a
more convenient way to represent the
identity rather than using e the inverse
of an element is denoted in the natural
way by minus G if we're using additive
notation or G to the -1 power if we're
using multiplicative notation and when
we talk about group group exponentiation
which means repeated application of the
group operation we denote that by ma
when we're using additive notation which
again refers to repeated addition in
quotes of a to itself a total of M times
or when using multiplicative notation we
write a to the M to refer to repeated
multiplication of a by itself M times
where again we're careful to understand
that this does not mean that we're that
we're referring to integer
multiplication or integer addition in
either case one thing I'll point out
here this starts getting a little bit
abstract but I think it's if you can
understand this you have a good
understanding what's going on when we
write something like m dot a using
additive notation for the group a is a
group element and M is an integer so
what we're talking about here is not the
group operation applied to M and a right
Emma's not even necessarily in the group
its type is that of an integer but where
what we're referring to is repeated
application of the group operation to
the group element a a total of M times
and here we're assuming that M is a
positive integer you can handle
negatives and zeros in really pretty
much the natural way and we don't handle
fractional m at all in terms of
performing computations in groups so
we're again going to ultimately be
interested in the algorithmic efficiency
of performing different operations in
different
mutations in the groups that we're going
to be working with and we're always
going to implicitly assume that for any
groups we're talking about in the
context of cryptography that it is
possible to efficiently recognize what a
group element is so that is we
ultimately going to be writing every
element of some group as a sequence of
bits and it should be possible given
some sequence of bits to tell whether or
not that represents a valid group
element we also are going to assume that
the group operation can be computed
efficiently so again this means that
given two group elements represented by
their bit strings we can compute the
group operation on those two group
elements ie those two strings and
furthermore that we can compute this
group operation in time polynomial in
the length of those strings now when I
say a film here I don't mean that we
don't think about it at all what I mean
is that we of course have to analyze for
some group of cryptographic interest
that it is indeed possible to perform
these operations efficiently but we will
assume that somebody else has done the
work for us and therefore that they can
indeed be done efficiently now the fact
that the group operation can be computed
efficiently means also that group
exponentiation can be computed
efficiently and this follows using the
same algorithm that we showed last time
for performing modular exponentiation
and the connection between the two might
become more clear after we show that in
fact some form of multiplication modulo
n can indeed be viewed as a group
operation let's see an example of a
group this is perhaps the most basic
example so consider the set V n which
denotes the set of elements from 0 to n
minus 1 under addition modulo n so this
means that the group operation here or
the operation is defined as taking any
two elements in the set adding them and
taking the result reducing it modulo n
to give back an integer in the range of
0 to n minus 1 well it's not too
difficult to convince yourself that this
does give a valid group the identity
element here is simply 0 which is in the
set the inverse of the element a
is the element - a reduced modulo n
where we need to reduce modulo n so that
we get back something in the same set
associativity and commutativity of the
group operation is immediate it follows
from associativity and commutativity of
the underlying operation on the integers
and the order of this group is n because
it contains exactly the n elements the n
integers from 0 to n minus 1 and the
exponentiation here m dot a corresponds
to as we said earlier repeated addition
of a to itself m times and as we noted
this can be computed efficiently in fact
in this case you can compute it just by
using standard integer arithmetic this
is kind of a coincidence if you want to
call it that due to the fact that the
element a here can be viewed both as an
element of the set V n as well as an
integer now what happens if we try to
extend the previous example and think
about multiplication modulo n well the
first thing to note is that the same set
0 to n minus 1 is not going to be a
group under this operation one would
have to be the identity but for example
the element 0 has no inverse there's
nothing no element in that set when
multiplied by 0 is going to give us 1 in
fact even if we exclude 0 from
consideration if we take it out of the
set that doesn't solve the problem
because for example think about the case
when N equals 4 well there's no inverse
of 2 modulo 4 something that you can
check just by brute force and numerating
over all the possibilities right the set
in this case would be the elements 1 2
and 3 under multiplication modulo 4 and
none of 1 or 2 or 3 multiplied by 2
gives 1 1 reduced modulo 4 so what we
need to do instead is to restrict the
elements in our set so let's first begin
with a definition say that the element b
is invertible modulo n if there is some
other element B inverse such that B
times B inverse is equal to 1 mod n in
other words we're just defining
invertibility modulo n to mean that B
has an in
is modulo N and if such a B inverse
exists it turns out you can show that
it's unique modulo n so an element if it
has an inverse has exactly one inverse
I'll note also that we can use this to
define a notion of division by B so when
we're mark when we're working with an
operation of multiplication modulo N and
we say or we tour we talk about division
by B in fact what we mean formally is
multiplication by B inverse modulo N and
in fact the notion of division is not
really well defined modulo n if the
element B does not have an inverse so
the operation of division by B it really
should only be defined when B is
invertible module and in the first place
now the natural question is which
elements are invertible and we can fully
characterize those elements by the
following theorem element b is
invertible modulo n if and only if the
greatest common divisor of b and n is
equal to one we're not going to prove
that here although a proof is not
incredibly difficult but it's not really
so important for our purposes and this
also means not only can we characterize
invertibility but we can efficiently
test whether a given element is
invertible and this is a consequence of
the fact that GCD can be computed in
polynomial time that is given two
integers be an N here for example we can
compute their greatest common divisor in
polynomial time this is not trivial but
it is something that has been known
since the time of Euclid the algorithm
for doing this actually is called the
Euclidean algorithm now coming back to
the question of invert ability so we
said earlier that an element b is
invertible if the greatest common
divisor of b and n is 1 so if we take
for example a P Prime if we're
considering a prime modulus then all of
the elements between 1 and P minus 1
will be invertible modulo P and that
follows from the fact that the greatest
common divisor of P and any integer
less than p is going to have to be one
right because the only factors of PR 1
NP nothing else no no image are smaller
than P can have any other factor than 1
in common with P a second interesting
example is given by a moduli of the form
of product of two primes
so say n is equal to PQ for P and Q
distinct primes
then the invertible elements modulo n
are going to be the integers from 0 to n
minus 1 that do not share a factor in
common with n other than 1 right this is
just re expressing the fact that the
greatest common divisor of the element
and n should be 1 so this means that we
can imagine listing out the elements
from 1 to n minus 1 and excluding all
the multiples of P and all the multiples
of Q and again this will what we're left
with is going to consist of exactly the
elements whose greatest common divisor
with n is equal to 1 and this is a
consequence of the fact that P and Q are
prime so it turns out that if we do this
then the said Zn star which we will
define as the set of invertible elements
between 1 and n minus 1 is indeed a
group under multiplication modulo n so
we came to the question earlier or we or
we noted earlier that just looking at
multiplication modulo n does not
straightaway give us a group because
some elements are not invertible but if
we simply take out if we simply exclude
those elements that are not invertible
then what we're left with is a group and
we'll denote that group by Zn star it's
not immediately obvious here that it's a
group because in particular it's not
immediately obvious that we have closure
that is it's not immediately obvious
that if I take two elements a and B both
of which are invertible then their
product a be mod n is also invertible
nevertheless this can be shown and it
does in fact hold the identity is
obviously going to be 1 the inverse of a
is going to be a inverse mod n this is
where we use the fact that we're
restricting attention to all invertible
elements only and as before for the case
of Zn the additive group modulo
associativity and commutativity here are
obvious because they follow from the
same properties over the integers and
again the exponentiation that is a to
the M mod and repeated multiplication of
a M times and taking the result modulo n
can be computed efficiently as well and
this follows from the fact that
multiplication can be done efficiently
and follows from the exponentiation
algorithm we saw in the previous lecture
what's the order of these different
groups
well we'll define fee of n where fee is
a Greek letter to exactly be the number
of invertible elements modulo n that is
a set of elements between 1 and n minus
1 whose GCD with n is equal to 1 and
this is precisely the order of Zn star
because we define Zn star to consist
precisely of those elements whose GCD
with n is equal to 1 when n is prime we
said earlier that every element between
1 and n minus 1 is in Zn star and so
when n is prime fee of n is equal to n
minus 1 that is the size or the order of
the group Zn star when n is prime is
exactly n minus 1 furthermore when n is
a product of two distinct Prime's then
we can compute V of n using the
characterization of the elements of Zn
star that we talked about a moment ago
so remember that VN star consists of
those elements that we get if we write
out the integers from 1 to n minus 1 and
then exclude all multiples of P and all
multiples of Q so this means we start
with a list of n minus 1 elements right
all the elements from from 1 to n minus
1 and then we exclude all the elements
of P well how many elements are sorry
all the multiples of P well how many
multiples of P are there well we have P
we have 2 P we have 3 P 4 P 5 P all the
way up to Q minus 1 times P Q P is
already too large QP is equal to n and
that's beyond the limit of our set so if
we cross out every multiple of P
there will be exactly Q minus 1 elements
that we cross out similarly if we cross
out every multiple of Q we end up
crossing out precisely P minus 1
elements and note here that no element
in the range of 1 to n minus 1 that can
be both a multiple of P and a multiple
of Q there's no double counting going on
here because again P times Q is equal to
n which is beyond the range of our set
so the total number of elements in Zn
star is given by our list n minus 1
minus the Q minus 1 elements we cross
out because they're multiples of P minus
the P minus 1 elements we cross out for
being multiples of Q and that simplifies
to the very nice form P minus 1 times Q
minus 1 so the upshot is that fee of n
when n is a product of two distinct
Prime's ie the size of Zn star when n is
a product of two distinct Prime's is
exactly P minus 1 times Q minus 1 ok so
let's go back now to our discussion of
abstract group theory a very important
theorem of group theory is called from
as little theorem and it says the
following let G be a finite group of
order M that is having M elements then
for any element in that group any
element G in that group it holds that G
to the M is equal to the identity ok so
here we're writing the group
multiplicatively and what the theorem
says is that if m is the order of the
group then if we repeatedly apply the
group operation to G M times then we get
the identity element the proof is
emitted it's again not something that's
very complicated but it's not very
important for our setting either just as
an example to illustrate the theorem if
we take the group Zn the group of
elements under addition modulo n then we
said earlier that this group has order N
and therefore what the theorem tells us
is that for any element a in that group
we have that n times a is equal to 0 mod
n this of course agrees with our
expectation because of course n times a
is going to have to be 0 mod
because na is divisible by n but very be
very careful here note that as we talked
about earlier a here is a group element
and n is an integer not an element of
the group in particular the integer n is
not an element of V n because V n
contains only the elements from 0 to n
minus 1 anyway what we're saying here
just matches our expectation but it does
fulfill or it does illustrate an
application of the theorem that's
another example if we look at the group
Zn star where this is the group of
invertible elements modulo n taken under
multiplication modulo n so what the
theorem tells us here is that for all a
in Zn star we have that a to the fee of
n is equal to 1 mod n right that is that
if we raise a to the fee of n power or
equivalently apply the group operation
which is just multiplication fee of n
times to any element a then we get the
identity element in Zn star which is of
course one in particular if n is prime
then for all elements a in Zn star which
is all a between 1 and n minus 1
inclusive we have a to the N minus 1 is
equal to 1 modulo M a corollary of from
our theorem is that if we let G be a
finite group of order M then for any
element G and any integer X we can
always reduce in the exponent that is G
to the X is equal to G to the X reduced
modulo M and the proof is one line so
let's write the integer X as Q times M
plus R this is just division with
remainder we divide X by M we get a
quotient Q and a remainder R well then
it holds that G to the X is certainly
equal to G to the Q M plus R we can just
reexpress that as G to the M to the Q
times G to the R but now from AHS little
theorem tells us that G to the M is
equal to 1 so this expression simplifies
to G to the R and of course our the
remainder of X divided by M is exactly
what bracket X mod M means and this is
very interesting because it means
it gives us something that can be used
to speed up exponentiation in particular
if we want to compute G to the X in some
group then what we can do is we can
always first reduce the exponent X
modular the order of the group so just
to take a kind of a silly example if we
were computing G to the one thousand and
five in some group of order 10 then
rather than computing the exponentiation
of G to the one thousand five which
would require you know some number of
repeated squaring and multiplications if
we use the exponentiation algorithm we I
talked about last time well what we can
do instead is simply reduce the exponent
one thousand five modular the order of
the group that is ten and get the result
five and we only then have to compute G
to the fifth power which is going to be
in general much much simpler another
corollary is the following and this
corollary is actually both very
important but a little bit hard to parse
so I want to walk through it let's let G
be a finite group of order m and then
for any integer e I want to define the
function f sub e F sub e is going to be
a function on the group and the function
f sub e is going to take as input a
group element G and return the group
element G to the eath power
ok so we're defining a function on the
group itself that takes an input and
raises it to the eath power the claim is
that if the GCD of E and M is equal to 1
then this function f sub E is in fact a
permutation that it is going to be a
bijection both one-to-one and onto so
the function f sub e will simply permute
the elements of the group in some way
moreover if we let D be equal to e
inverse modulo M and note that we know
that such a D exists precisely because
GCD M equals 1 means that E is
invertible modulo n well then the
function f sub d that is raising to the
DS power is the inverse of the function
f sub e so again it takes a bit of time
to parse this but what we're saying is
that
one F sub e is a permutation under the
stated conditions and furthermore that F
sub D will also be a permutation and in
particular will be the inverse of F sub
e the proof here is again one line so
once you understand what's going on the
proof is rather simple okay so it's two
lines so the first part follows from the
second that is if we can show that F D
is the inverse of F E then that in
particular implies that F E is a
permutation so let's prove that so we
want to show that for any element G if
we apply as e to G and then apply F D to
the result we should get back the same
element G well F D of F e of G is by
definition G to the e which is the
result of Fe of G and then we take that
and apply FD to that we get we raise
that to the D so it's just G to the e to
the D algebraically that's just the same
thing as G raised to the power of the
product of e and E but the previous
claim the one we had on the previous
slide tells us that to compute G to the
II D we can reduce the exponent modular
the order of the group which is M so
that's equal to G to the e d reduced mod
M but e and D are inverses modulo M so
that means that II D mod M is exactly 1
and of course G to the 1 is just G and
that completes the proof of this theorem
so it shows you had just a few simple
facts about groups can be used to prove
relatively powerful results in the next
lecture we're going to see how this
corollary leads to a computational
problem that in turn is very useful for
cryptography you may have even heard
about it that is the RSA problem as a
precursor to that we'll also talk about
the related factoring problem