ĐẠI HỌC BÁCH KHOA HÀ NỘI

LUẬN VĂN THẠC SĨ
NGHIÊN CỨU THUẬT TỐN CHỨNG MINH
TÍNH NGUN TỐ CỦA MỘT SỐ NGUN DỰA
TRÊN KỸ THUẬT TÍNH TỐN CỦA ĐƯỜNG
CONG ELLIPTIC

Nguyen Thanh Long

Hà Nội - 2023

1


MỤC LỤC
LỜI CẢM ƠN............................................................................................................. i
LỜI CAM ĐOAN ...................................................................................................... ii
MỤC LỤC ... ......................................................................................................iii
DANH MỤC HÌNH VẼ ..................................................................................................v
DANH MỤC KÝ HIỆU............................................................................................... vi
LỜI MỞ ĐẦU ..... ...... .. ................ ..................................................................
vii
CHƯƠNG 1: TỔNG QUAN VỀ MỘT SỐ THUẬT TỐN KIỂM TRA TÍNH
NGUN TỐ CỦA SỐ NGUYÊN. ......................................................................... 1
1.1 Lịch sử, vai trò số nguyên tố sử dụng trong mật mã .........................................1
1.1.1 Giới thiệu về số học .....................................................................................1
1.1.2 Các kết quả lý thuyết số học đại số ..............................................................4
1.2 Một số thuật tốn kiểmtra tính ngun tố....................................................... 12
1.2.1 Thuật tốn kiểm tra tính ngun tố theo xác suất .....................................12
1.2.2 Thuật tốn kiểm tra tính ngun tố tất định ............................................. 14

1.2.3 Thuật toán kiểm tra dựa trên sự phân rã N-1(tương ứng N+1) ............... 15
1.3 Kết luận chương 1 ............................................................................................ 20
CHƯƠNG 2: THUẬT TỐN CHỨNG MINH TÍNH NGUYÊN TỐ DỰA TRÊN
ĐƯỜNG CONG ELLIPTIC ....................................................................................... 21
2.1 Tổng quan số học đường cong elliptic ............................................................. 21
2.1.1 Một số khái niệm đường cong đại số .......................................................... 21
2.1.2 Tự đồng cấu frobenius ............................................................................... 26
2.1.3 Bậc của nhóm ............................................................................................ 28
2.1.4 Thuật tốn ECPP ...................................................................................... 31
2.2 Thuật tốn chứng minh tính ngun tố dựa trên đường cong elliptic... 32
2.2.1 Thuật toán ECPP của Goldwasser-Kilian .................................................. 32
2.2.2 Thuật toán ECPP của Atkin ....................................................................... 41
2.2.3 Tính đúng đắn của thuật tốn ECPP của Atkin .......................................... 48
2.3 Kết luận chương 2 ............................................................................................ 53
CHƯƠNG 3: XÂY DỰNG CHƯƠNG TRÌNH THUẬT TỐN CHỨNG MINH TINH
NGUN TỐ DỰA TRÊN DƯỜNG CONG ELLIPTIC ....................................................... 55
3.1 Môi trường thực thi chương trình ...................................................................55
3.2 Xây dựng chương trình chứng minh tính ngun tố ECPP của một số
nguyên dựa trên kỹ thuật tính toán của đường cong elliptic .................................57
3.2.1 Lưu đồ thuật toán ECPP của Atkin ............................................................ 57
2


3.2.2 Tạo Project C++ ....................................................................................... 59
3.2.3 Lập trình, thực thi một số hàm được sử dụng trong thuật toán ECPP của
Atkin ............................................................................................................ 60
3.2.4 Kết quả đạt được và đánh giá ....................................................................62
3.3 Phân tích đánh giá độ phức tạp tính tốn cho thuật toán ECPP của Atkin .. .
65
3.4 Kết luận chương 3........................................................................................... 67

KẾT LUẬN............................................................................................................. 68
TÀI LIỆU THAM KHẢO ......................................................................................... 69
PHỤ LỤC ............................................................................................................... 70

3


DANH MỤC HÌNH VẼ
Hình 3.1: Cài đặt Java ............................................................................................... 55
Hình 3.2: Kiểm tra phiên bản Java ............................................................................ 56
Hình 3.3: Cài đặt NetBeans thành cơng ..................................................................... 56
Hình 3.4: Trang chủ NetBeans .................................................................................. 56
Hình 3.5: Tạo Project C++ ........................................................................................ 59
Hình 3.6:Chọn đường dẫn lưu Project ....................................................................... 60
Hình 3.7: Tạo makefile cho Project ........................................................................... 60
Hình 3.8: Hàm rand2 ................................................................................................. 61
Hình 3.9: Hàm gcd .................................................................................................... 61
Hình 3.10:

Hàm inverse ....................................................................................... 61

Hình 3.11:

Hàm modps ........................................................................................ 62

Hình 3.12:

Hàm exp_mod.................................................................................... 62

Hình 3.13:


Hàm exp_pow .................................................................................... 62

Hình 3.14:

Khởi tạo các giá trị mầm .................................................................... 63

Hình 3.15: Nhập số nguyên 210 chữ số cần kiểm tra ................................................. 63
Hình 3.16:Kết quả đạt được (số nguyên 210 chữ số) với

thời gian thực thi..... 64

Hình 3.17: Nhập số nguyên 300 chữ số cần kiểm tra ................................................. 64
Hình 3.18: Kết quả đạt được(số nguyên 300 chữ số) với

4

thời gian thực thi..... 65


DANH MỤC KÝ HIỆU
Tiếng Việt

Viết tắt

Tiếng Anh

ECPP

Elliptic curve primality proving


RSA

Rivest - Shamir - Adleman

