summer-school-razvan-barbulescu-3301.pdf

Algebraic number theory

1. ECC summer school, 1 September 2016, Izmir
Overview - Algebraic Number Theory in
Cryptography
Razvan Barbulescu
CNRS and IMJ-PRG
R. Barbulescu | Overview - Algebraic Number Theory in Cryptography

2. Starting point
Notations
qprime
ga generator of (Fq)

Xa (secret) integer less thanq
Y=g
X
modq.
Quote
\Computing X from Y, on the other hand can be computed much more dicult and,
for certain carefully chosen values ofq, requires on the order ofq
1=2
operations [...]"
Die and Hellman 1976
Indeed, the best known algorithm in 1976 was Baby step giant step.
The DLP was as hard for (Fq)

as for any other group (e.g. elliptic curves).
R. Barbulescu | Overview - Algebraic Number Theory in Cryptography

3. TheLnotation
For any integerQ=e
n
,LQ(;c) = exp

cn

(logn)
1

.
Whencis not specied we writeLQ().
Example
ILQ(1;
1
2
) = exp

1
2
n

=
p
exp(n) =
p
Q(exponential algorithm).
ILQ(0;3) = exp(3logn) =n
3
(cubic algorithm)
ILQ(1=2;1) = exp
p
n
p
logn

exp
p
n

=e
p
n
(sub-exponential algorithm).
Exercice
L
Lx()() =Lx():
L()L() =L(max(;))
1+o(1)
.
R. Barbulescu | Overview - Algebraic Number Theory in Cryptography

4. History
IOne year after the introduction of DLP in cryptography, a subexponential
algorithm was proposed by Adleman (complexityL(1=2)).
IIn 1978 when RSA was proposed, it was known that the continued fractions
method of factorization was very fast. In early 80s Dixon and Pomerance proved
that there are algorithms of complexityL(1=2).
IIdeas traveled from factorization to discrete logarithm in nite elds and
vice-versa.
Chronology
Dates below give the publication year of the rst algorithm of each class. For discrete
logarithm, one uses dierent algorithms depending on the characteristic of the eld,
which have distinct publication dates.
complexity factorization
DLP
in nite elds
LQ(1=2) 1970
a
19791994
LQ(1=3) 1989 1984 2006
LQ() 2013
a
complexity unknown until 1980 (after the introduction of RSA)
R. Barbulescu | Overview - Algebraic Number Theory in Cryptography

5. Algorithms families
Let us use
early
sieve algorithms
created in 1975-1994
of complexityL(1=2)
factorization+DLP
elliptic curve method
created in 1985
of complexityL(1=2)
factorization
Rho + BSGS
created in 1971-1978
of complexity
p
N=L(1)
factorization+DLP
advanced
sieve algorithms
created in 1984-2006
of complexityL(1=3)
factorization+DLP
quasi-polynomial
created in 2013-
of complexityL()
DLP in eldsF
q
k
with smallq.
R. Barbulescu | Overview - Algebraic Number Theory in Cryptography

6. Plan of the lecture
IIntroduction
IIndex Calculus
IQuadratic sieve (QS/MPQS)
ISieving
R. Barbulescu | Overview - Algebraic Number Theory in Cryptography

7. Smoothness
Integers
denitionAn integer isB-smooth if all its prime factors are less thanB.
computationOne nds small prime divisors with ECM, which
is probabilistic;
relies on a conjecture of analytic number theory;
given an integerx, it nds all its factors less thanBin average time
LB(1=2;
p
2)
1+o(1)
log(x)
4
. In practice, the dependency in logxis quadratic.
Polynomials
denitionA polynomial inFq[t] ism-smooth if all its irreducible factors have
degree less than or equal tom.
computationOne tests if a polynomialP(t) ism-smooth by one of the two
methods below:
by factoring it (correctness is trivial, probabilistic, slow);
by taking gcd withP
0
(t)(t
q
m
t) (prove it!, deterministic, faster).
It is not known how to dene smooth elements on an elliptic curves
with a fast smoothness test.
R. Barbulescu | Overview - Algebraic Number Theory in Cryptography

