CHƯƠng 1 CƠ BẢn về ĐẠi số trừu tưỢNG

3. 
   Trường hữu hạn, xây dựng trên đa thức cơ sở
   

Nếu như , thì rõ ràng thuộc trường . Dẫn đến điều kiện , tương đương với . Giả sử là hệ số bậc cao của f(x). Khi đó và . Điều này là không thể, bởi vì đa thức có bậc là n, trong khi đó bậc của r(x) nhỏ hơn n. Dẫn đến đa thức r(x) là đa thức không. Điều này là vô lý này dẫn đến kết luận của định lý.

Cho F là trường hữu hạn, là đa thức bất khả quy bậc n trên trường F. Khi đó α là nghiệm của phương trình = 0, và các thành phần 1, α, α²,…, α^n-1 gọi là đa thức cơ sở của không gian hữu hạn trên trường F.

Trong đại số tuyến tính, một đa thức cơ sở gồm n phần tử sẽ sinh ra không gian vector n chiều. Để biểu diễn ý này, sử dụng tích vô hướng các độ lớn thuộc về trường F, tức là không gian vector n chiều, sinh bởi đa thức cơ sở 1, α, α²,…, α^n-1 có cấu trúc sau:

.

Định lý 1.3.6: Cho F là trường hữu hạn, là đa thức bất khả quy bậc n trên trường F. Không gian vector (định nghĩa 1.3.10) đối với bất kỳ nghiệm nào của phương trình = 0 đều là trường hữu hạn và có số phần tử là (#F)ⁿ.

Chứng minh: Đầu tiên sẽ chứng minh rằng không gian vector (định nghĩa 1.3.10) là một vành. Để làm điều này, chú ý rằng phương trình:

.

Với , có thể viết lại dưới dạng sau

Nhờ vậy mà là tổ hợp tuyên tính của đa thức cơ sở . Nhân hai vế của f() cho , dễ dàng chứng tỏ rằng với bất kỳ một số nguyên dương , phần tử có thể biểu diễn dưới dạng tổ hợp tuyến tính của chính đa thức cơ sở của nó. Điều này dẫn đến, bất kỳ phần tử u, v từ không gian (định nghĩa 1.3.10) tích uv là tổ hợp tuyến tính từ cơ sở của các phần tử , với , nó phải là tố hợp tuyến tính của cơ sở các phần tử , có nghĩa là thuộc về không gian (định nghĩa 1.3.10). Cho nên tiên đề về “đóng” thỏa mãn.

Thứ hai, để chứng minh rằng không gian (định nghĩa 1.3.10) là một trường, cần phải chứng minh rằng nó không chứa phần tử không. Để chứng mình điều này, ứng dụng điều kiện độc lập tuyến tính của (định lý 1.3.5) và từ điều kiện dẫn đến đẳng thức không của một trong hai u và v.

Và cuối cùng chú ý rằng, trong sự triển khai các phần tử của không gian theo đa thức cơ sở, sử dụng phần tử của trường F, và bản thân đa thức cơ sở chứa n phần tử. Nên không gian (định nghĩa 1.3.10) chứa phần tử.

Cho q là số lượng phần tử của trường hữu hạn F. Ký hiệu cho trường hữu hạn, được xây dựng trên cơ sở gồm n phần tử trên trường F.

Ví dụ 1.3.5 (Trường )

Thấy rằng / x⁸ + x⁴ + x³ + x + 1 là một trường bao gồm 2⁸ phần tử. Biết rằng cũng là một trường bao gồm 2⁸ phần tử và có thể biểu diễn dưới dạng không gian vector

ở đây α là nghiệm của phương trình x⁸ + x⁴ + x³ + x + 1 = 0, các hệ số b₇, b₆, b₅, b₄, b₃, b₂, b₁, b₀ .

Nhận thấy việc tính toán trong trường đơn giản hơn trong trường / x⁸ + x⁴ + x³ + x + 1 nhờ trực tiếp nhân hai thành phần và biểu diễn dưới dạng tổ hợp tuyến tính các thành phần 1, α, α²,…, α^n-1.

Ví dụ cần tính ‘57’.’83’. Chú ý: ‘57’ = (0101_0111), còn ‘83’ = (1000_0011).

(α⁶ + α⁴ + α² + α + 1).(α⁷ + α + 1) = α¹³ + α¹¹ + α⁹ + α⁸ + α⁶ + α⁵ + α⁴ + α³ + 1

Bởi vì α⁸ + α⁴ + α³ + α + 1 = 0 nên nhận được các tổ hợp tuyến tính sau:

cho nên α¹³ + α¹¹ + α⁹ + α⁸ + α⁶ + α⁵ + α⁴ + α³ + 1= α⁷ + α⁶ + 1. Và có nghĩa là ‘57’.’83’=’C1’. Nếu như dùng / x⁸+x⁴+x³+x+1, thì cần phải thực hiện phép chia và sẽ phức tạp hơn.

1. 
   Trường F là trường con của trường
   
2. 
   Bất kỳ thành phần thỏa mãn điều kiện khi và chỉ khi
   

Chứng minh khẳng định thứ nhất:

Cho 1, α, α²,…, α^n-1 là đa thức cơ sở của trường trên trường F. Bởi vì đa thức cơ sở này bao gồm phần tử đơn vị, bất kỳ phần tử nào của trường F đều có thể biểu diễn dưới dạng tổ hợp tuyến tính của phần tử đơn vị, có nghĩa là dưới dạng tổ hợp tuyến tính của phần tử cơ sở.

Chứng minh khẳng định thứ hai:

Đặt , ở đây là nhóm nhân với các phần tử khác không. Như vậy điều kiện có thể là 0 hoặc có thể là thuộc . Với khả năng đầu tiên thì điều kiện là hiển nhiên đúng. Đối với khả năng thứ hai, nhóm sinh bởi phần tử sinh a, rõ ràng nhóm này là nhóm con của , thì theo định lý Lagrange có (a)|#= q – 1, và có . Nhờ vậy mà.

Chứng minh điều ngược lại: Bất kỳ phần tử a thuộc , thỏa mãn điều kiện phải là nghiệm của phương trình . Thấy rằng bậc của đa thức bằng q nên phương trình trên trong trường không thể có số nghiệm lớn hơn q kể cả 0. Từ phần 1 của định lý, trường là trường con của , mà các nghiệm của phương trình thuộc về F. Nên không một nghiệm của đa thức không là phần tử của .

4. 
   XÂY DỰNG NHÓM TRÊN CƠ SỞ ĐƯỜNG CONG ELLIPTIC
   

1. 
   Công thức Weierstrasse và đường cong elliptic
   

ở đây a, b, c, d, e là các số thỏa mãn một vài điều kiện đơn giản nào đó và thuộc K.

2. 
   Đường cong elliptic trên trường hữu hạn
   

Tùy thuộc vào trường hữu hạn F_q, với mỗi bậc của q, tồn tại nhiều đường cong elliptic. Do đó, với một trường hữu hạn cố định có q phần tử và q lớn, có nhiều sự lựa chọn nhóm đường cong elliptic.

3. 
   Đường cong elliptic trên trường F_p (p là số nguyên tố)
   

Cho p là số nguyên tố (p > 3), cho a, b  F_p sao cho 4a³ + 27b² ≠ 0 trong trường F_p. Một đường cong elliptic E(F_p) trên F_p (được định nghĩa bởi các tham số a và b) là một tập hợp các cặp giá trị (x, y) (x, y  F_p) thỏa mãn công thức:

cùng với điểm O đặc biệt gọi là điểm vô cực và có thể biểu diễn dưới dạng O = (x, ).

Số lượng điểm của E(F_p) là #E(F_p) thỏa mãn định lý Hasse.

Chú ý: Độ phức tạp của thuật toán xây dựng trên nhóm đường cong Elliptic phụ thuộc vào số điểm trên đường cong đó, và xét định lý Hasse về số điểm trên đường cong Elliptic.

Định lý 1.4.1 (Định lý Hasse): Số các điểm trên đương cong Elliptic thỏa mãn bất đẳng thức sau:

.

Định nghĩa 1.4.2 (Bậc của điểm)

Cho điểm P(x, y) thuộc đường cong elliptic. Bậc n của điểm P(x, y) là số nguyên dương thỏa mãn biểu thức:

Tập hợp các điểm trên E(F_p) tạo thành một nhóm thỏa mãn các tính chất sau:

• 
  Tính đóng: a, b  G, a + b  G.
  
• 
  Tính kết hợp: Các phép toán trong nhóm có tính kết hợp.
  

• 
  Phần tử đơn vị: có một giá trị 0  G sao cho a + 0 = 0 + a = a, a  G.
  
• 
  Phần tử nghịch đảo: a  G, –a  G gọi là số nghich đảo của a, sao cho
  

1. Cho phương trình mod 7. Nhận thấy (4.6³ + 27.4²) mod 7 = 1 ≠ 0, nó phù hợp với điều kiện của các nhóm elliptic theo mudulo 7. Đường cong này có các điểm sau:

Ta thấy (3, 0) + (3, 0) = O. Phần tử sinh của nhóm G = (1, 2). Nhóm các điểm trên đường cong elliptic là nhóm cyclic.

2. Giả sử p = 23, khảo sát đ­ường cong elliptic y² = x³ + x + 1. Trong tr­ường hợp này a = b = 1 và có 4  1³ +27  1 (mod 23) = 8  0, nó phù hợp với điều kiện của các nhóm elliptic theo mudulo 23.

Trên hình 2 biểu diễn đ­ường cong liên tục, các điểm sẽ cho giá trị phù hợp với ph­ương trình đã cho. Đối với các nhóm điểm trên elliptic chỉ khảo sát các giá trị nguyên từ (0, 0) đến (p, p) trong góc phần tư của các số không âm (góc thứ nhất), phù hợp với ph­ương trình theo modulo p.

Trong bảng dưới, trình bày các điểm (khác với O) là các phần tử của tr­ường E₂₃(1, 1).

(0, 1)	(6, 4)	(12, 19)
(0, 22)	(6, 19)	(13, 7)
(1, 7)	(7, 11)	(13, 16)
(1, 16)	(7, 12)	(17, 3)
(3, 10)	(9, 7)	(17, 20)
(3, 13)	(9, 16)	(18, 3)
(4, 0)	(11, 3)	(18, 20)
(5, 4)	(11, 20)	(19, 5)
(5, 19)	(12, 4)	(19, 18)

4.2.2 Đường cong elliptic trên trường

Định nghĩa 1.4.3 (Đường cong elliptic trên trường )

Một đường cong elliptic E() trên được định nghĩa bởi các tham số a, b  (với b ≠ 0) là tập các điểm P(x, y) với x  , y  thỏa mãn công thức:

cùng với điểm O là điểm tại vô cực. Số lượng các điểm thuộc E( m F2 ) ký hiệu #E( m F2 ) thoả mãn định lý Hasse:

trong đó p = 2^m. Ngoài ra, #E() là số chẵn.

• 
  O + O = O.
  
• 
  (x, y) + O = (x, y), (x, y)  E( )
  
• 
  (x, y) + (x, - y) = O, (x, y)  E(). Khi đó, (x,- y) là điểm đối của (x, y) trên E().