Kiểm tra số nguyên tố trên đường
cong elliptic

gcd

Ước chung lớn nhất

lcm

Bội chung nhỏ nhất

Cl(D)

Form class group

Nhóm lớp dạng

CM

Complex multiplication

Lý thuyết nhân phức

5



LỜI MỞ ĐẦU
Số nguyên tố là chủ đề trọng tâm của lý thuyết số và có nhiều ứng dụng trong các
lĩnh vực của toán học, đặc biệt trong mật mã hiện đại. Một số thuật tốn mật mã khóa
cơng khai, chẳng hạn như RSA, trao đổi khóa Diffle-Hellman dựa trên số nguyên tố lớn
(khoảng 2048 bit), hàm băm, ... đều cần số nguyên tố lớn làm đầu vào thuật toán. Vì vậy
việc tính số ngun tố lớn và đánh giá xem số đó có là số ngun tố hay khơng là một
vấn đề quan trọng trong mật mã hiện đại. Việc nghiên cứu các phương pháp kiểm tra
tính nguyên tố được nghiên cứu từ thế kỷ 17 thể hiện định lý của Fermat, Sollovay và
Strassen vào năm 1977. Sau đó được Miller và Rabin phát triển ý tưởng kiểm tra tính
nguyên tố theo lý thuyết xác suất.
Vào năm 1985, H.W.Lentra đề xuất cách sử dụng các tính tốn đường cong
elliptic trong việc phân tích các số ngun. Sau đó Goldwasser và Kilian phát triển việc
kiểm tra tính nguyên tố dựa vào nhóm các điểm hữu tỷ của đường cong elliptic trên
trường hữu hạn (thuật toán ECPP). Atkin và Morain đề xuất một ý tưởng tốt hơn cho
việc chứng minh tính nguyên tố dựa trên đường cong elliptic.
Tiếp đó, việc chứng minh tính nguyên tố được thiết kế bởi Adleman, Pomerence
và Rumely, thuật tốn của họ đã có thời gian chạy khá tốt. Thuật tốn có thời gian chạy
là đa thức với độ phức tạp đa thức được mong đợi. Cách tiếp cận phù hợp với sử dụng
trong thực tế. Năm 2007, Morain và et.la, đã đưa ra một thực thi cho thuật toán ECPP
với hiệu quả thực thi tốt và tối ưu hơn cho thuật toán ECPP.
Nội dung của đồ án được chia làm 3 nội dung như sau:
Chương 1: Tổng quan về một số thuật tốn chứng minh tính nguyên tố của
số nguyên.
Chương này trình bày tổng quan về cơ sở toán học của một số thuật toán chứng
minh tính ngun tố và thuật tốn ECPP trong mật mã.
Chương 2: Thuật tốn chứng minh tính ngun tố dựa trên đường cong
Elliptic.
Chương này đưa ra cơ sở toán học của thuật tốn chứng minh tính ngun tố dựa
trên đường cong elliptic và trình bày chi tiết hai thuật tốn chứng mình tính ngun tố

dựa trên đường cong elliptic của Goldwasser-Kilian và Atkin.
Chương 3: Xây dựng chương trình thuật tốn chứng minh tính ngun tố
dựa trên đường cong elliptic.
Chương trình trình bày về ngơn ngữ lập trình NetBeans và cách xây dựng chương
trình chứng minh tính ngun tố dựa trên đường cong. Đưa ra cài đặt thực nghiệm và kết
6


quả chương trình chứng minh tính ngun tố dựa trên đường cong elliptic.

7


CHƯƠNG 1: TỔNG QUAN VỀ MỘT SỐ THUẬT TOÁN KIỂM TRA
TÍNH NGUN TỐ CỦA SỐ NGUN.
1.1 Lịch sử, vai trị số nguyên tố sử dụng trong mật mã.
Số nguyên tố và việc đánh giá xem một số có là số nguyên tố hay không là một
vấn đề quan trọng trong mật mã hiện đại. Việc nghiên cứu các phương pháp kiểm tra tính
nguyên tố được nghiên cứu đầu tiên theo lý thuyết số là Eratos - thenes đầu tiên vào thế
kỷ 3rd BC. Hiệu quả tạo ra tập các số nguyên tố từ 1 tới N khoảng O (N log log N) các
bước theo phương pháp sàng Eratosthenes. Vào thế kỷ 17 việc nghiên cứu kiểm tra tính
nguyên tố thể hiện qua một số định lý của Fermat. Với sự cải tiến của mật mã, cụ thể mã
hóa dữ liệu trong mật mã khóa cơng khai. Khi đó, tính quan trọng của việc tìm các số
nguyên tố lớn là rất quan trọng. Sử dụng được các ý tưởng của định lý Fermat, vào năm
1977 Sollovay và Strassen và vào năm 1980 Miller và Rabin đã phát triển ý tưởng kiểm
tra tính ngun tố theo lý thuyết xác suất.
Sau đó, kiểm tra tính nguyên tố được thiết kế bởi Adleman, Pomerence và
Rumely, thuật tốn của họ đã có thời gian chạy được khá tốt. Thời gian chạy thuật toán
của họ được chứng minh là O((log N) c'log log log N) với c > 0. Thuật tốn có thời gian chạy
là đa thức với độ phức tạp đa thức được mong đợi. Cách tiếp cận phù hợp với sử dụng

trong thực tế. Nó được cải tiến bởi H.W.Lentra và Cohen, được cài đặt bởi Cohen và
A.K.Lenstra.
Vào năm 1985, H.W.Lentra đề xuất cách sử dụng các tính tốn đường cong
elliptic trong việc phân tích các số ngun. Sau đó Goldwasser và Kilian phát triển việc
kiểm tra tính ngun tố dựa vào nhóm các điểm hữu tỷ của đường cong elliptic trên
trường hữu hạn (thuật toán ECPP). Atkin và Morain đề xuất một ý tưởng tốt hơn cho
việc chứng minh tính nguyên tố dựa trên đường cong elliptic. Lý thuyết và thực tiễn cho
thấy rằng, thuật tốn chứng minh tính ngun tố dựa trên đường cong elliptic có hiệu quả
tốt hơn các phương pháp truyền thống.
1.1.1 Giới thiệu về số học
a) Ước chung lớn nhất và bội chung nhỏ nhất
Số nguyên d chia hết n nếu và chỉ nếu tồn tại số nguyên k sao cho n = kd . Khi
đó, d cịn gọi là ước của n. Ước d của n là ước đúng nếu d £ {-n,n,1,-1} . Bội N của n là
bội đúng nếu N £ {-n, n}.