8. Smoothness
Integers
denitionAn integer isB-smooth if all its prime factors are less thanB.
computationOne nds small prime divisors with ECM, which
is probabilistic;
relies on a conjecture of analytic number theory;
given an integerx, it nds all its factors less thanBin average time
LB(1=2;
p
2)
1+o(1)
log(x)
4
. In practice, the dependency in logxis quadratic.
Polynomials
denitionA polynomial inFq[t] ism-smooth if all its irreducible factors have
degree less than or equal tom.
computationOne tests if a polynomialP(t) ism-smooth by one of the two
methods below:
by factoring it (correctness is trivial, probabilistic, slow);
by taking gcd withP
0
(t)(t
q
m
t) (prove it!, deterministic, faster).
It is not known how to dene smooth elements on an elliptic curves
with a fast smoothness test.
R. Barbulescu | Overview - Algebraic Number Theory in Cryptography

9. DLP: an example (1)
Parameters
p= 12101
g= 7 is a generator ofG= (Z=pZ)

`= 11 is a prime factor of (p1) = #G
B= 10 is the smoothness bound
factor base 2;3;5;7
Finding relations among logs
7
5
modp= 4706 = 213181
The last relation gives:
7
73 +
75
25=
72 +
73
42
72 +
75:
R. Barbulescu | Overview - Algebraic Number Theory in Cryptography

10. DLP: an example (1)
Parameters
p= 12101
g= 7 is a generator ofG= (Z=pZ)

`= 11 is a prime factor of (p1) = #G
B= 10 is the smoothness bound
factor base 2;3;5;7
Finding relations among logs
7
5
modp= 13181
7
6
modp= 8740 = 2
2
51923The last relation gives:
7
73 +
75
25=
72 +
73
42
72 +
75:
R. Barbulescu | Overview - Algebraic Number Theory in Cryptography

11. DLP: an example (1)
Parameters
p= 12101
g= 7 is a generator ofG= (Z=pZ)

`= 11 is a prime factor of (p1) = #G
B= 10 is the smoothness bound
factor base 2;3;5;7
Finding relations among logs
7
5
modp= 13181
7
6
modp=
2
519237
7
modp= 675 = 3
3
5
2
The last relation gives:
7
73 +
75
25=
72 +
73
42
72 +
75:
R. Barbulescu | Overview - Algebraic Number Theory in Cryptography

12. DLP: an example (1)
Parameters
p= 12101
g= 7 is a generator ofG= (Z=pZ)

`= 11 is a prime factor of (p1) = #G
B= 10 is the smoothness bound
factor base 2;3;5;7
Finding relations among logs
7
5
modp= 13181
7
6
modp=
2
519237
7
modp= 675 = 3
3
5
2
The last relation gives:
7
73 +
75
25=
72 +
73
42
72 +
75:
R. Barbulescu | Overview - Algebraic Number Theory in Cryptography

13. DLP: an example (1)
Parameters
p= 12101
g= 7 is a generator ofG= (Z=pZ)

`= 11 is a prime factor of (p1) = #G
B= 10 is the smoothness bound
factor base 2;3;5;7
Finding relations among logs
7
5
modp= 13181
7
6
modp=
2
519237
7
modp=
3
5
2
7
8
modp=:::
The last relation gives:
7
73 +
75
25=
72 +
73
42
72 +
75:
R. Barbulescu | Overview - Algebraic Number Theory in Cryptography

14. DLP: an example (2)
Thanks to the Pohlig-Hellman reduction
we do the linear algebra computations modulo`= 11.
Linear algebra computations
We have to nd the unknown log
72, log
73 and lg
75 in the equation
0
B
@
0 3 2
8 1 0
6 0 2
1
C
A
0
B
@
log
72
log
73
log
75
1
C
A
0
B
@
7
25
42
1
C
Amod 11:
Conjecture
The matrix obtained by the technique above has maximal rank.
We can drop all conjectures by modifying the algorithm, but this variant is fast and,
even if the matrix has smaller rank we can nd logs.
Solution
We solve to obtain log
720 mod 11; log
733 mod 11 and log
7510 mod 11.
For this small example we can also use Pollard's rho method and obtain that
log
73 = 88693 mod 11:
R. Barbulescu | Overview - Algebraic Number Theory in Cryptography

