Khảo sát các thuật toán kiểm định số nguyên tố lớn và ứng dụng

ĐẠI HỌC THÁI NGUYÊN

TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

NGUYỄN THỊ MỴ

KHẢO SÁT CÁC THUẬT TOÁN KIỂM ĐỊNH

SỐ NGUYÊN TỐ LỚN VÀ ỨNG DỤNG.

Chuyên ngành: KHOA HỌC MÁY TÍNH

Mã số : 60.48.01.01

LUẬN VĂN THẠC SĨ

HƢỚNG DẪN KHOA HỌC: PGS TSKH NGUYỄN XUÂN HUY

THÁI NGUYÊN – 2017

i

LỜI CAM ĐOAN

T i xin m o n y l ng tr nh nghi n u ri ng t i, s liệu v

kết quả nghi n u trong luận v n n y l trung th v kh ng tr ng l p với

t i kh T i ng xin m o n r ng mọi s gi p cho việ th

hiện luận v n n y ã ƣợ ảm ơn v th ng tin trí h dẫn trong luận v n ã

ƣợ hỉ rõ nguồn g

T giả

Nguyễn Thị Mỵ

\

ii

LỜI CẢM ƠN

T i xin b y tỏ s kính trọng v lòng biết ơn s u sắ ến PGS.TSKH.

Nguyễn Xuân Huy - ngƣời ã tận t nh hƣớng dẫn v gi p t i trong su t

qu tr nh họ tập, nghi n u v ho n th nh luận v n, xin ảm ơn thầy,

gi o trong v ngo i trƣờng ã ung ấp kiến th v tạo i u kiện thuận lợi

ho qu tr nh họ tập v rèn luyện bản th n t i

T i ng xin ƣợ b y tỏ lòng biết ơn h n th nh ến B n Gi m Hiệu,

thầy gi o, gi o phòng S u ại họ trƣờng Đại họ C ng Nghệ Th ng

Tin &Truy nTh ng, thầy gi o ở Viện C ng Nghệ Th ng Tin ã giảng dạy

v tạo mọi i u kiện ho t i họ tập, nghi n u v ho n th nh luận v n n y

Xin ảm ơn gi nh, bạn bè ã hết lòng gi p , khí h lệ, ộng vi n t i

ể t i ho n th nh luận v n

Thái Nguyên, tháng 03 năm 2017

T giả

Nguyễn Thị Mỵ

iii

DANH MỤC CÁC KÝ HIỆU TRONG LUẬN VĂN

Kí hiệu Ý nghĩa

ℝ Tập s th

ℝ

+ Tập s th kh ng m

ℕ Tập s t nhi n (kể ả 0)

ℤ Tập s nguy n

ℤ

+

Tập s nguy n kh ng m, ℤ

+

= ℕ

(a, b), gcd (a,b) Ƣớ hung lớn nhất a v b

Ordn(b) Bậ b theo modulo n

ℤ/n V nh nguy n theo modulo n.

Nếu n nguy n theo th ℤ/n l trƣờng

ℤ[x] V nh th nguy n

≡ To n ẳng, tƣơng ƣơng, ồng dƣ

ϕ(n) H m phi Euler

L, BitLen(n) S bit biểu diễn nhị ph n n

logn log rit ơ s 2 n

lgamma(n) log((n1)!)

(

)

( )

Tổ hợp hập k n

iv

DANH MỤC CÁC BẢNG TRONG LUẬN VĂN

Bảng Tên các bảng trong luận văn Trang

1.1 Ph n b s nguy n t 10

1.2 Một v i s nguy n t Mersenne 16

1.3 Một s p nguy n t sinh i 17

1.4 Một s s nguy n t Sophie Germ in 17

1.5 V i s gi i thừ nguy n t 18

1.6 20 s nguy n t ầu ti n v h m n#, pn# 19

1.7 Một s s nguy n t gi i th y ã biết 20

1.8 Thời gi n m y tính d ng ể ph n tí hs n r thừ s nguy n t 24

2.1 C s nguy n t v hợp s trong khoảng 2100-1 l s biệt 31

2.2 C phép + v ⋅ trong v nh ℤ/7 49

3.1 C phƣơng th lớp BI 52

3.2 Bậ s trong ℤ/7 61

3.3 H i phần tử sinh ℤ/7 62

v

MỤC LỤC

LỜI CẢM ƠN...................................................................................................II

DANH MỤC CÁC KÝ HIỆU TRONG LUẬN VĂN.................................... III

DANH MỤC CÁC BẢNG TRONG LUẬN VĂN.........................................IV

MỞ ĐẦU........................................................................................................... 1

CHƢƠNG1. TỔNG QUAN VỀ SỐ NGUYÊN TỐ ....................................... 4

1.1 Các định nghĩa và khái niệm mở đầu........................................................ 4

1.2 Một số tính chất của số nguyên tố ............................................................. 7

1.3 Sự phân bổ của số nguyên tố...................................................................... 9

1.4 Số giả nguyên tố........................................................................................ 11

1.5 Số Mersenne.............................................................................................. 13

1.6 Số Fermat.................................................................................................. 16

1.7 Các số nguyên tố lớn................................................................................. 17

1 7 1 C s nguy n t sinh i ............................................................ 17

1 7 2 C s nguy n t Sophie Germ in ............................................... 17

1 7 3 C s gi i thừ nguy n t ........................................................... 18

1 7 4 C s nguy n t gi i th y ........................................................... 19