1


Số ngun dương là ngun tố nếu nó khơng có ước đúng. Nghĩa là, nó khơng có
ước nào ngồi chính nó, đối của nó và ±1. Thơng thường ta chỉ quan tâm đến số nguyên
tố dương.
Mệnh đề 1. Số nguyên dương n là nguyên tố nếu và chỉ nếu nó không chia hết
cho bất kỳ số nguyên d nào thỏa mãn 1 < d <4n .
Hai số nguyên m, n là nguyên tố cùng nhau nếu các số nguyên duy nhất chia hết
cả m và n là ±1. Ta cũng nói rằng m nguyên tố với n nếu chúng nguyên tố cùng nhau.
Ký hi u Z

ệ

n


= {0,Ư..,n -1},Z*n = {k e Zn:(k,n) = 1},^(n) =1 Z I.

Mệnh đề 2.
z

Nếu a|b và b|c thì a|c.

z

Nếu d|x và d|y thì mọi số nguyên a, b ta có d|(ax+by).

Mệnh đề 3. Cho n và N là 2 số nguyên với n|N, Khi đó, với số nguyên x bất kỳ,
ta có

(xmodN)modn = xmodn .
Định lý 4: Cho m, n là các số nguyên khác 0. Trong tất cả các ước chung của m
và n, có một ước chung duy nhất d > 0 sao cho với mỗi ước chung e khác của m và n ta
có e|d.
Ước d này là ước chung lớn nhất của m, n; được ký hiệu là (m, n) hoặc gcd(m,
n).
Ước chung lớn nhất của 2 số nguyên m, n khác 0 là số nguyên dương nhỏ nhất
dạng xm+yn với x, y e Z.
Chú ý 5: Hai số nguyên tố cùng nhau nếu ước chung lớn nhất của chúng bằng 1.
Hệ quả 6. Cho m, n là các số nguyên khác 0. Trong tất cả các bội chung của m
và n, có duy nhất bội N > 0 sao cho mỗi bội chung M khác của m, n. Khi đó N|M. Bội N
này là bội chung nhỏ nhất của m, n (được ký hiệu là lcm(n,m)).
b) Sự phân tích duy nhất
Định lý 7 (sự phân tích duy nhất): Mỗi số nguyên N có thể được viết theo cách
duy nhất như tích các số nguyên tố N = ±pf ...pf, với các số mũ nguyên dương và các số

1

nguyên tố pỴ,...,pn khác nhau.

2


Hệ quả 8. Cho N là số nguyên dương đã được phân tích ra thừa số nguyên tố N

= ±Pỵ.-.Pe . Khi đó, hàm Ơle có dạng:
Ợ9(N)

= (P1 - 1)Pie ...(p„ - 1)pn
i_1

-1

Bổ đề 9: Cho p là số nguyên tố và giả sử rằng a và b là các số nguyên với p|(ab).
Khi đó hoặc p|a hoặc p|b hoặc cả hai.
Hệ quả của bổ đề 9. Nếu số nguyên tố p chia hết tích aa...an thì p chia hết ít nhất
một trong các nhân tử ai.
Các kết quả hoàn toàn đúng trên vành bất kỳ và vành Euclid.
Định nghĩa 10. Cho R là một miền nguyên, a,b G R, d là ước chung của a & b.
Khi đó d là ước chung lớn nhất (viết là gcd của a & b), nếu d’|d với tất cả ước chung d’
của a &b.
Bổ đề 11. Cho R là miền ideal chính, a, b G R và I = (a, b) là một ideal của R
được sinh bởi a và b. Nếu I = (d) với d G R thì d là gcd của a và b.
Định lý 12 (Thuật toán Euclid): Cho R là một vành euclid với hàm euclid ip,
a,b E R,b * 0,1 = (a, b).
Đặt r = a;r = b và Vi > 0,r = qpi+i + r+2 sao cho:

ri+2

= 0 hoặc iptPi+J <ự(ri+1').

Khi đó, 3 một số tự nhiên nhỏ nhất K với rK * 0 nhưng rK+ỉ = 0 và I = (rK)
Nghĩa là với a, b G R thì tìm được một gcd d của a, b. tức là tồn tại x,y G R sao
cho d =ax+by. Khi đó, việc tìm ước chung theo thuật toán ước chung mở rộng.
Định lý 13 (Định lý phần dư trung hoa): cho R là một vành euclid, t G N và

m,•••,m e R thỏa mãn gcd(pẠ,m}) = 1 với i * j . Khi đó:
t

/ nt)\ =

/m
i=1

1

Hệ quả 14. Cho vành Euclid R, t G N và mmt e R, gcd(m.,m.) = 1 với ỉ j. Hơn
thế, với a,...,at e R ta có:

3x e R với x = at mod(m ),1 < ỉ < t.

3


Nó được xác định duy nhất.
1.1.2 Các kết quả lý thuyết số học đại số
a) Định lý Fermat và các số ngun tố

Tìm hiểu về một số tính chất, kết quả về số nguyên tố, các số nguyên tố đặc biệt.
Khi vành R = Z thì tập số nguyên Z là vành Euclid. Tập các số nguyên tố dương gọi là
w.l.o.g. các số nguyên tố.
- Một số tính chất của số nguyên tố:
Định lý 1. (Euclid) Tồn tại tập vô hạn các số nguyên tố.
Chứng minh: Cho tập các số nguyên tố M 0 và 2 e M. Cho pp...,pk
là các số nguyên tố phân biệt và k

> 1. Cho Q = 1 + nPi, 3P là ước của Q.
i=0

k

Cho P = p P Q - n p

,

P1 mâu thuẫn với giả thiết p là nguyên
ỉ=0

tố Vi,1 < i < k.
Theo định lý trên, mỗi số n G N có một phân tích duy nhất thành tích các số
nguyên tố. Tức là, 3s G N và các số nguyên tố pp.. .,ps sao cho n = nPi.
ỉ=0

Khi đó:
5
n

=


n

p

ỉ

, i * j và pi?pj là nguyên tố cùng nhau với i j,e eN (Nó
p

p

ỉ=0

gọi là sự phân tích thành tích các nhân tử nguyên tố hợp chuẩn của n).
Định lý 2. (Định lý số nguyên tố): Cho 7ĩ(x) là số nguyên tố nhỏ hơn ‘x’ ở đây
x e R . Khi đó:

lim

x)

■

logx

x

x^V'


Chú ý.

4

=1


1. Một vài hệ mật giống như RSA cần các số nguyên tố lớn (như các số nguyên
tố với biểu diễn nhị phân là 128 bit) thì có bao nhiêu số nguyên tố như vậy tồn tại?
Bởi sử dụng định lý số nguyên tố, nó thể xấp xỉ

TT(2128)-TT(2127)

2— 2

=

-

128.log2

— (- 1906.10 số nguyên tố)

127.log2

2. Định lý này rất hữu ích trong việc phân tích thời gian chạy của thuật tốn chứng
minh tính nguyên tố.
đối với một số lẻ nguyên tố p , nó được xác định:

Kí hiệu Legendre:


+1 nếu t2 = x(mod p) có lời giải t A 0(mod p) —1 nếu t2 = x(mod p)
khơng có lời giải 0 nếu x = 0(mod p)
r

k

r

r

Kí hiệu Jacobi: Cho số nguyên lẻ N = npe với tất cả nguyên tố p và
i=0

a e Z . Khi đó:
z X c „ Ví

a

\e2

a

a

I N ) I P1 ) I P2 )

pk )

Bây giờ ta tìm hiểu về một số kết quả của đinh lý Fermat. Đây là cơ sở đầu tiên

cho việc chứng minh tính đúng đắn của thuật tốn chứng minh tính nguyên tố dựa trên
đường cong elliptic.
Định lý 3. (Định lý Fermat nhỏ): Cho số nguyên tố p và a G N với gcd(a,p) = 1.
Khi đó:
a 1 = 1mod(p).
p

Định nghĩa 4. Số N gọi là giả nguyên tố (ký hiệu psp (a)) nếu a 1 = 1mod N với
N-

a e Z ,1 < a < N -1.
Định nghĩa 5. Số N gọi là giả nguyên tố euler (ký hiệu epsp(a)) nếu
N -1

a2

mod( N) với a e Z,1 < a < N -1.
Mệnh đề 6. Với mọi số nguyên lẻ a e N, tồn tại vô hạn các số psp(a) và epsp(a).
Mệnh đề 7. Với số nguyên tố p (p -1 = 2l.m, với số nguyên lẻ m) và gcd(a,p)

5

=


1,a e Z. Khi đó:
am = 1 mod(p)
hoặc tồn tại j(0 < j < l) sao cho aa ' =-1 mod(p).
m


Định nghĩa 8. Với N là hợp số và các điều kiện ở trên được thỏa mãn với a e Z
thì N được gọi là một giả nguyên tố mạnh (ký hiệu spsp (a)).
- Các số nguyên tố đặc biệt:
Bổ đề 9. Với a, b e N và a| n thì 2a -1| 2n -1.
Hệ quả 10. Nếu Mn = 2n -1 là nguyên tố thì n là nguyên tố (các số nguyên tố như
vậy gọi là nguyên tố Mersenne).
Chứng minh: Theo bổ đề trên.
Số hoàn hảo là số nguyên dương bằng tổng của các ước nguyên dương của nó.
Bổ đề 11. Nếu M là nguyên tố thì n = 2p 1. Mp là một số hoàn hảo. Ngược lại mỗi
-

số hồn hảo chẵn n có dạng n = 2p 1. Mp ở đây Mp là số nguyên tố Mersenne
-

Bổ đề 12. Nếu N = 2m +1 là nguyên tố thì m = 2n. Các số Fn = 22 được gọi là số
nguyên tố Fermat.
b) Số học trong trường số toàn phương
Với D

e Z và 4D e C là một nghiệm của đa thức X2 - D. Khi đó, tập Q(\ỈD) :=

{a + WD | a, b e Q} o C. Khi Q(4D) là một trường thì được gọi là trường số tồn
phương. Nếu D<0 (D>0) thì nó được gọi là trường số phức (tương ứng trường thực).
Q(4D ) là không gian Q-vector 2 chiều, với cơ sở là P1=(1,O), P2=(0,«S/D ).