15. DLP: an example (3)
At this point, we know discrete logarithms of the factor base and of smooth numbers:
log
7(10) = log
72 + log
7510 mod 11:
Smoothing by randomization
Consider a residue modulopwhich is not 10-smooth, e.g.h= 151. We take random
exponentsaand test is (g
a
h) modpisB-smooth.
The discrete logarithms of the two members are equal:
5
7(151) =
72 +
73:
We nd log
7(151)3 mod 11.
Remark
This part of the computations is independent of the relation collection and linear
algebra stages. It is called individual logarithm stage.
R. Barbulescu | Overview - Algebraic Number Theory in Cryptography

16. DLP: an example (3)
At this point, we know discrete logarithms of the factor base and of smooth numbers:
log
7(10) = log
72 + log
7510 mod 11:
Smoothing by randomization
Consider a residue modulopwhich is not 10-smooth, e.g.h= 151. We take random
exponentsaand test is (g
a
h) modpisB-smooth.
7
3
151 modp= 3389
The discrete logarithms of the two members are equal:
5
7(151) =
72 +
73:
We nd log
7(151)3 mod 11.
Remark
This part of the computations is independent of the relation collection and linear
algebra stages. It is called individual logarithm stage.
R. Barbulescu | Overview - Algebraic Number Theory in Cryptography

17. DLP: an example (3)
At this point, we know discrete logarithms of the factor base and of smooth numbers:
log
7(10) = log
72 + log
7510 mod 11:
Smoothing by randomization
Consider a residue modulopwhich is not 10-smooth, e.g.h= 151. We take random
exponentsaand test is (g
a
h) modpisB-smooth.
7
3
151 modp=
7
4
151 modp= 11622 = 2313149The discrete logarithms of the two members are equal:
5
7(151) =
72 +
73:
We nd log
7(151)3 mod 11.
Remark
This part of the computations is independent of the relation collection and linear
algebra stages. It is called individual logarithm stage.
R. Barbulescu | Overview - Algebraic Number Theory in Cryptography

18. DLP: an example (3)
At this point, we know discrete logarithms of the factor base and of smooth numbers:
log
7(10) = log
72 + log
7510 mod 11:
Smoothing by randomization
Consider a residue modulopwhich is not 10-smooth, e.g.h= 151. We take random
exponentsaand test is (g
a
h) modpisB-smooth.
7
3
151 modp=
7
4
151 modp= 3131497
5
151 modp= 8748 = 2
2
3
7
The discrete logarithms of the two members are equal:
5
7(151) =
72 +
73:
We nd log
7(151)3 mod 11.
Remark
This part of the computations is independent of the relation collection and linear
algebra stages. It is called individual logarithm stage.
R. Barbulescu | Overview - Algebraic Number Theory in Cryptography

19. DLP: an example (3)
At this point, we know discrete logarithms of the factor base and of smooth numbers:
log
7(10) = log
72 + log
7510 mod 11:
Smoothing by randomization
Consider a residue modulopwhich is not 10-smooth, e.g.h= 151. We take random
exponentsaand test is (g
a
h) modpisB-smooth.
7
3
151 modp=
7
4
151 modp= 3131497
5
151 modp= 8748 = 2
2
3
7
The discrete logarithms of the two members are equal:
5
7(151) =
72 +
73:
We nd log
7(151)3 mod 11.
Remark
This part of the computations is independent of the relation collection and linear
algebra stages. It is called individual logarithm stage.
R. Barbulescu | Overview - Algebraic Number Theory in Cryptography

20. Index Calculus
Input:
pprime,ggenerator of (Z=pZ)