1.8 Ứng dụng của số nguyên tố ...................................................................... 21

1 8 1 Mật mã v s nguy n t ............................................................... 21

1 8 2 C hệ mật mã ng kh i ............................................................. 21

CHƢƠNG 2. CÁC THUẬT TOÁN KIỂM ĐỊNH SỐ NGUYÊN TỐ ......... 26

2.1 Các lớp P và NP........................................................................................ 26

2.2 Thuật toán kiểm định theo√ .................................................................. 28

2.3 Sàng Eratosthenes .................................................................................... 30

2.4 Thuật toán kiểm định theo xác suất MILLER-RABIN.......................... 31

2 4 1 Cơ sở to n họ ............................................................................. 31

2 4 2 Thuật to n Miller Test ................................................................. 36

vi

2 4 3 Thuật to n Miller-Rabin............................................................... 36

2 4 4 C trƣờng hợp biệt ............................................................... 37

2.5 Kiểm định theo giả thuyết Riemann........................................................ 38

2.6 Thuật toán kiểm định tính nguyên tố AKS ............................................. 39

2.6 1 Giới thiệu hung .......................................................................... 39

2.6 2 Định lí AKS................................................................................. 40

2.6 3 Thuật to n.................................................................................... 41

2.6 4 Một s kiến th to n họ ........................................................... 42

2.7 Thuật toán Bernstein................................................................................ 46

2.7 1 Định lí Bernstein.......................................................................... 46

2.7 2 Thuật to n Bernstein .................................................................... 47

CHƢƠNG 3. CÀI ĐẶT VÀ ỨNG DỤNG..................................................... 48

3 1 Lớp BI........................................................................................................ 49

3 1 1 Nhận xét hung ............................................................................ 49

3 1 2 C trƣờng dữ liệu ....................................................................... 49

3 1 3 C phƣơng th .......................................................................... 49

3.2 Lớp ARITHM........................................................................................... 55

3 2 1 Ƣớ hung lớn nhất...................................................................... 55

3 2 2 H m phi Euler.............................................................................. 55

3 2 3 S hính n ................................................................................ 56

3 2 4 Bậ theo modulo .......................................................................... 58

3 2 5 C n nguy n th y .......................................................................... 59

3 2 6 S nguy n t s t s u..................................................................... 61

3 2 7 Kiểm tr ƣớ nguy n t ................................................................ 62

3 2 8 Ƣớ nguy n t lớn nhất................................................................ 64

3 2 9 Nh n modulo ............................................................................... 66

3 2 10 L y thừ modulo........................................................................ 67

vii

3.3 Lớp BIPOL............................................................................................... 67

3 3 1 C trƣờng dữ liệu ....................................................................... 67

3 3 2 C phƣơng th .......................................................................... 67

3.4 Lớp MR..................................................................................................... 72

3.5 Lớp AKS ................................................................................................... 72

3.6 Ứng dụng .................................................................................................. 72

KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN ........................................................ 73

TÀI LIỆU THAM KHẢO ................................................................................ 79

1

MỞ ĐẦU

Số nguyên tố l s t nhi n lớn hơn một v hỉ hi hết ho một v hính nó

Định nghĩ v s nguy n t m d ơn giản v ngắn gọn nhƣng những

vấn xo y qu nh nó lu n l m nh to n họ qu n t m

S nguy n t l một trong những kh i niệm xƣ nhất to n họ C

s nguy n t l vật liệu ơ bản x y d ng n n s t nhi n V s

nguy n t t ng l n v hạn n n u hỏi ầu ti n t r l : Có bao nhiêu số

nguyên tố? Có thể liệt k tất ả h ng r h y h ng lập th nh một dãy s v

hạn Để h ng minh i u n y Eu lid ã ƣ r một lập luận, xuất ph t từ giả

thiết phản h ng r ng dãy s nguy n t l hữu hạn, s u ó hỉ r một s

nguy n t mới kh với s nguy n t ã ó M u thuẫn n y ho biết tập s

nguy n t l vô hạn.

S u khi Eu lid h ng minh ó v s s nguy n t , nhi u u hỏi

xung qu nh s nguy n t ƣợ ƣ r Một s những u hỏi ó, dƣới

những ph t biểu ơn giản, ã trở th nh những b i to n trong lị h sử to n họ

m ho ến n y vẫn hƣ ó ƣợ lời giải trọn vẹn

Ngƣời t kh ng t m thấy một s tuần ho n n o trong dãy s nguy n t

S ph n b s nguy n t tỏ r ph tạp v kh ng ó quy luật Việ

ph t hiện s nguy n t lớn trong một thời gi n d i l s qu n t m

nhi u nh to n họ Tuy nhi n ho ến n y trong s họ vẫn òn tồn tại nhi u

giả thuyết mở v s nguy n t Hơn nữ , trong thời ại ng nghệ th ng tin

ng y n y việ nghi n u s nguy n t ng ƣợ kí h thí h bởi s kiện l

s nguy n t tỏ r rất ó í h trong việ mã hó v giải mã th ng tin Tính

bảo mật v n to n qu tr nh tr o ổi khó v hệ mật mã khó ng

khai ƣợ ảm bảo b ng ộ ph tạp b i to n s họ ph n tí h một s

nguy n th nh tí h thừ s nguy n t Nói h kh , vấn thời gi n ti u

t n ho việ hạy m y tính ể th hiện b i to n ph n tí h một s nguy n