WLOG giả thiết rằng D là một số nguyên khơng có nhân tử chính phương, tức là D
0mod(4). Trong đồ án này, em lấy D = 1,2,3mod(4).
Định nghĩa 1. Ánh xạ ơ: Q(4D)

Q(4D);ơ(a + bpD) = a -b4D gọi là ánh


xạ liên hợp.
Một số tính chất của ánh xạ liên hợp ơ:
1.

ơ(a ± 33 = ơ(a) ± ơ(P), Va,3G Q(4D),
6


2.

ơ(a.p) = ơ(a).ơ(P),'~aJ)G Q(4D),

3.

ơ(a) = ơ(a),^a,3& Q(4D) với 3 * 0,
3 °3)

4. ơ 3) = 0 khi và chỉ khi 3

= 0.

Định lý 2. Cho D là số nguyên không có nhân tử chính phương. Khi đó, Q(4D) là
một trường số với Q Q(4D) c C. Mỗi a G Q(JD) có một biểu diễn duy nhất a = a + b\[D,

a, b G Q.
Ánh xạ ơ là một tự đồng cấu của Q(yỊD).
Định nghĩa 3. Với a' = ơ(a) hàm chuẩn (Norm): N(a) = a.a' và hàm vết (trace):

T (a) = a + a'

Do đó, nếu a = a + bJD thì N(a) = a2 - b2D và T(a) = 2a .
Định lý 4:
1.

Hàm S: Q(4D)

Q là một đồng luân (epimorphism) với nhóm

cộng.
2.

Nếu a

S *: Q(4D )*
Cho a

G Q(4D) thì N(a) = 0 khi và chỉ khi a = 0 (với D 0) hàm
Q * là một đồng cấu của nhóm nhân.

= a + bJD G Q(y/D), khi đó:
a — a + 2abyỊ~D + b D — 2a (a + b\Ị D) — a + b D S (a) N (a)

a2 — S (a).a + N (a) — 0
Hệ quả 5. Mỗi
Một đơn thức ụa

a E Q(4D) là một nghiệm của đa thức thuộc Q[x] với bậc < 2.

E Q[X] với bậc nhỏ nhất sao cho ỊẢa (a) — 0 được gọi là đa thức


tối thiểu của a . Hơn nữa, pa được xác định duy nhất.
Định nghĩa 6. Cho a

E Q(4D). Khi đó, a gọi là số nguyên đại số nếu ụa E z[x].

Ta có ba trường hợp cho đa thức tối thiểu của các số nguyên đại số như sau:

•

Cho aE Z

ụa — x — aE Z [ x],

7


E Q — Z /aa — x — ữĩ. Z[x],

•

Cho a

•

Cho aE Q(4D ) — Z, a là một số nguyên đại số
T(a) E Z và N(a) E Z .

Bổ đề 7. Cho a

E Q(4D ). Khi đó a là số nguyên đại số khi và chỉ khi a có dạng:


■^•(a + bjũ), a, b E Z, if: a = b mod(2), for: D = 1mod(4) 2
a + bJD,a,b E Z,if: D = 2,3mod(4)
Đặt OD là tập tất cả số nguyên đại số của Q(JD). Ta có kết quả sau:
Hệ quả 8. O là một vành. Hơn thế, O là một miền nguyên.
Cho tập V, tồn tại tập hữu hạn (Vị )1tử của V được biểu diễn dưới dạng tuyến tính của V với các hệ số tuyến tính, tập V như
vậy gọi là Z-modules.
Định lý 9. OD là một Z-modules tự do của hạng 2, OD có Z-Basis (1, CỠD) với

JD , if: D = 2,3mod(4) (1 + 4D), if: D =
1mod(4)
Hơn thế, OD

= Z © (Ở z .
D

Định nghĩa 10. Kết thức toàn phương ảo của trường số toàn phương ảo K

=

), d > 0 là một số ngun khơng có nhân tử chính phương và nó bằng
d, if: D = 3mod(4)
4d, if: D 3mod(4)

với D =

Hệ quả 11. Tập tất cả số nguyên đại số trong K đẳng cấu với

z + zự^d,if: d 3mod(4)

z+

1+

——, if: d = 3 mod(4)

Định nghĩa 12. (Order của trường số toàn phương ảo) Order O thuộc K là một
vành con của K với Z-Module hữu hạn sinh và hạng lớn nhất n = deg(K).
Định nghĩa 13. Một ideal a của O là một sub-O-module, tức là sub-Z- module
8


của O thỏa mãn mỗi r e O và i Ea thì ta có r.ỉ E a.
Định nghĩa 14. Một ideal a được gọi là một ideal chính của O nếu tồn tại x

eK

sao cho a = x.O. Hơn thế O là một miền ideal chính nếu O là một miền nguyên (với các
order của nó) và mọi ideal a của O là một ideal chính.
Định nghĩa 15. Hai ideal a,f gọi là tương đương nếu tồn tại a,b

E K * với a.a

= b.f .
Lớp tương đương từ một lớp ideal U. Mỗi lớp ideal của O có một ideal dạng:

-b -V^D
aZ H----- - --- z
2

Trong đó a

e B, b e z .Ngoài ra c = (b2 + D) / 4a E z,gcd(a, b, c) = 1

Định nghĩa 16. Một ideal thương i của O là một module con khác không của K
sao cho tồn tại một số nguyên khác không d với di là một ideal của O.

9


Định nghĩa 17. Cho i là một ideal thương của O. Khi đó, i là một nghịch ảnh nếu
tồn tại một ideal thương j của O sao cho:
O

= ỉj

Trong đó, ideal j gọi là nghịch ảnh của ideal i.
Bổ đề 18. Cho một ideal thương i và tập ỉ' - {x e K, xỉ c O}. Khi đó i là nghịch
ảnh của i ’ khi và chỉ khi:
ỉ * ỉ' - O
Do đó i' là nghịch ảnh duy nhất của i (ký hiệu là i-1).
c) Các dạng toàn phương
Trong mục này trình bày các dạng tồn phương trên trường số toàn phương ảo và
kết thúc. Một số kết quả về dạng tồn phương liên quan tới kiểm tra tính ngun tố của
một số nguyên. Lý thuyết nhân phức (Complex multiplication - CM) trên đường cong
elliptic được áp dụng vào thuật tốn ECPP.
Định nghĩa 1. Dạng tồn phương hai biến trên Z là ánh xạ:
f: Z2 Z, f (x,y) - ax2 + bxy + cz2,a,b,c e Z
Trong đó định thức D - ac - b2. Khi đó, dạng tồn phương này được gọi là nguyên
nếu gcd(ứ, b, c) -1. Do đó, dạng toàn phương này được biểu diễn là một cặp bộ ba f - (a,

b, c).
, khi đó order tồn phương của f được