,`prime divisor of (p1)
hinteger less thanp
Output:log
ghmod`
1:SetBto its optimal value
2:Make the listFof the primes less thanB(factor base) .Initialization
3:repeat
4:a Random([1,p-1])
5:if(g
a
modp) isB-smooththen
6: relations=relations
S
fag .Relations collection
7:end if
8:until#relations#F
9:Construct the matrixM= (ma;q),ain relations,q2 Fas follows
ma;q= valq(g
a
modp): . Linear algebra
10:Solve the linear system Mx= (a)ain relations.
11:repeat
12:b Random([1,p-1])
13:until(g
b
hmodp) isB-smooth
14:Factor (g
b
hmodp) =
Q
q
ei
i
.Individual logarithm
15:returnx=
P
eilog
g(qi)b
R. Barbulescu | Overview - Algebraic Number Theory in Cryptography

21. Plan of the lecture
IIntroduction
IIndex Calculus
IQuadratic sieve (QS/MPQS)
ISieving
R. Barbulescu | Overview - Algebraic Number Theory in Cryptography

22. Fermat's idea
Idea
Fermat (XVII century) computed solutions of the equation
X
2
Y
2
modN: (1)
It became a classical idea for factoring, e.g. mechanical machines were built in France
in early XX century to solve the above equation.
a
a
\Discovery of a lost factoring machine", Shallit, Wiliams, MorainLemma
If N=pq, Equation(1)has four solutions Y for each X6= 0.
Proof.
Using the identityX
2
Y
2
= (XY)(X+Y) we haveY Xmodpand
Y Xmodq. We callX
0
the unique integer less thanNwhich satises the system
Y Xmodp
YXmodq:
Then the solutions of Equation (1) areY=X,Y=X,Y=X
0
andY=X
0
.
50% of the solutions, i.e.X
0
andX
0
, give gcd(XY;N) =porq.
R. Barbulescu | Overview - Algebraic Number Theory in Cryptography

23. Fermat's idea
Idea
Fermat (XVII century) computed solutions of the equation
X
2
Y
2
modN: (1)
It became a classical idea for factoring, e.g. mechanical machines were built in France
in early XX century to solve the above equation.
a
a
\Discovery of a lost factoring machine", Shallit, Wiliams, MorainLemma
If N=pq, Equation(1)has four solutions Y for each X6= 0.
Proof.
Using the identityX
2
Y
2
= (XY)(X+Y) we haveY Xmodpand
Y Xmodq. We callX
0
the unique integer less thanNwhich satises the system
Y Xmodp
YXmodq:
Then the solutions of Equation (1) areY=X,Y=X,Y=X
0
andY=X
0
.
50% of the solutions, i.e.X
0
andX
0
, give gcd(XY;N) =porq.
R. Barbulescu | Overview - Algebraic Number Theory in Cryptography

24. Factoring: an example (1)
Not squares but smooth numbers
Let us factorN= 2041. We search integersasuch thata
2
Nis a square. In order to
keepa
2
Nsmall, we takeaapproximately equal to
p
N: 46, 47,:::. Squares seem to
be rare! Kraitchik (1922) proposed to collect integers which are 10-smooth.
We call factor base the set of primes less than 10: 2, 3, 5 and 7.
Collecting relations
46
2
N= 75 = 35
2
R. Barbulescu | Overview - Algebraic Number Theory in Cryptography

25. Factoring: an example (1)
Not squares but smooth numbers
Let us factorN= 2041. We search integersasuch thata
2
Nis a square. In order to
keepa
2
Nsmall, we takeaapproximately equal to
p
N: 46, 47,:::. Squares seem to
be rare! Kraitchik (1922) proposed to collect integers which are 10-smooth.
We call factor base the set of primes less than 10: 2, 3, 5 and 7.
Collecting relations
46
2
N= 75 = 35
2
47
2
N= 168 = 2
3
37
R. Barbulescu | Overview - Algebraic Number Theory in Cryptography

