Cyclic Groups and Discrete Logarithms
Discrete Log
Slides by Prof. Jonathan Katz.
Lightly edited by me.
Cyclic groups
Cyclic groups
•
Let G be a finite group of order m (written
multiplicatively)
•
Let g be some element of G
•
Consider the set <g> = {g0
, g
1
, …}
–
We know g
m
= 1 = g
0
, so the set has ≤
m
elements
–
If the set has
m
elements, then it is all of G !
•
In this case, we say g is a
generator
of G
•
If G has a generator, we say G is
cyclic
•
A cyclic group can have more than one generator
Examples
•
ℤ
N
–
Cyclic (for any N); 1 is always a generator:
{0, 1, 2, …, N-1}•
ℤ
8
–
Is 3 a generator?
{0, 3, 6, 1, 4, 7, 2, 5} – yes!–
Is 2 a generator?
{0, 2, 4, 6} – no!Example
•
ℤ
*
11
–
Is 3 a generator?
{1, 3, 9, 5, 4} – no!–
Is 2 a generator?
{1, 2, 4, 8, 5, 10, 9, 7, 3, 6} – yes!–
Is 8 a generator?
{1, 8, 9, 6, 4, 10, 3, 2, 5, 7} – yes!Note that elements appear in a different order
from above…
Example
•
ℤ
*
13
–
<2> = {1, 2, 4, 8, 3, 6, 12, 11, 9, 5, 10, 7},so 2 is a generator
–
<8> = {1, 8, 12, 5},so 8 is not a generator
Important examples
•
Theorem:
Any group of
prime order
is cyclic,
and every non-identity element is a generator
•
Theorem:
If p is prime, then
ℤ
*
p
is cyclic
–
Note: the order is p-1, which is not prime for p > 3
Uniform sampling
•
Given cyclic group G of order q along with
generator g, easy to sample a uniform h
G:
–
Choose uniform x
{0, …, q-1}; set h := gx
Discrete-logarithm problem
•
Fix cyclic group G of order q, and generator g
•
We know that {g0
, g
1
, …, g
q-1
} = G
–
For every h
G, there is a unique x
ℤ
q
s.t. g
x
= h
–
Define log
g
h to be this x –
the discrete logarithm
of h with respect to g
(in the group G)
Examples
•
In
ℤ
*
11
–
What is log
2
9?
•
<2> = {1, 2, 4, 8, 5, 10, 9, 7, 3, 6}, so log2
9 = 6
–
What is log
8
9?
•
<8> = {1, 8, 9, 6, 4, 10, 3, 2, 5, 7}, so log8
9 = 2
•
In
ℤ
*
13
–
What is log
2
9?
•
<2> = {1, 2, 4, 8, 3, 6, 12, 11, 9, 5, 10, 7}, so log2
9 = 8
Discrete-logarithm problem (informal)
•
Dlog problem in G:
Given generator g and
element h, compute log
g
h
•
Dlog assumption in G:
Solving the discrete log
problem in G is hard
–
Careful: not hard to compute log
g
h for
all
h, but
hard for a randomly chosen h
Example
•
In
ℤ
*
3092091139
–
What is log
2
1656755742 ?
Discrete-logarithm problem
•
Let
G
be a group-generation algorithm
–
On input 1
n
, outputs a (description of a) cyclic
group G, its order q (with
ǁqǁ
=n), and a generator g
•
For algorithm A, define exp’t Dlog
A,
G
(n):
–
Compute (G, q, g)
G
(1
n
)
–
Choose uniform h
G
–
Run A(G, q, g, h) to get x
–
Experiment evaluates to 1 if g
x
= h
Discrete-logarithm problem
•
The
discrete-logarithm problem is hard
relative to
G
if for all PPT algorithms A,
Pr[Dlog
A,
G
(n) = 1]
≤ negl(n)
Exploring the concepts of cyclic groups and discrete logarithms in group theory. This presentation covers the definition of generators, examples of cyclic groups, important theorems related to prime orders and cyclic groups, uniform sampling in cyclic groups, and the discrete logarithm problem. Examples are provided to illustrate these concepts.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Discrete Log Slides by Prof. Jonathan Katz. Lightly edited by me.
Cyclic groups Let G be a finite group of order m (written multiplicatively) Let g be some element of G Consider the set <g> = {g0, g1, } We know gm = 1 = g0, so the set has m elements If the set has m elements, then it is all of G ! In this case, we say g is a generator of G If G has a generator, we say G is cyclic A cyclic group can have more than one generator
Examples N Cyclic (for any N); 1 is always a generator: {0, 1, 2, , N-1} 8 Is 3 a generator? {0, 3, 6, 1, 4, 7, 2, 5} yes! Is 2 a generator? {0, 2, 4, 6} no!
Example *11 Is 3 a generator? {1, 3, 9, 5, 4} no! Is 2 a generator? {1, 2, 4, 8, 5, 10, 9, 7, 3, 6} yes! Is 8 a generator? {1, 8, 9, 6, 4, 10, 3, 2, 5, 7} yes! Note that elements appear in a different order from above
Example *13 <2> = {1, 2, 4, 8, 3, 6, 12, 11, 9, 5, 10, 7}, so 2 is a generator <8> = {1, 8, 12, 5}, so 8 is not a generator
Important examples Theorem: Any group of prime order is cyclic, and every non-identity element is a generator Theorem: If p is prime, then *p is cyclic Note: the order is p-1, which is not prime for p > 3
Uniform sampling Given cyclic group G of order q along with generator g, easy to sample a uniform h G: Choose uniform x {0, , q-1}; set h := gx
Discrete-logarithm problem Fix cyclic group G of order q, and generator g We know that {g0, g1, , gq-1} = G For every h G, there is a unique x q s.t. gx = h Define loggh to be this x the discrete logarithm of h with respect to g (in the group G)
Examples In *11 What is log2 9? <2> = {1, 2, 4, 8, 5, 10, 9, 7, 3, 6}, so log2 9 = 6 What is log8 9? <8> = {1, 8, 9, 6, 4, 10, 3, 2, 5, 7}, so log8 9 = 2 In *13 What is log2 9? <2> = {1, 2, 4, 8, 3, 6, 12, 11, 9, 5, 10, 7}, so log2 9 = 8
Discrete-logarithm problem (informal) Dlog problem in G: Given generator g and element h, compute loggh Dlog assumption in G: Solving the discrete log problem in G is hard Careful: not hard to compute loggh for all h, but hard for a randomly chosen h
Example In *3092091139 What is log2 1656755742 ?
Discrete-logarithm problem Let G be a group-generation algorithm On input 1n, outputs a (description of a) cyclic group G, its order q (with q =n), and a generator g For algorithm A, define exp t DlogA,G(n): Compute (G, q, g) G(1n) Choose uniform h G Run A(G, q, g, h) to get x Experiment evaluates to 1 if gx = h
Discrete-logarithm problem The discrete-logarithm problem is hard relative to Gif for all PPT algorithms A, Pr[DlogA,G(n) = 1] negl(n)