Cho f (x, y) - (x, y)
Mf

biểu diễn dưới dạng các từ của ma trận M f.
Định nghĩa 2. Hai dạng toàn phương hai biến f & g được gọi là tương đương nếu

35 G SL(2, Z) (A là ma trận) với Mg - A 1.Mf.A .
Định nghĩa 3. Các dạng toàn phương hai biến f thuộc một nhóm các lớp tương
đương dạng [f] được gọi là nhóm lớp dạng (form class group - ký hiệu Cl (D)).
Hệ quả 4. Mỗi lớp tương đương chứa đúng một dạng (a, b, c) với a, b, c là nguyên
tố thỏa mãn điều: |b| < a < c & (|b\ — a or a — c b > 0). Dạng như thế này gọi là phần
dư.

10


Định lý 5. Cho OK là một order chính của trường số toàn phương ảo K và D là
một kết thức toàn phương ảo của OK. Định nghĩa ánh xạ:

2

2

,.

—h+—/D

ộ: f (x,y) — ax + bxy + c i->aZ --------- ------- Z
với D — b1 — 4ac.
Khi đó, ộ là một toàn ánh giữa Cl(D) và Cl(O).

Định lý này cho ta thấy: \CĨ(D)| — \Cl(OD)| và hơn thế h(OD) — h(D). Trong đó,
h(OD) và h(D) được đinh nghĩa bởi số các tọa độ trong tập Cl(OD) và Cl(D) tương ứng.
Định nghĩa 6. Cho D là một kết thức toàn phương ảo, n <= Z, dạng toàn phương
f — (a, b, c) với kết thức D. Nếu 3( x, w) e Z2 sao cho n — ax2 + bxw + w2 — f (x, w)
thì n được biểu diễn bởi hàm f. Khi đó, n gọi là chuẩn của một phần tử thuộc O D nếu tồn
tại 71G O với n — ~~ .
Như vậy, một câu hỏi đặt ra: Khi nào có dạng tồn phương như vậy và tính tốn
nó như thế nào? Để trả lời cho câu hỏi này, ta có:
Bổ đề 6. Cho D là một kết thức tồn phương ảo, n G Z, khi đó, tồn tại 7 e OD với
n — 771 khi và chỉ khi phương trình diaphontine 4n — t2 + D.y2 có một nghiệm (t, y) e
Z2 .
Đây là cơ sở của thuật tốn tìm nghiệm phương trình diaphontine. Tuy nhiên
khơng phải lúc nào ta cũng tìm được nghiệm của nó. Việc tìm nghiệm này chính là tìm
một cặp (t, y) thỏa mãn phương trình trên. Thuật tốn của Cornaicchia làm việc này để
trả lời xem nó có nghiệm hay khơng và đưa ra nghiệm trong trường hợp có nghiệm, cũng
được sử dụng để phân tích số ngun. Chú ý rằng tìm một cặp là tương đương để giải
phương trình p — x2 + d.ỹ2 với số nguyên tố p. Thuật toán cũng được sử dụng trong phép
nhân phức CM trên đường cong elliptic với kết thức D đã cho.
Thuật toán hiệu chỉnh của Cornaicchia
Đầu vào: Cho D là số ngun khơng có nhân tử chính phương và số nguyên tố p
sao cho D = 0 hoặc 1mod(4) và DI < 4p,
Đầu ra: Một nghiệm của phương trình 4 p = x2 + d .y2 nếu nó tồn tại,

11

1. (Trường hợp p = 2) Nếu D + 8 là bình phương của một số nguyên thì kết quả là
(V D

+ 8,1), ngược lại kết quả ‘Vô nghiệm’;
2. (Kiểm tra thặng dư) Sử dụng thuật tốn Jacobi tính k

. Nếu k = -1

kết quả ‘Vơ nghiệm’.
3. (Tính nghiệm bậc 2) Tính số nguyên X0 sao cho x2 = Dmodp và
0

< x0 < p.
(a) Gán x0

p - x0 nếu x0

D(mod 2)

(b) Gán a

2p, b

2y[p

x0, l

4. (Thuật toán Euclid) Nếu b > l thì r

a(mod b), a b,b r ; chuyển về

bước 3;
5. (Kiểm tra nghiệm) Nếu DI không chia hết 4p - b2 hoặc nếu c
khơng là bình phương của một số ngun thì kết quả là 'vơ
nghiệm'. Ngược lại kết quả là (x,y) = (b,vc).

1.2 Một số thuật toán kiểm tra tính ngun tố.
1.2.1 Thuật tốn kiểm tra tính nguyên tố theo xác suất
a) Thuật toán Euler-Salovay-Strassen
*) Tiêu chuẩn:
Nếu n là số nguyên tố thì với mọi số nguyên dương a < n:

— = a ! mod n
knJ

12

= (4p - b2)/ DI


Nếu n là hợp số thì
__ (n—1)/2 ___ J

*) Thuật toán Euler-Salovay-Strassen

„=

a ’ mod n >

Input: N là số nguyên lẻ;

Output: Trả lời N là số nguyên tố hoặc N là hợp số;
Bước 1: Lấy ngẫu nhiên a thuộc Z;
Bước 2: Tính d=gcd(a,N);
Nếu d >1 thì trả lời ‘N là hợp số’. Nếu d =1 đến bước B3
Bước 3: Tính b = a(N 1)/2modN và c =

faA

-- ;
lN)

Nếu b=c thì ‘N là số nguyên tố’
Ngược lại ‘N là hợp số’
Nhận xét: Nếu N là hợp số thì khơng q (N-1)/2 số thỏa mãn điều kiện nguyên
tố tại bước 3, nên có thể kết luận sai với xác suất khơng q 1/2. Để giảm xác suất sai
lầm này, ta thực hiện thuật toán với m số a được chọn ngẫu nhiên, độc lập với nhau. Khi
đó, xác suất để kết luận ‘N là số nguyên tố’ bị sai sẽ không vượt quá 1 / 2m.
b) Thuật toán Miller - Rabin
*) Tiêu chuẩn: Cho n là số nguyên lẻ, ta viết n -1 = 2eu, với u là số lẻ.
Nếu n là số nguyên tố thì mọi số nguyên dương a < n:
(au = 1mod n) V 3k | e(a2 u = -1modn)
Nếu n là hợp số thì :
ọk

a: 1 < a < n - 1,(au = 1modn) V Bk | e.(a u
*) Thuật toán:
Input: N = 2k .R +1 với R lẻ; Output: Tính

)n—1
1modn)\ < ——

1
4

nguyên tố của N Bước 1: Lấy ngẫu nhiên số a;
Bước 2: Tính d=gcd(a,N);
Nếu d >1 thì ‘N là hợp số’ và dừng thuật tốn;

13


Bước 3: Tính b = aR mod N.
Nếu b=1 thì ‘N là số nguyên tố’ và dừng thuật toán;
Bước 4: (Lặp vòng) Với i=0 đến k -1 thực hiện:
Nếu b=N-1 thì ‘N là số ngun tố’ và dừng thuật tốn;
Ngược lại, tính b = b2 mod N
Bước 5: Kết luận ‘N là hợp số’ và dừng thuật toán;
Với mỗi a xác suất chấp nhận nhầm N là số nguyên tố không quá 1/4. Nếu chọn
m số a độc lập với nhau và cả m lần đều kết luận ‘N là số ngun tố’ thì sác suất phạm
sai lầm khơng q 1/ 4m.
1.2.2 Thuật tốn kiểm tra tính ngun tố tất định
Việc kiểm tra một số là số nguyên tố hay không thông qua phương thức chia thử.
Phương thức này được mơ tả thơng qua bài tốn sau:
Bài tốn: Nếu một số đã cho N £ N không chia hết cho một số nguyên tố bất kỳ
(Ví dụ: nếu N = a.b thì 1 < a < b < N

a2 < a.b = N p2 < N với các số

nguyên tố p | a).
Độ phức tạp thuật toán này là O(4N). Ta sử dụng phương thức này để phân tích

số nguyên cần kiểm tra thành các nhân tử nhỏ hay khơng. Nó được sử dụng tại bước đầu
tiên của thuật toán Atkin để hạn chế việc tính tốn, kết thúc ngay khi chứng minh được
tính nguyên tố. Việc kiểm tra được lưu trữ theo sàng Eratosthenes với các số nguyên tố
trong một danh sách đối chiếu kiểm tra nó có là ngun tố hay khơng một cách đơn giản.
a) Thuật toán sàng Eratosthenes
Input: Số N cần kiểm tra;
Output: Trả lời N là số nguyên tố hay N là hợp số;
Bước 1: Cho một số N; a=2;
Bước 2: N = q.a + r;
Bước 3: Kiểm tra: Nếu r = 0 N là hợp số
Nếu r # 0 thì kiểm tra:

14


Nếu a >4N thì dừng: N là số nguyên tố;
Nếu a b) Thuật toán AKS
AKS (Agrawal-Kayal-Saxena) là tên ba nhà toán học Ân Độ vào năm 2002 đã
đưa ra được lời giải cho định lý nổi tiếng về bài tốn kiểm tra tính nguyên tố của một số
nguyên, có độ phức tạp thuộc lớp bài tốn lớp P. Nghĩa là có thể giải được trong thời
gian đa thức. Cơng trình này được mang tên của giáo sư Manindra Agrawal và hai học
trò của ông là Neeraj Kayal, Nitin Saxena.
Thuật toán :
Input : số nguyên n >1.
Bước 1: if (n = ab với a

và b>1), output : Hợp số.

Bước 2: Tìm số r nhỏ nhất sao cho Ord.(n) > 4log2 n

Bước 3: if 1 < (a,n) < n với a < r nào đó, output: Hợp số.
Bước 4: if n < r, output: N nguyên tố
Bước 5: for a=1 to

2ự0(r) log n

if ỰX + a)n

do