26. Factoring: an example (1)
Not squares but smooth numbers
Let us factorN= 2041. We search integersasuch thata
2
Nis a square. In order to
keepa
2
Nsmall, we takeaapproximately equal to
p
N: 46, 47,:::. Squares seem to
be rare! Kraitchik (1922) proposed to collect integers which are 10-smooth.
We call factor base the set of primes less than 10: 2, 3, 5 and 7.
Collecting relations
46
2
N= 75 = 35
2
47
2
N= 168 = 2
3
3748
2
N= 263 = 263
1
R. Barbulescu | Overview - Algebraic Number Theory in Cryptography

27. Factoring: an example (1)
Not squares but smooth numbers
Let us factorN= 2041. We search integersasuch thata
2
Nis a square. In order to
keepa
2
Nsmall, we takeaapproximately equal to
p
N: 46, 47,:::. Squares seem to
be rare! Kraitchik (1922) proposed to collect integers which are 10-smooth.
We call factor base the set of primes less than 10: 2, 3, 5 and 7.
Collecting relations
46
2
N= 75 = 35
2
47
2
N= 168 = 2
3
3748
2
N=
1
49
2
N= 360 = 2
3
3
2
5
R. Barbulescu | Overview - Algebraic Number Theory in Cryptography

28. Factoring: an example (1)
Not squares but smooth numbers
Let us factorN= 2041. We search integersasuch thata
2
Nis a square. In order to
keepa
2
Nsmall, we takeaapproximately equal to
p
N: 46, 47,:::. Squares seem to
be rare! Kraitchik (1922) proposed to collect integers which are 10-smooth.
We call factor base the set of primes less than 10: 2, 3, 5 and 7.
Collecting relations
46
2
N= 75 = 35
2
47
2
N= 168 = 2
3
3748
2
N=
1
49
2
N= 360 = 2
3
3
2
550
2
N= 459 = 3
3
17
R. Barbulescu | Overview - Algebraic Number Theory in Cryptography

29. Factoring: an example (1)
Not squares but smooth numbers
Let us factorN= 2041. We search integersasuch thata
2
Nis a square. In order to
keepa
2
Nsmall, we takeaapproximately equal to
p
N: 46, 47,:::. Squares seem to
be rare! Kraitchik (1922) proposed to collect integers which are 10-smooth.
We call factor base the set of primes less than 10: 2, 3, 5 and 7.
Collecting relations
46
2
N= 75 = 35
2
47
2
N= 168 = 2
3
3748
2
N=
1
49
2
N= 360 = 2
3
3
2
550
2
N=
3
17
51
2
N= 560 = 2
4
57
R. Barbulescu | Overview - Algebraic Number Theory in Cryptography

30. Factoring: an example (2)
Combining relations
With the previous relations we have, for all non-negative integersu46,u47,u49,u51:

46
2u46
47
2u47
49
2u49
51
2u51

2
3u47+3u49+4u51
3
u46+u47+2u49
5
2u46+u49+u51
7
u47+u51
modN
Linear algebra stage
We ndu46,u47,u49,u51inZ=2Zsatisfying
u47+ 3u49+ 4u510 mod 2
u46+u47+ 2u490 mod 2
2u46+u49+u510 mod 2
u47+u510 mod 2:
We obtainu46=u47=u49=u51= 1.
R. Barbulescu | Overview - Algebraic Number Theory in Cryptography

31. Factoring: an example (3)
ComputingX
We multiply the left sides of all the relations to nd
X= 46
u46
47
u47
49
u49
51
u51
modN
= 46474951 modN
= 311:
ComputingY
We multiply the right sides of all the relations to nd
Y=

2
3u47+3u49+4u51
3
u46+u47+2u49
5
2u46+u49+u51
7
u47+u51

1=2
modN
= 2
5
3
2
5
2
7 modN
= 1416:
Euclid gives the factorization!
SinceX6 YmodN, we succeed. We compute
gcd(YX;N) = gcd(1416311;2041) = 13:
The factorization is 2041 = 13157.
R. Barbulescu | Overview - Algebraic Number Theory in Cryptography

