Số học và Lý thuyết số
Đường cong elliptic
Các đường cong bậc ba trơn có các điểm tạo thành một nhóm abel theo luật dây cung-tiếp tuyến hình học, liên kết hình học Diophantus cổ điển với dạng modular, mật mã đường cong elliptic, và giả thuyết Birch và Swinnerton-Dyer còn mở.
Trực giácĐường cong biến các điểm thành một nhóm
Xét một đường cong bậc ba trơn — một hình dạng trông như một đường cong chữ S lười biếng, hoặc (tùy theo ) một nhánh lượn sóng đơn cộng thêm một vòng oval tách biệt. Chọn hai điểm bất kỳ và trên đường cong. Một sự thật đáng chú ý của đại số đảm bảo rằng đường thẳng qua và luôn cắt đường cong tại đúng thêm một điểm nữa (tính cả bội), vì thay phương trình đường thẳng vào đa thức bậc ba sẽ để lại một đa thức bậc , và hai trong ba nghiệm của nó đã bị chốt sẵn bởi và . Gọi điểm thứ ba đó là . Bây giờ phản chiếu qua trục : ảnh gương được định nghĩa là tổng . Công thức thuần túy hình học này — kẻ một dây cung, tìm điểm thứ ba, lật nó qua trục — biến các điểm trên đường cong thành một nhóm giao hoán, với điểm tại vô cực (nơi mọi đường thẳng đứng cắt đường cong) đóng vai trò phần tử đơn vị .
Ví dụ: Cộng hai điểm hữu tỉ bằng tay
Trên đường cong , hãy kiểm tra rằng và đều là các điểm hữu tỉ, rồi dùng cách dựng dây cung để tính .
Lời giải
Trước hết, và , nên cả hai điểm đều nằm trên (đây là đường cong số đồng dư , liên hệ với tam giác vuông -- có diện tích ). Dây cung qua và có hệ số góc . Điểm giao thứ ba có tọa độ là và tọa độ là . Vậy đường thẳng cắt lần nữa tại — và vì điểm này đã nằm trên trục rồi, ảnh phản chiếu của chính nó là chính nó, cho ta . Để kiểm tra lại, , xác nhận .
Đại họcDạng Weierstrass, biệt thức và tính không suy biến
Định nghĩa: Đường cong elliptic (dạng Weierstrass rút gọn)
Trên một trường có đặc số (chẳng hạn , , hay một trường hữu hạn với ), mọi đường cong bậc ba phẳng trơn có một điểm hữu tỉ đều có thể đưa về dạng Weierstrass rút gọn với các hằng số nào đó trong trường. Một đường cong elliptic là một đường cong như vậy cùng với điểm bổ sung tại vô cực , và bắt buộc phải không suy biến: không điểm nào của đường cong được có cả hai đạo hàm riêng của triệt tiêu đồng thời (một điểm suy biến sẽ là một nút tự cắt hoặc một mũi nhọn, nơi công thức dây cung-tiếp tuyến bị hỏng).
Đường cong không suy biến khi và chỉ khi biệt thức khác không, điều này xảy ra khi và chỉ khi đa thức bậc ba có ba nghiệm phân biệt (trên một bao đóng đại số).
Vì sao đúng?
Một điểm nơi đa thức bậc ba có nghiệm bội chính là nơi đường cong bị thắt lại thành mũi nhọn hoặc tự cắt chính nó, vì hướng tiếp tuyến ở đó trở nên không xác định — đúng là khiếm khuyết hình học sẽ phá vỡ luật nhóm dây cung-tiếp tuyến.
Chứng minh
Điểm là điểm suy biến khi và chỉ khi đồng thời , , và . Phương trình thứ hai buộc , nên phải là nghiệm của ; phương trình thứ ba buộc , tức cũng là nghiệm của đạo hàm . Một đa thức và đạo hàm của nó có chung nghiệm chính xác tại một nghiệm bội của đa thức đó, nên suy biến khi và chỉ khi có nghiệm bội. Biệt thức cổ điển của đa thức bậc ba khuyết là , triệt tiêu đúng khi đa thức bậc ba có nghiệm bội; nhân với hằng số chuẩn hóa cho , vậy không suy biến khi và chỉ khi .
Công thức hình học dây cung-tiếp tuyến chuyển thành đại số tường minh. Với hai điểm phân biệt , mà , dây cung có hệ số góc ; khi nhân đôi một điểm với , tiếp tuyến tại có hệ số góc (tìm được bằng đạo hàm ẩn của ). Trong cả hai trường hợp, tọa độ của tổng được cho bởi cùng hai công thức dưới đây. Nếu cộng với , đường thẳng đứng qua chúng chỉ cắt tại , nên , khớp với tiên đề phần tử đơn vị của một nhóm.
Vì có đặc số với , các công thức cộng và nhân đôi y hệt vẫn áp dụng khi được rút gọn theo modulo một số nguyên tố , cho đường cong rút gọn cấu trúc của một nhóm abel hữu hạn. Đây chính là bối cảnh được dùng xuyên suốt trong mật mã đường cong elliptic, và nó đặt ra một câu hỏi hiển nhiên: lớn cỡ nào?
Với một đường cong elliptic trên trường hữu hạn ( nguyên tố), số điểm thỏa mãn .
Vì sao đúng?
Đại lượng đo 'số hạng sai số' so với phỏng đoán ngây thơ rằng một đa thức bậc ba ngẫu nhiên nên có khoảng nghiệm cộng thêm điểm tại vô cực; chặn Hasse nói rằng sai số này không bao giờ vượt quá khoảng , một độ lệch nhỏ đến kinh ngạc so với chặn tầm thường cỡ , và chính điều này khiến trở thành một bậc nhóm đáng tin cậy, dự đoán được, dùng trong các cấu trúc mật mã.
Chứng minh
Xét tự đồng cấu Frobenius , . Các điểm bất động của nó chính xác là , và ta chứng minh được với là vết của Frobenius tác động lên vành tự đồng cấu. Ánh xạ bậc trên các tự đồng cấu của là một dạng toàn phương nguyên xác định dương (thỏa mãn với mọi số nguyên , đẳng thức chỉ xảy ra khi ), và . Khai triển như một dạng toàn phương theo buộc biệt thức của nó không dương: , tức . Vì , đây chính xác là chặn đã nêu.
Ví dụ: Đếm điểm trên một đường cong trên trường hữu hạn nhỏ
Cho trên . Hãy tính bằng cách liệt kê trực tiếp và kiểm tra nó thỏa mãn chặn Hasse.
Lời giải
Với mỗi , tính và kiểm tra xem nó có phải là số chính phương mod không (các số chính phương mod là , vì ): (chính phương, , điểm); (không chính phương, điểm); (chính phương, , điểm); (chính phương, , điểm); (chính phương, , điểm). Điều này cho điểm hữu hạn, cộng thêm điểm tại vô cực, nên . Kiểm tra chặn Hasse: , và , nên đúng.
Nâng caoHạng, xoắn và hình dạng của
Trên , nhóm là vô hạn bất cứ khi nào nó chứa một điểm có bậc vô hạn, và bài báo năm 1901 của Henri Poincaré lần đầu đặt câu hỏi cần bao nhiêu điểm hữu tỉ để sinh ra mọi điểm khác bằng dây cung và tiếp tuyến. Louis Mordell đã trả lời câu hỏi này năm 1922 bằng cách tinh chỉnh phương pháp giáng vô hạn của Fermat, và André Weil đã tổng quát hóa kết quả này trong luận án năm 1929 của ông sang các đa tạp abel trên các trường số bất kỳ.
Với một đường cong elliptic trên , nhóm các điểm hữu tỉ được sinh hữu hạn: với một số nguyên nào đó gọi là hạng, trong đó là một nhóm abel hữu hạn.
Vì sao đúng?
Định lý này là thành quả số học của luật nhóm: nó nói rằng dù tập các điểm hữu tỉ trông phức tạp đến đâu, nó luôn được kiểm soát bởi hữu hạn các điểm 'hạt giống' — một tập sinh hữu hạn — mà từ đó mọi điểm hữu tỉ khác đều đạt được bằng phép cộng dây cung-tiếp tuyến lặp lại.
Chứng minh
Chứng minh kết hợp hai thành phần. Mordell–Weil yếu: ta chứng minh là một nhóm hữu hạn, bằng cách nhúng nó (qua đối đồng điều Galois, dùng ánh xạ giáng bậc là với các nghiệm của đa thức bậc ba) vào một nhóm dựng từ nhóm lớp và nhóm đơn vị của một trường số liên quan, cả hai đều được biết là hữu hạn. Giáng theo độ cao: ta gắn cho mỗi điểm một độ cao chính tắc , một đại lượng thực đo độ phức tạp số học thỏa mãn và chỉ hữu hạn điểm có độ cao dưới một chặn cho trước. Kết hợp một tập hữu hạn đại diện lớp ghép của với việc lặp lại giảm một nửa độ cao của bất kỳ điểm nào (qua luật hình bình hành cho độ cao) cuối cùng rơi vào vùng độ cao bị chặn cho thấy mọi điểm đều là một tổ hợp của hữu hạn đại diện và hữu hạn điểm có độ cao bị chặn — vậy được sinh hữu hạn.
Với một đường cong elliptic trên , nhóm con xoắn đẳng cấu với đúng một trong nhóm sau: nhóm cyclic với hoặc , hoặc nhóm với ; không nhóm abel hữu hạn nào khác xảy ra.
Vì sao đúng?
Đây là một phát biểu cứng nhắc đáng kinh ngạc: trong vô số nhóm abel hữu hạn khả dĩ về mặt trừu tượng, chỉ đúng nhóm này từng xuất hiện làm phần xoắn của một đường cong elliptic hữu tỉ — một nhóm con xoắn có cấp, chẳng hạn, hay đơn giản là không thể xảy ra.
Chứng minh
Chứng minh năm 1977 của Mazur chuyển việc tồn tại một điểm hữu tỉ có bậc đúng trên thành việc tồn tại một điểm hữu tỉ không phải điểm chóp trên đường cong modular , phân loại các cặp với có bậc . Chiến lược này khảo sát Jacobian của đường cong modular liên quan và iđêan Eisenstein — iđêan trong đại số Hecke sinh bởi với các số nguyên tố — tác động lên nó. Bằng cách phân tích thương Eisenstein của và phép rút gọn của nó theo modulo các số nguyên tố phụ trợ, Mazur chứng minh rằng với nằm ngoài danh sách cho phép, chỉ gồm các điểm chóp, nên không đường cong elliptic nào trên có thể có điểm hữu tỉ với bậc đúng đó; các cấu trúc tường minh (chẳng hạn dùng các đường cong và ) minh họa các ví dụ hiện thực hóa mỗi nhóm trong nhóm được phép.
Định nghĩa: Bất biến
Với , **bất biến ** là . Hai đường cong elliptic trên một trường đóng đại số đẳng cấu với nhau khi và chỉ khi chúng có cùng bất biến , nên là bất biến phân loại đầy đủ cho hình dạng của đường cong, không phụ thuộc phương trình Weierstrass nào được dùng để biểu diễn nó (các đường cong có chung bất biến trên nhưng không đẳng cấu trên được gọi là các xoắn (twist) của nhau).
Vì phép tính số học trong nhanh khi tính xuôi nhưng (với các đường cong được chọn tốt) cực kỳ chậm khi tính ngược, các đường cong elliptic là nền tảng cho phần lớn mật mã khóa công khai ngày nay. Cố định một điểm gốc công khai ; việc tính (cộng với chính nó lần, thực hiện hiệu quả bằng cách nhân đôi lặp lại) là dễ, nhưng khôi phục số nguyên bí mật chỉ từ và — Bài toán logarit rời rạc trên đường cong elliptic (ECDLP) — được tin là cần khoảng phép tính đối với các thuật toán cổ điển tốt nhất đã biết, và không có phương pháp nhanh hơn nào được biết đến. Điều này cho phép các giao thức như ECDSA và ECDH dùng khóa ngắn hơn nhiều so với RSA cùng mức độ an toàn.
Ví dụ: Một phép tính logarit rời rạc mẫu
Trên trên , hãy kiểm tra rằng nằm trên , rồi tính bằng công thức nhân đôi, minh họa (ở quy mô mẫu) phép tính số học đằng sau Bài toán logarit rời rạc trên đường cong elliptic.
Lời giải
Trước hết, , và , nên . Để nhân đôi , hệ số góc tiếp tuyến là ; vì , nghịch đảo của theo modulo là , nên . Sau đó , và , nên . Kiểm tra lại: , và ✓. Trên đường cong mẫu này chỉ có giá trị khả dĩ, kẻ tấn công có thể tìm mọi bội số của bằng tay; ECC thực tế dùng số nguyên tố khoảng bit, khiến phép tìm kiếm tương tự ( bước) trở nên hoàn toàn bất khả thi.
Nâng caoCầu nối tới dạng modular và Định lý lớn Fermat
Các đường cong elliptic cũng sống trong một thế giới thứ hai: thế giới của dạng modular, các hàm chỉnh hình có tính đối xứng cao trên nửa mặt phẳng trên. Gắn cho hàm Hasse–Weil của nó (dựng từ cùng xuất hiện trong chặn Hasse), Định lý Modularity (giả thuyết Taniyama–Shimura–Weil) khẳng định rằng luôn trùng với hàm của một dạng modular trọng số . Tương đương, được phủ bởi một đường cong modular qua một ánh xạ không hằng xác định trên , trong đó là dẫn (conductor) của . Điều này liên kết dữ liệu số học thuần túy với mọi số nguyên tố với các hệ số Fourier của một hàm duy nhất, có cấu trúc cao — một cầu nối phi thường giữa hai lĩnh vực toán học thoạt nhìn không liên quan. Biểu diễn Galois liên kết trên môđun Tate -adic của (một cấu trúc dựng từ các ý tưởng lý thuyết nhóm do Évariste Galois tiên phong) chính là đối tượng mà tính 'modular' của nó đang được khẳng định.
Mọi đường cong elliptic trên đều là modular: tồn tại một cấu xạ không hằng xác định trên , trong đó là dẫn của ; tương đương, bằng hàm của một dạng mới trọng số trên .
Vì sao đúng?
Tính modular biến mỗi đường cong elliptic thành một dạng modular được ngụy trang, chuyển bộ máy giải tích mạnh mẽ sẵn có cho dạng modular (tiếp tục giải tích, phương trình hàm) sang cho đường cong elliptic, và — điều quan trọng cho Định lý lớn Fermat — nó có nghĩa là một đường cong không thể là modular thì không thể tồn tại.
Chứng minh
Wiles đã chứng minh tính modular cho các đường cong elliptic bán ổn định trên vào năm 1994–95 (với bước cuối cùng, một tiêu chuẩn số học cho đẳng cấu giữa các vành biến dạng và đại số Hecke — ' định lý' — được thiết lập cùng với Richard Taylor). Chiến lược này chứng minh rằng biểu diễn Galois trên môđun Tate -adic của , và biểu diễn tương ứng gắn với một dạng modular ứng viên, sống trong cùng một không gian biến dạng; chứng minh rằng vành biến dạng và đại số Hecke tác động lên dạng modular trùng nhau buộc mọi biểu diễn Galois được phép — đặc biệt là của — phải đến từ một dạng modular. Vì mọi đường cong bán ổn định là đủ để loại trừ một phản ví dụ cho phương trình Fermat (bất kỳ nghiệm nào cũng sẽ cho ra một đường cong Frey bán ổn định mà Kenneth Ribet đã chứng minh, qua chứng minh giả thuyết năm 1990 của ông, không thể là modular), điều này đã chứng minh Định lý lớn Fermat. Ràng buộc bán ổn định sau đó được gỡ bỏ hoàn toàn, mở rộng tính modular cho mọi đường cong elliptic trên , bởi Christophe Breuil, Brian Conrad, Fred Diamond, và Richard Taylor năm 2001.
Nghiên cứuBài toán mở: giả thuyết Birch và Swinnerton-Dyer và mật mã hậu lượng tử
Phương trình Weierstrass nào dưới đây bị suy biến (tức là KHÔNG xác định một đường cong elliptic)?
Phát biểu nào sau đây phải đúng với mọi đường cong elliptic trên trường hữu hạn ?
Theo định lý phân loại xoắn của Mazur, nhóm con nào dưới đây KHÔNG thể là nhóm xoắn của một đường cong elliptic trên ?
Định lý Modularity, được Wiles (cùng Taylor) chứng minh cho các đường cong elliptic bán ổn định vào năm 1994–95, là thành phần then chốt trong chứng minh bài toán cổ điển nào?
Tài liệu tham khảo
- Joseph H. Silverman (2009). The Arithmetic of Elliptic Curves · DOI:10.1007/978-0-387-09494-6
- Andrew Wiles (1995). Modular elliptic curves and Fermat's Last Theorem · DOI:10.2307/2118559
- Andrew Wiles / Clay Mathematics Institute (2000). The Birch and Swinnerton-Dyer Conjecture (official Millennium Problem description)
- Wouter Castryck, Thomas Decru (2022). An efficient key recovery attack on SIDH