Xn + a(modXr -1,n, output: Hợp số;

Output: nguyên tố.
Bảo đảm cho thuật toán này chạy trong thời gian đa thức là các định lý sau: Định
lý: Thuật toán trên trả lời nguyên tố khi và chỉ khi n là số nguyên tố. Định lý: Tồn
tại số r

<1 16log n I sao cho Ord (n) > 4log2 n .
5

r

Định lý: Độ phức tạp thời gian tiệm cận của thuật toán này là O(log10.5 n).
1.2.3 Thuật toán kiểm tra dựa trên sự phân rã N-1 (tương ứng N+1)
a) Định lý Pockington

15


Định lý (Lucas): Cho a, N GN với gcd(a,N) =1. Nếu aN 1 = 1mod(N), nhưng a d í

1mod(N) với mỗi ước d >1 của N-1 thì N là nguyên tố.

Định lý Pockington: Cho s là ước dương của N-1, s > 4N. Giả sử có một tố.
số a thỏa mãn:

aN 1 = 1mod N

với ước nguyên tố q của s. Khi đó N là nguyên

(a{N 1)/q -1, N) = 1
-

Định lý: Cho N=FR+1, trong đó đã biết phân tích của F và F >

Ị.Ạ

[ aN 1 = 1modN ,
với ước nguyên tố q của F tôn tại số a sao cho <
,

-

3N . Nếu ..

Ặ

,
\(a(N 1)/■ -1, N) = 1

và giả sử

-

N = AF + BF +1 với 0 < A, B < F thì:
2

a. Nếu A = 0 thì N là số nguyên tố
b. Nếu A > 0 và B2 - 4A là số khơng chính phương thì N là số ngun tố.
b) Thuật tốn kiểm tra tính nguyên tố dựa trên sự phân rã N-1
Định lý Pockington chính là cơ sở tốn học cho thuật tốn kiểm tra tính nguyên
tố theo N - 1 (tương ứng với N + 1) và thể hiện qua một số định lý sau:
Định lý: Cho Ne N, N -1 =

nt

=(

pe . Nếu tôn tại a e N sao cho :

aN 1 = 1 mod N
-

*

N-1

a Pi Tệ. 1 mod N
Khi đó, N là số nguyên tố.
Định lý: Cho NeN, N -1 =

n t pe , 1 < i < t. Nếu tơn tại ai sao cho:
=

a 1 = 1mod( N)
N

aA

1mod(N)

Khi đó, N là nguyên tố.
Phân tích đầy đủ và thỏa mãn một số phép chia của N-1 như vậy là thỏa mãn tính
chất kiểm tra tính nguyên tố theo số nguyên tố ứng cử viên (candidate) N.

16


Thuật tốn: Kiểm tra N - 1 (Sự phân tích đủ N - 1)
Input: Cho N e N, N lẻ, cơ số ai (0 < i < r) (định lý trên) điều này được kiểm tra
theo Miler-Rabbin
Output: ‘N là nguyên tố’ hày ‘N là hợp số’.
Bước 1: Khởi tạo i = 0 (cơ sở đầu tiên mo);
Bước 2: Xác định s, t sao cho N -1 = m2 t;
Bước3: (Lặp vòng) While i < k do:
If m\ = 1mod(N) , then i i +1,
While k < s do:
Nếu m2 t = - 1mod(N) thì i i +1 và dừng thuật tốn, k

k +1,

If k = s thì trả lời ‘N hợp số’.
Bước 4: Kết quả trả lại ‘N nguyên tố’.
Ngoài ra ta có thể kiểm tra các điều kiện của Pocklington theo thuật toán
sau:
Thuật toán: Kiểm tra N -1 (phân tích khơng đầy đủ N -1)

n "0 Pĩ

Input: Cho N e N, N lẻ, P là ước nguyên tố của N - 1 và là
Q
=
ước của N - 1 cới các nhân tử nguyên tố pi sao cho N -1 = Q.P và Q
< P.
Output: Kết quả ‘N là nguyên tố’ hay ‘N là hợp số’.
Bước 1. Chọn một số tự nhiên a e N sao cho 1 < a < N,
Bước 2. Nếu aN 1 ± 1mod( N) thì chuyển về B1,
Bước 3. Nếu gcd(aQ -1, N)

1 thì chuyển về B1,

Bước 4. Trả lại ‘N là nguyên tố’.
c) Các số nguyên tố đặc biệt
Dạng đơn giản nhất của số nguyên tố là N

17

— 1 = 2m .


xn + 1 1 .

, n-1
—
1
+
x
+
...
+ , thay x bởi -x, ta có:
x -1
x

Cho số nguyên lẻ n e N. Ta có

(-x)n +1
— 1 - x + ... + (-x)n 1
- x -1
-

xn +1
— 1 - x + ... + xn 1
x -1
x +1| xn +1, (n = 1 mod 2)
-

Cho m

— bu với u lẻ, ta có :
2b + 1|2bu +1 — N.

x:— 2b

Từ định lý trên, nếu a e Z với aFn 1 = 1mod(Fn ) và a(Fn 1)/2

1mod(F )

thì Fn là nguyên tố với Fn — 22 +1 .
Định lý (Peppin): Fn là nguyên tố khi và chỉ khi:

32 = - 1mod (F )
với n > 1.
Định lý: Cho n > 2, p | Fn và p là nguyên tố. Khi đó:

p = -1 mod (2n

+2

).

Từ định lý Poclington, ta có các kết quả phía sau:
Định lý: Cho N — K,2n +1,2\ K, 0 < K < 2n + 2. Khi đó, N là nguyên tố khi và chỉ
khi:

3a e Z: a 2 =-1mod(N).
Định lý: Cho N — K.2n

+1, n > 2 và K là lẻ và 3\ K, với 0 < K < 2n + 2 . Khi đó

N là nguyên tố khi và chỉ khi:
N-1

3
d)

2

=-

1mod (N)

Thuật tốn chứng minh tính ngun tố theo N+1.

18