32. Quadratic sieve
Input:integerN=pqfor two primespandq
Output:pandq
1:SetBto its optimal value
2:Make the listFof the primes less thanB(factor base) .Initialization
3:a b
p
Nc
4:repeata a+ 1
5:if(a
2
N) isB-smooththen
6: relations=relations
S
fag .Relations collection
7:end if
8:until#relations#F
9:Construct the matrixM= (ma;q),ain relations,q2 Fas follows
ma;q= valq

a
2
N

: . Linear algebra
10:Solve the linear system transpose(x)M0 mod 2.
11:ComputeX=
Q
ain relations
a
xa
.
12:ComputeY=
Q
q2F
q
(
P
a
xa)=2
.
13:Computeg= gcd(XY;N) .Square root
14:ifg6= 1 orNthen
15:returnp=g,q=N=g
16:else
17:Find more relations and do the linear algebra again.
18:end if
R. Barbulescu | Overview - Algebraic Number Theory in Cryptography

33. Plan of the lecture
IIntroduction
IIndex Calculus
IQuadratic sieve (QS/MPQS)
ISieving
R. Barbulescu | Overview - Algebraic Number Theory in Cryptography

34. The idea of sieving
What we need
In QS, we collect integersa=d
p
Ne+x, wherexis a small integer, such thata
2
N
isB-smooth.
We need to nd the smooth values ofQ(x), whenQ(x) =

d
p
Ne+x

2
N.
Eratosthenes sieve
Given a polynomialQ(x)2Z[x], one can compute the valuesxin an interval [E1;E2]
such thatQ(x) is prime. One marks with a line every value ofxwhich is divisible by
two, then by three and so on. The values ofxwhich have no marks correspond to
prime values ofQ.
Numbers which have many marks are smooth.
R. Barbulescu | Overview - Algebraic Number Theory in Cryptography

35. The idea of sieving
What we need
In QS, we collect integersa=d
p
Ne+x, wherexis a small integer, such thata
2
N
isB-smooth.
We need to nd the smooth values ofQ(x), whenQ(x) =

d
p
Ne+x

2
N.
Eratosthenes sieve
Given a polynomialQ(x)2Z[x], one can compute the valuesxin an interval [E1;E2]
such thatQ(x) is prime. One marks with a line every value ofxwhich is divisible by
two, then by three and so on. The values ofxwhich have no marks correspond to
prime values ofQ.
Numbers which have many marks are smooth.
R. Barbulescu | Overview - Algebraic Number Theory in Cryptography

36. Sieving: an example
Problem
Find valuesain the interval [3;7] such thatQ(a) =a
2
+ 1 is prime, respectively
6-smooth.
Table of sieving
a 3 4 5 6 7
ticks
log(a
2
+ 1)log 10 log 17 log 26 log 37 log 50
Computations Consider primes less than 6 and their powers less than maxfQ(a)ja2[2;7]g:
p= 2, solutions ofa
2
+ 10 mod 2 aref1g;
q= 2
2
, solutions ofa
2
+ 10 mod 4 are?;p= 3, solutions ofa
2
+ 10 mod 3 are?;p= 5, solutions ofa
2
+ 10 mod 5 aref2;3g;p= 5
2
, solutions ofa
2
+ 10 mod 25 aref7;18g
Conclusion
The prime values ofQareQ(4) = 17 andQ(6) = 37.
The 6-smooth values ofQareQ(3) = 10 andQ(7) = 50.
R. Barbulescu | Overview - Algebraic Number Theory in Cryptography

