1 of 39

Number Field Sieve

Cryptography Seminar Fall 2018

2 of 39

2

“A Tale of Two Sieves” by Carl Pomerance

An insightful and beautifully written exposition on the methods and history of using sieves to factor.

Another good reference.

3 of 39

Number Field Sieve History

  •  

3

4 of 39

Number Field Sieve: Set Up

4

 

 

 

 

 

5 of 39

Number Field Sieve

  •  

5

 

6 of 39

The Set S

  •  

6

(Property 1)

(Property 2)

7 of 39

The Set S

Why do we want S?

7

 

 

8 of 39

The Set S: Property 1

  •  

8

 

 

What about Property 2?

9 of 39

Property 2

9

 

Ideally, we want:

 

This gives unique factorization into primes. This usually won’t be true.

10 of 39

Property 2

10

 

Ideally, we want:

 

Get unique factorization of ideals into prime ideals.

11 of 39

Property 2

11

 

Ideally, we want:

 

 

 

12 of 39

Property 2

12

 

Ideally, we want:

 

Then we can repeat a similar sieving argument.

13 of 39

  •  

13

14 of 39

How do we do anything?

  •  

14

 

 

15 of 39

Number Field Sieve: First Steps

  •  

15

 

 

16 of 39

Factoring Primitive Polynomials

  •  

16

polynomial time:

17 of 39

Factoring Primitive Polynomials

  •  

17

 

18 of 39

Factoring Primitive Polynomials

  •  

18

19 of 39

The Norm Map

  •  

19

 

20 of 39

Sieving Norms

  •  

20

21 of 39

CounterExample

21

 

22 of 39

Primes Above p

  •  

22

 

23 of 39

Elongating the Exponent Vector

Define

​

23

 

 

24 of 39

Elongating the Exponent Vector

  •  

24

 

But we’re getting a bit closer.

25 of 39

Obstructions

25

 

Algebraic Object

 

 

 

 

 

26 of 39

The Obstruction Group

Let

26

 

27 of 39

  •  

27

28 of 39

  •  

28

29 of 39

 

  •  

29

30 of 39

A Minor Problem

30

 

 

 

31 of 39

A Major Problem

31

 

 

32 of 39

The Square Root Problem

  • Solving the square root problem is faster than sieving and linear algebra with exponent vectors.
  • In practice, this won’t be an issue.

32

33 of 39

Run Time

  •  

33

34 of 39

Comparison of Methods

34

Method

Run Time

Trial Division

​

Quadratic Sieve

​

Number Field Sieve

​

35 of 39

Comparison of Methods

35

 

 

36 of 39

36

 

 

37 of 39

37

 

 

38 of 39

Concluding Remarks

In practice, number field sieve is faster for digits > 130.

38

Record: Largest number factored by number field sieve is RSA-768 (232 digits)

RSA-768 = 12301866845301177551304949583849627207728535695953347921973224521517264005 07263657518745202199786469389956474942774063845925192557326303453731548268 50791702612214291346167042921431160222124047927473779408066535141959745985 6902143413 =

33478071698956898786044169848212690817704794983713768568912431388982883793 878002287614711652531743087737814467999489 × 36746043666799590428244633799627952632279158164343087642676032283815739666 511279233373417143396810270092798736308917

​

39 of 39

39

Thank you.