Cryptography and Number Theory Crash Course
Intro. Number Theory
Notation
Online Cryptography Course Dan Boneh
Background
We will use a bit of number theory to construct:
•
Key exchange protocols
•
Digital signatures
•
Public-key encryption
This module: crash course on relevant concepts
More info:
read parts of Shoup’s book referenced
at end of module
Notation
From here on:
•
N denotes a positive integer.
•
p denote a prime.
Notation:
Can do addition and multiplication modulo N
Modular arithmetic
Examples: let N = 12
9 + 8 = 5 in
5 × 7 = 11 in
5 − 7 = 10 in
Arithmetic in works as you expect, e.g x
⋅
(y+z) = x
⋅
y + x
⋅
z in
Greatest common divisor
Def
: For ints. x,y:
gcd(x, y)
is the
greatest common divisor
of x,y
Example:
gcd( 12, 18 ) = 6
Fact
: for all ints. x,y there exist ints. a,b such that
a
⋅
x + b
⋅
y = gcd(x,y)
a,b can be found efficiently using the extended Euclid alg.
If gcd(x,y)=1 we say that x and y are
relatively prime
Modular inversion
Over the rationals, inverse of 2 is ½ . What about ?
Def
: The
inverse
of x in is an element y in s.t.
y is denoted x
-1
.
Example: let N be an odd integer. The inverse of 2 in is
Modular inversion
Which elements have an inverse in ?
Lemma
: x in has an inverse if and only if gcd(x,N) = 1
Proof:
gcd(x,N)=1
⇒
∃
a,b: a
⋅
x + b
⋅
N = 1
gcd(x,N) > 1
⇒
∀
a: gcd( a
⋅
x, N ) > 1
⇒
a
⋅
x ≠ 1 in
More notation
Def:
= (set of invertible elements in ) =
=
{ x
∈
: gcd(x,N) = 1
}
Examples:
1.
for prime p,
2.
= { 1, 5, 7, 11}For x in , can find x
-1
using extended Euclid algorithm.
Solving modular linear equations
Solve:
a
⋅
x + b = 0 in
Solution:
x = −b
⋅
a
-1
in
Find a
-1
in using extended Euclid. Run time: O(log
2
N)
What about modular quadratic equations?
next segments
End of Segment
Intro. Number Theory
Fermat and Euler
Online Cryptography Course Dan Boneh
Review
N denotes an n-bit positive integer. p denotes a prime.
•
Z
N
= { 0, 1, …, N-1 }•
(Z
N
)
*
= (set of invertible elements in Z
N
) =
=
{ x
∈
Z
N
: gcd(x,N) = 1
}
Can find inverses efficiently using Euclid alg.: time = O(n
2
)
Fermat’s theorem
(1640)
Thm
:
Let p be a prime
∀
x
∈
(Z
p
)
*
:
x
p-1
= 1 in Z
p
Example: p=5. 3
4
= 81 = 1 in Z
5
So: x
∈
(Z
p
)
*
⇒
x
⋅
x
p-2
= 1
⇒
x
−1
= x
p-2
in Z
p
another way to compute inverses, but less efficient than Euclid
Application: generating random primes
Suppose we want to generate a large random prime
say, prime p of length 1024 bits ( i.e. p ≈ 2
1024
)
Step 1: choose a random integer p
∈
[ 2
1024
, 2
1025
-1 ]
Step 2: test if 2
p-1
= 1 in Z
p
If so, output p and stop. If not, goto step 1 .
Simple algorithm (not the best).
Pr[ p not prime ] < 2
-60
The structure of
(Z
p
)
*
Thm
(Euler): (Z
p
)
*
is a
cyclic group
, that is
∃
g
∈
(Z
p
)
*
such that
{1, g, g
2
, g
3
, …, g
p-2
}
= (Z
p
)
*
g is called a
generator
of (Z
p
)
*
Example: p=7. {1, 3, 32
, 3
3
, 3
4
, 3
5
} = {1, 3, 2, 6, 4, 5} = (Z7
)
*
Not every elem. is a generator: {1, 2, 22
, 2
3
, 2
4
, 2
5
} = {1, 2, 4}Order
For g
∈
(Z
p
)
*
the set {1 , g , g2
, g
3
, …
} is called
the
group generated by g
, denoted <g>
Def
: the
order
of g
∈
(Z
p
)
*
is the size of <g>
ord
p
(g) = |<g>| = (smallest a>0 s.t. g
a
= 1 in Z
p
)
Examples: ord
7
(3) = 6 ; ord
7
(2) = 3 ; ord
7
(1) = 1
Thm
(Lagrange):
∀
g
∈
(Z
p
)
*
:
ord
p
(g)
divides p-1
Euler’s generalization of Fermat
(1736)
Def
: For an integer N define ϕ (N) =
|
(Z
N
)
*
|
(Euler’s ϕ func.)
Examples: ϕ (12) =
|
{1,5,7,11}|
= 4 ; ϕ (p) = p-1
For N=p
⋅
q:
ϕ (N) = N-p-q+1 = (p-1)(q-1)
Thm
(Euler):
∀
x
∈
(Z
N
)
*
:
x
ϕ(N)
= 1 in Z
N
Example: 5
ϕ(12)
= 5
4
= 625 = 1 in Z
12
Generalization of Fermat. Basis of the RSA cryptosystem
End of Segment
Intro. Number Theory
Modular e’th roots
Online Cryptography Course Dan Boneh
Modular e’th roots
We know how to solve modular
linear
equations:
a
⋅
x + b = 0
in
Z
N
Solution:
x = −b
⋅
a
-1
in Z
N
What about higher degree polynomials?
Example: let p be a prime and c
∈
Z
p
. Can we solve:
x
2
– c = 0 , y
3
– c = 0 , z
37
– c = 0 in Z
p
Modular e’th roots
Let p be a prime and c
∈
Z
p
.
Def
: x
∈
Z
p
s.t. x
e
= c in Z
p
is called an
e’th root
of c .
Examples:
7
1/3
= 6 in
3
1/2
= 5 in
1
1/3
= 1 in
The easy case
When does
c
1/e
in Z
p
exist? Can we compute it efficiently?
The easy case
: suppose gcd( e , p-1 ) = 1
Then for all c in (Z
p
)
*
:
c
1/e
exists in Z
p
and is easy to find.
Proof: let
d = e
-1
in Z
p-1
. Then
d
⋅
e = 1 in Z
p-1
⇒
The case e=2: square roots
If p is an odd prime then gcd( 2, p-1) ≠ 1
Fact
: in , x
⟶
x
2
is a 2-to-1 function
Example
: in :
Def
: x in is a
quadratic residue
(Q.R.) if it has a square root in
p odd prime
⇒
the # of Q.R. in is (p-1)/2 + 1
Euler’s theorem
Thm:
x in (Z
p
)
*
is a Q.R.
⟺
x
(p-1)/2
= 1 in Z
p
(p odd prime)
Example:
Note: x≠0
⇒
x
(p-1)/2
=
(
x
p-1
)
1/2
= 1
1/2
∈
{ 1, -1 } in Zp
Def
: x
(p-1)/2
is called the
Legendre Symbol
of x over p
(1798)
Computing square roots mod p
Suppose p = 3 (mod 4)
Lemma
: if c
∈
(Z
p
)
*
is Q.R. then
√
c = c
(p+1)/4
in Z
p
Proof:
When p = 1 (mod 4), can also be done efficiently, but a bit harder
run time ≈ O(log
3
p)
Solving quadratic equations mod p
Solve:
a
⋅
x
2
+ b
⋅
x + c = 0 in Z
p
Solution:
x = (-b ±
√
b
2
– 4
⋅
a
⋅
c ) / 2a in Z
p
•
Find
(2a)
-1
in Z
p
using extended Euclid.
•
Find square root of
b
2
– 4
⋅
a
⋅
c
in Z
p
(if one exists)
using a square root algorithm
Computing e’th roots mod N ??
Let N be a composite number and e>1
When does
c
1/e
in Z
N
exist? Can we compute it efficiently?
Answering these questions requires the factorization of N
(as far as we know)
End of Segment
Intro. Number Theory
Arithmetic algorithms
Online Cryptography Course Dan Boneh
Representing bignums
Representing an n-bit integer (e.g. n=2048) on a 64-bit machine
Note: some processors have 128-bit registers (or more)
and support multiplication on them
32 bits
32 bits
32 bits
32 bits
⋯
n/32 blocks
Arithmetic
Given: two n-bit integers
•
Addition and subtraction
: linear time O(n)
•
Multiplication
: naively O(n
2
). Karatsuba
(1960)
: O(n
1.585
)
Basic idea: (2
b
x
2
+ x
1
) × (2
b
y
2
+ y
1
) with 3 mults.
Best (asymptotic) algorithm: about O(n
⋅
log n).
•
Division with remainder
: O(n
2
).
Exponentiation
Finite cyclic group G (for example G = )
Goal: given g in G and x compute g
x
Example
: suppose x = 53 = (110101)
2
= 32+16+4+1
Then: g
53
= g
32+16+4+1
= g
32
⋅
g
16
⋅
g
4
⋅
g
1
g
⟶
g
2
⟶
g
4
⟶
g
8
⟶
g
16
⟶
g
32
g
53
The repeated squaring alg.
Input
: g in G and x>0 ;
Output
: g
x
write x = (x
n
x
n-1
… x
2
x
1
x
0
)
2
y
⟵
g , z
⟵
1
for i = 0 to n do:
if (x[i] == 1): z
⟵
z
⋅
y
y
⟵
y
2
output z
example: g
53
y
z
g
2
g
g
4
g
g
8
g
5
g
16
g
5
g
32
g
21
g
64
g
53
Running times
Given n-bit int. N:
•
Addition and subtraction in Z
N
: linear time T
+
= O(n)
•
Modular multiplication in Z
N
: naively T
×
= O(n
2
)
•
Modular exponentiation in Z
N
( g
x
)
:
O
(
(log x)
⋅
T
×
)
≤ O
(
(log x)
⋅
n
2
)
≤ O( n
3
)
End of Segment
Intro. Number Theory
Intractable problems
Online Cryptography Course Dan Boneh
Easy problems
•
Given composite N and x in Z
N
find x
-1
in Z
N
•
Given prime p and polynomial f(x) in Z
p
[x]
find x in Z
p
s.t. f(x) = 0 in Z
p
(if one exists)
Running time is linear in deg(f) .
… but many problems are difficult
Intractable problems with primes
Fix a prime p>2 and g in (Z
p
)
*
of order q.
Consider the function:
x
⟼
g
x
in Z
p
Now, consider the inverse function:
Dlog
g
(g
x
) = x
where x in {0, …, q-2}Example:
DLOG: more generally
Let
G
be a finite cyclic group and
g
a generator of G
G =
{1 , g , g
2
, g
3
, … , g
q-1
}
( q is called the order of G )
Def
: We say that
DLOG is hard in G
if for all efficient alg. A:
Pr
g
⟵
G, x
⟵
Z
q
[
A( G, q, g, g
x
) = x
]
< negligible
Example candidates:
(1) (Z
p
)
*
for large p, (2) Elliptic curve groups mod p
Computing Dlog in (Z
p
)
*
(n-bit prime p)
Best known algorithm (GNFS): run time exp( )
cipher key size
modulus size
80 bits
1024 bits
128 bits
3072 bits
256 bits (AES)
15360
bits
As a result: slow transition away from (mod p) to elliptic curves
160 bits
256 bits
512 bits
An application: collision resistance
Choose a group G where Dlog is hard (e.g. (Z
p
)
*
for large p)
Let q = |G| be a prime. Choose generators g, h of G
For x,y
∈
{1,…,q} define H(x,y) = g
x
⋅
h
y
in G
Lemma
:
finding collision for H(.,.) is as hard as computing Dlog
g
(h)
Proof: Suppose we are given a collision H(x
0
,y
0
) = H(x
1
,y
1
)
then
g
x
0
⋅
h
y
0
=
g
x
1
⋅
h
y
1
⇒
g
x
0
-x
1
=
h
y
1
-y
0
⇒
h = g
x
0
-x
1
/y
1
-y
0
Intractable problems with composites
Consider the set of integers: (e.g. for n=1024)
Problem 1
: Factor a random N in (e.g. for n=1024)
Problem 2
: Given a polynomial
f(x)
where degree(f) > 1
and a random N in
find x in s.t. f(x) = 0 in
The factoring problem
Gauss (1805):
Best known alg. (NFS): run time exp( ) for n-bit integer
Current world record:
RSA-768
(232 digits)
•
Work: two years on hundreds of machines
•
Factoring a 1024-bit integer: about 1000 times harder
⇒
likely possible this decade
“The problem of distinguishing prime numbers from
composite numbers and of resolving the latter into
their prime factors is known to be one of the most
important and useful in arithmetic.”
Further reading
•
A Computational Introduction to Number Theory and Algebra,
V. Shoup, 2008 (V2), Chapter 1-4, 11, 12
A
v
a
i
l
a
b
l
e
a
t
/
/
s
h
o
u
p
.
n
e
t
/
n
t
b
/
n
t
b
-
v
2
.
p
d
f
End of Segment
In the last module we saw that number theory can be useful for key exchange. In this module we will review some basic facts from number theory that will help us build many public key systems next week. As we go through the material it might help to pause the video from time to time to make sure all the examples are clear.
Background on the use of number theory in constructing key exchange protocols, digital signatures, and public-key encryption. Covers notation, modular arithmetic, greatest common divisor, modular inversion, invertible elements, and solving modular linear equations efficiently using the extended Euclidean algorithm. Next segments will explore modular quadratic equations.
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. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Online Cryptography Course Dan Boneh Intro. Number Theory Notation Dan Boneh
Background We will use a bit of number theory to construct: Key exchange protocols Digital signatures Public-key encryption This module: crash course on relevant concepts More info: read parts of Shoup s book referenced at end of module Dan Boneh
Notation From here on: N denotes a positive integer. p denote a prime. Notation: Can do addition and multiplication modulo N Dan Boneh
Modular arithmetic Examples: let N = 12 9 + 8 = 5 in 5 7 = 11 in 5 7 = 10 in Arithmetic in works as you expect, e.g x (y+z) = x y + x z in Dan Boneh
Greatest common divisor Def: For ints. x,y: gcd(x, y) is the greatest common divisor of x,y Example: gcd( 12, 18 ) = 6 Fact: for all ints. x,y there exist ints. a,b such that a x + b y = gcd(x,y) a,b can be found efficiently using the extended Euclid alg. If gcd(x,y)=1 we say that x and y are relatively prime Dan Boneh
Modular inversion Over the rationals, inverse of 2 is . What about ? Def: The inverse of x in is an element y in s.t. y is denoted x-1 . Example: let N be an odd integer. The inverse of 2 in is Dan Boneh
Modular inversion Which elements have an inverse in ? Lemma: x in has an inverse if and only if gcd(x,N) = 1 Proof: gcd(x,N)=1 a,b: a x + b N = 1 gcd(x,N) > 1 a: gcd( a x, N ) > 1 a x 1 in Dan Boneh
More notation Def: = (set of invertible elements in ) = = { x : gcd(x,N) = 1 } Examples: 1. for prime p, = { 1, 5, 7, 11} 2. , can find x-1 using extended Euclid algorithm. For x in Dan Boneh
Solving modular linear equations Solve: a x + b = 0 in Solution: x = b a-1 in Find a-1 in using extended Euclid. Run time: O(log2 N) What about modular quadratic equations? next segments Dan Boneh
End of Segment Dan Boneh
Online Cryptography Course Dan Boneh Intro. Number Theory Fermat and Euler Dan Boneh
Review N denotes an n-bit positive integer. p denotes a prime. ZN = { 0, 1, , N-1 } (ZN)* = (set of invertible elements in ZN) = = { x ZN : gcd(x,N) = 1 } Can find inverses efficiently using Euclid alg.: time = O(n2) Dan Boneh
Fermats theorem (1640) Thm: Let p be a prime x (Zp)* : xp-1 = 1 in Zp Example: p=5. 34 = 81 = 1 in Z5 So: x (Zp)* x xp-2 = 1 x 1 = xp-2 in Zp another way to compute inverses, but less efficient than Euclid Dan Boneh
Application: generating random primes Suppose we want to generate a large random prime say, prime p of length 1024 bits ( i.e. p 21024 ) Step 1: choose a random integer p [ 21024 , 21025-1 ] Step 2: test if 2p-1 = 1 in Zp If so, output p and stop. If not, goto step 1 . Simple algorithm (not the best). Pr[ p not prime ] < 2-60 Dan Boneh
The structure of (Zp)* Thm (Euler): (Zp)* is a cyclic group, that is g (Zp)* such that {1, g, g2, g3, , gp-2} = (Zp)* g is called a generator of (Zp)* Example: p=7. {1, 3, 32, 33, 34, 35} = {1, 3, 2, 6, 4, 5} = (Z7)* Not every elem. is a generator: {1, 2, 22, 23, 24, 25} = {1, 2, 4} Dan Boneh
Order For g (Zp)* the set {1 , g , g2, g3, } is called the group generated by g, denoted <g> Def: the order of g (Zp)* is the size of <g> ordp(g) = |<g>| = (smallest a>0 s.t. ga = 1 in Zp) Examples: ord7(3) = 6 ; ord 7(2) = 3 ; ord7(1) = 1 Thm (Lagrange): g (Zp)* : ordp(g) divides p-1 Dan Boneh
Eulers generalization of Fermat (1736) Def: For an integer N define (N) = |(ZN)*| (Euler s func.) Examples: (12) = |{1,5,7,11}| = 4 ; (p) = p-1 For N=p q: (N) = N-p-q+1 = (p-1)(q-1) Thm (Euler): x (ZN)* : x (N) = 1 in ZN Example: 5 (12) = 54 = 625 = 1 in Z12 Generalization of Fermat. Basis of the RSA cryptosystem Dan Boneh
End of Segment Dan Boneh
Online Cryptography Course Dan Boneh Intro. Number Theory Modular e th roots Dan Boneh
Modular eth roots We know how to solve modular linear equations: a x + b = 0 in ZN Solution: x = b a-1 in ZN What about higher degree polynomials? Example: let p be a prime and c Zp . Can we solve: x2 c = 0 , y3 c = 0 , z37 c = 0 in Zp Dan Boneh
Modular eth roots Let p be a prime and c Zp . Def: x Zp s.t. xe = c in Zp is called an e th root of c . Examples: 71/3 = 6 in 31/2 = 5 in 21/2 does not exist in 11/3 = 1 in Dan Boneh
The easy case When does c1/e in Zpexist? Can we compute it efficiently? The easy case: suppose gcd( e , p-1 ) = 1 Then for all c in (Zp)*: c1/eexists in Zp and is easy to find. Proof: let d = e-1 in Zp-1 . Then d e = 1 in Zp-1 Dan Boneh
The case e=2: square roots If p is an odd prime then gcd( 2, p-1) 1 x x x2 , x x2 is a 2-to-1 function Fact: in Example: in : 1 10 2 9 4 7 5 6 3 8 1 4 5 3 9 Def: x in is a quadratic residue (Q.R.) if it has a square root in p odd prime the # of Q.R. in is (p-1)/2 + 1 Dan Boneh
Eulers theorem Thm: x in (Zp)* is a Q.R. x(p-1)/2= 1 in Zp (p odd prime) Example: in : 15, 25, 35, 45, 55, 65, 75, 85, 95, 105 = 1 -1 1 1 1, -1, -1, -1, 1, -1 Note: x 0 x(p-1)/2 = (xp-1)1/2 = 11/2 { 1, -1 } in Zp Def: x(p-1)/2 is called the Legendre Symbol of x over p (1798) Dan Boneh
Computing square roots mod p Suppose p = 3 (mod 4) Lemma: if c (Zp)* is Q.R. then c = c(p+1)/4 in Zp Proof: When p = 1 (mod 4), can also be done efficiently, but a bit harder run time O(log3 p) Dan Boneh
Solving quadratic equations mod p Solve: a x2 + b x + c = 0 in Zp Solution: x = (-b b2 4 a c ) / 2a in Zp Find (2a)-1 in Zpusing extended Euclid. Find square root of b2 4 a c in Zp (if one exists) using a square root algorithm Dan Boneh
Computing eth roots mod N ?? Let N be a composite number and e>1 When does c1/e in ZNexist? Can we compute it efficiently? Answering these questions requires the factorization of N (as far as we know) Dan Boneh
End of Segment Dan Boneh
Online Cryptography Course Dan Boneh Intro. Number Theory Arithmetic algorithms Dan Boneh
Representing bignums Representing an n-bit integer (e.g. n=2048) on a 64-bit machine 32 bits 32 bits 32 bits 32 bits n/32 blocks Note: some processors have 128-bit registers (or more) and support multiplication on them Dan Boneh
Arithmetic Given: two n-bit integers Addition and subtraction: linear time O(n) Multiplication: naively O(n2). Karatsuba (1960): O(n1.585) Basic idea: (2b x2+ x1) (2b y2+ y1) with 3 mults. Best (asymptotic) algorithm: about O(n log n). Division with remainder: O(n2). Dan Boneh
Exponentiation Finite cyclic group G (for example G = ) Goal: given g in G and x compute gx Example: suppose x = 53 = (110101)2 = 32+16+4+1 Then: g53 = g32+16+4+1= g32 g16 g4 g1 g g2 g4 g8 g16 g32 g53 Dan Boneh
The repeated squaring alg. Input: g in G and x>0 ; Output: gx example: g53 y z g2 g g4 g g8 g5 g16 g5 g32 g21 g64g53 write x = (xn xn-1 x2 x1 x0)2 y g , z 1 for i = 0 to n do: if (x[i] == 1): z z y y y2 output z Dan Boneh
Running times Given n-bit int. N: Addition and subtraction in ZN: linear time T+ = O(n) Modular multiplication in ZN: naively T = O(n2) Modular exponentiation in ZN ( gx ): O( (log x) T ) O( (log x) n2) O( n3 ) Dan Boneh
End of Segment Dan Boneh
Online Cryptography Course Dan Boneh Intro. Number Theory Intractable problems Dan Boneh
Easy problems Given composite N and x in ZN find x-1 in ZN Given prime p and polynomial f(x) in Zp[x] find x in Zp s.t. f(x) = 0 in Zp (if one exists) Running time is linear in deg(f) . but many problems are difficult Dan Boneh
Intractable problems with primes Fix a prime p>2 and g in (Zp)* of order q. gxin Zp Consider the function: x Now, consider the inverse function: Dlogg (gx) = x where x in {0, , q-2} in : 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 Example: Dlog2( ) : 0, 1, 8, 2, 4, 9, 7, 3, 6, 5 Dan Boneh
DLOG: more generally Let Gbe a finite cyclic group and ga generator of G G = { 1 , g , g2 , g3, , gq-1} ( q is called the order of G ) Def: We say that DLOG is hard in G if for all efficient alg. A: Pr g G, x Zq [ A( G, q, g, gx) = x ] < negligible Example candidates: (1) (Zp)* for large p, (2) Elliptic curve groups mod p Dan Boneh
Computing Dlog in (Zp)* (n-bit prime p) Best known algorithm (GNFS): run time exp( ) Elliptic Curve group size 160 bits 256 bits 512 bits cipher key size 80 bits 128 bits 256 bits (AES) modulus size 1024 bits 3072 bits 15360 bits As a result: slow transition away from (mod p) to elliptic curves Dan Boneh
An application: collision resistance Choose a group G where Dlog is hard (e.g. (Zp)* for large p) Let q = |G| be a prime. Choose generators g, h of G For x,y {1, ,q} define H(x,y) = gx hy in G Lemma: finding collision for H(.,.) is as hard as computing Dlogg(h) Proof: Suppose we are given a collision H(x0,y0) = H(x1,y1) then gx0 hy0 =gx1 hy1 gx0-x1 =hy1-y0 h = g x0-x1/y1-y0 Dan Boneh
Intractable problems with composites Consider the set of integers: (e.g. for n=1024) := { N = p q where p,q are n-bit primes } Problem 1: Factor a random N in (e.g. for n=1024) Problem 2: Given a polynomial f(x) where degree(f) > 1 and a random N in find x in s.t. f(x) = 0 in Dan Boneh
The factoring problem The problem of distinguishing prime numbers from composite numbers and of resolving the latter into their prime factors is known to be one of the most important and useful in arithmetic. Gauss (1805): Best known alg. (NFS): run time exp( ) for n-bit integer Current world record: RSA-768 (232 digits) Work: two years on hundreds of machines Factoring a 1024-bit integer: about 1000 times harder likely possible this decade Dan Boneh
Further reading A Computational Introduction to Number Theory and Algebra, V. Shoup, 2008 (V2), Chapter 1-4, 11, 12 Available at //shoup.net/ntb/ntb-v2.pdf Dan Boneh
End of Segment Dan Boneh