37. Sieving: an example
Problem
Find valuesain the interval [3;7] such thatQ(a) =a
2
+ 1 is prime, respectively
6-smooth.
Table of sieving
a 3 4 5 6 7
ticks
log(a
2
+ 1)log 10 log 17 log 26 log 37 log 50
Computations Consider primes less than 6 and their powers less than maxfQ(a)ja2[2;7]g:
p= 2, solutions ofa
2
+ 10 mod 2 aref1g;
q= 2
2
, solutions ofa
2
+ 10 mod 4 are?;p= 3, solutions ofa
2
+ 10 mod 3 are?;p= 5, solutions ofa
2
+ 10 mod 5 aref2;3g;p= 5
2
, solutions ofa
2
+ 10 mod 25 aref7;18g
Conclusion
The prime values ofQareQ(4) = 17 andQ(6) = 37.
The 6-smooth values ofQareQ(3) = 10 andQ(7) = 50.
R. Barbulescu | Overview - Algebraic Number Theory in Cryptography

38. Sieving: an example
Problem
Find valuesain the interval [3;7] such thatQ(a) =a
2
+ 1 is prime, respectively
6-smooth.
Table of sieving
a 3 4 5 6 7
ticks l l l
log(a
2
+ 1)log 5 log 17 log 13 log 37 log 25
Computations Consider primes less than 6 and their powers less than maxfQ(a)ja2[2;7]g:
p= 2, solutions ofa
2
+ 10 mod 2 aref1g;
q= 2
2
, solutions ofa
2
+ 10 mod 4 are?;p= 3, solutions ofa
2
+ 10 mod 3 are?;p= 5, solutions ofa
2
+ 10 mod 5 aref2;3g;p= 5
2
, solutions ofa
2
+ 10 mod 25 aref7;18g
Conclusion
The prime values ofQareQ(4) = 17 andQ(6) = 37.
The 6-smooth values ofQareQ(3) = 10 andQ(7) = 50.
R. Barbulescu | Overview - Algebraic Number Theory in Cryptography

39. Sieving: an example
Problem
Find valuesain the interval [3;7] such thatQ(a) =a
2
+ 1 is prime, respectively
6-smooth.
Table of sieving
a 3 4 5 6 7
ticks l l l
log(a
2
+ 1)log 5 log 17 log 13 log 37 log 25
Computations Consider primes less than 6 and their powers less than maxfQ(a)ja2[2;7]g:
p= 2, solutions ofa
2
+ 10 mod 2 aref1g;
q= 2
2
, solutions ofa
2
+ 10 mod 4 are?;p= 3, solutions ofa
2
+ 10 mod 3 are?;p= 5, solutions ofa
2
+ 10 mod 5 aref2;3g;p= 5
2
, solutions ofa
2
+ 10 mod 25 aref7;18g
Conclusion
The prime values ofQareQ(4) = 17 andQ(6) = 37.
The 6-smooth values ofQareQ(3) = 10 andQ(7) = 50.
R. Barbulescu | Overview - Algebraic Number Theory in Cryptography

40. Sieving: an example
Problem
Find valuesain the interval [3;7] such thatQ(a) =a
2
+ 1 is prime, respectively
6-smooth.
Table of sieving
a 3 4 5 6 7
ticks l l l
log(a
2
+ 1)log 5 log 17 log 13 log 37 log 25
Computations Consider primes less than 6 and their powers less than maxfQ(a)ja2[2;7]g:
p= 2, solutions ofa
2
+ 10 mod 2 aref1g;
q= 2
2
, solutions ofa
2
+ 10 mod 4 are?;p= 3, solutions ofa
2
+ 10 mod 3 are?;p= 5, solutions ofa
2
+ 10 mod 5 aref2;3g;p= 5
2
, solutions ofa
2
+ 10 mod 25 aref7;18g
Conclusion
The prime values ofQareQ(4) = 17 andQ(6) = 37.
The 6-smooth values ofQareQ(3) = 10 andQ(7) = 50.
R. Barbulescu | Overview - Algebraic Number Theory in Cryptography

41. Sieving: an example
Problem
Find valuesain the interval [3;7] such thatQ(a) =a
2
+ 1 is prime, respectively
6-smooth.
Table of sieving
a 3 4 5 6 7
ticks ll l ll
log(a
2
+ 1)0 log 17 log 13 log 37 log 5
Computations Consider primes less than 6 and their powers less than maxfQ(a)ja2[2;7]g:
p= 2, solutions ofa
2
+ 10 mod 2 aref1g;
q= 2
2
, solutions ofa
2
+ 10 mod 4 are?;p= 3, solutions ofa
2
+ 10 mod 3 are?;p= 5, solutions ofa
2
+ 10 mod 5 aref2;3g;p= 5
2
, solutions ofa
2
+ 10 mod 25 aref7;18g
Conclusion
The prime values ofQareQ(4) = 17 andQ(6) = 37.
The 6-smooth values ofQareQ(3) = 10 andQ(7) = 50.
R. Barbulescu | Overview - Algebraic Number Theory in Cryptography

42. Sieving: an example
Problem
Find valuesain the interval [3;7] such thatQ(a) =a
2
+ 1 is prime, respectively
6-smooth.
Table of sieving
a 3 4 5 6 7
ticks ll l lll
log(a
2
+ 1)0 log 17 log 13 log 37 0
Computations Consider primes less than 6 and their powers less than maxfQ(a)ja2[2;7]g:
p= 2, solutions ofa
2
+ 10 mod 2 aref1g;
q= 2
2
, solutions ofa
2
+ 10 mod 4 are?;p= 3, solutions ofa
2
+ 10 mod 3 are?;p= 5, solutions ofa
2
+ 10 mod 5 aref2;3g;p= 5
2
, solutions ofa
2
+ 10 mod 25 aref7;18g
Conclusion
The prime values ofQareQ(4) = 17 andQ(6) = 37.
The 6-smooth values ofQareQ(3) = 10 andQ(7) = 50.
R. Barbulescu | Overview - Algebraic Number Theory in Cryptography

43. Sieving: an example
Problem
Find valuesain the interval [3;7] such thatQ(a) =a
2
+ 1 is prime, respectively
6-smooth.
Table of sieving
a 3 4 5 6 7
ticks ll l lll
log(a
2
+ 1)0 log 17 log 13 log 37 0
Computations Consider primes less than 6 and their powers less than maxfQ(a)ja2[2;7]g:
p= 2, solutions ofa
2
+ 10 mod 2 aref1g;
q= 2
2
, solutions ofa
2
+ 10 mod 4 are?;p= 3, solutions ofa
2
+ 10 mod 3 are?;p= 5, solutions ofa
2
+ 10 mod 5 aref2;3g;p= 5
2
, solutions ofa
2
+ 10 mod 25 aref7;18g
Conclusion
The prime values ofQareQ(4) = 17 andQ(6) = 37.
The 6-smooth values ofQareQ(3) = 10 andQ(7) = 50.
R. Barbulescu | Overview - Algebraic Number Theory in Cryptography

44. Algorithm for sieving
Algorithm
Input:a monic polynomialQ(x) inZ[x] and parametersB,E1,E2;
Output:all the integersx2[E1;E2] for whichQ(x) isB-smooth.
1:Make a list (p
k
;r) of prime powersp
k
maxfjQ(x)j;x2[E1;E2]g, withp<B,
and integers 0r<p
k
such thatQ(r)0 modp
k
2:Dene an array indexed byx2[E1;E2] and initialize it with log
2jQ(x)j
3:forall (p
k
;r) considered abovedo
4:forxin [E1;E2] andxrmodp
k
do
5: Subtract log
2pfrom the entry of indexx;
6:end for
7:end for
8:Collect the indicesxwhere the array is close to 0 (numerical errors).
Cofactorization
In practice we sieve on primes smaller than a boundfbb<Band we collect indicesx
whose value is smaller than a threshold. Then we test smoothness with ECM on the
survivals in a step called cofactorization. In the literature, the smoothness boundBis
calledlpb, \large prime bound", to distinguish fromfbb, actor base bound".
Exercice
What is the condition onfbbandlpbsuch that ECM is not needed, i.e., we know that
there is only one large prime.
R. Barbulescu | Overview - Algebraic Number Theory in Cryptography