Lôgarit rời rạc

Lôgarit rời rạc là sự tiếp nối của phép tính lôgarit trên trường số thực vào các nhóm hữu hạn. Ta nhắc lại rằng với hai số thực x, y và cơ số a>0, a≠1,nếu ax=y thì x được gọi là lôgarit cơ số a của y, ký hiệu x= logay.

Lôgarit rời rạc có ứng dụng trong hệ mật mã khóa công khai Hệ mật mã Elgamal, Mật mã dựa trên ghép cặp (Pairing-based Cryptography)...

Cho p là một số nguyên tố. Xét nhóm nhân các số nguyên modulo p: với phép nhân modulo p.

Nếu ta tính luỹ thừa bậc k của một số trong nhóm rồi rút gọn theo modulo p thì ta được một số trong nhóm đó. Quá trình này được gọi là luỹ thừa rời rạc modulo p. Chẳng hạn với p=17, lấy a=3, k=4 ta có

.

Lôgarit rời rạc là phép tính ngược lại:

Biết: hãy tìm k.

Định nghĩa

[sửa | sửa mã nguồn]

Tổng quát, giả sử G là một nhóm cyclic hữu hạn có n phần tử. Chúng ta ký hiệu phép toán của G theo kiểu nhân. Giả sử b là một phần tử sinh của G; khi đó mọi phần tử g G có thể viết dưới dạng g = bk với một số nguyên k nào đó. Hơn nữa, hai số nguyên có cùng tính chất đó với gđồng dư theo modulo n. Chúng ta định nghĩa một hàm

(trong đó Zn ký hiệu cho vành các số nguyên modulo n) theo g là lớp các số nguyên k modulo n. Hàm này là một đồng cấu nhóm, được gọi là logarit rời rạc theo cơ số b.

Sau đây là công thức đổi cơ số giống như logarith thông thường: Nếu c là một phần tử sinh khác của G, thì:

Thuật toán

[sửa | sửa mã nguồn]

Chưa có thuật toán hiệu quả nào để tính logarit rời rạc tổng quát .

Có nhiều thuật toán phức tạp, thường sinh ra từ những thuật toán tương tự cho bài toán phân tích thừa số nguyên. Chúng chạy nhanh hơn các thuật toán thô sơ, nhưng vẫn còn chậm hơn so với thời gian đa thức.

Ứng dụng trong mật mã

[sửa | sửa mã nguồn]

Logarit rời rạc là bài toán khó (chưa biết một thuật toán hiệu quả nào), trong khi bài toán ngược luỹ thừa rời rạc lại không khó (có thể sử dụng thuật toán bình phương và nhân). Tình trạng này giống như tình hình giữa bài toán thừa số nguyên và phép nhân các số nguyên. Chúng đều có thể dùng để xây dựng cấu trúc cho một hệ mật mã.

Người ta thường chọn nhóm G trong mật mã logarit rời rạc là nhóm cyclic (Zp)×; chẳng hạn như mật mã ElGamal, Trao đổi khoá Diffie-Hellman, và Chữ ký số Elgamal.

Ngoài ra còn có mật mã sử dụng lôgarit rời rạc trong nhóm con cyclic của các đường elliptic trên trường hữu hạn; gọi là mật mã đường cong elliptic.

Tham khảo

[sửa | sửa mã nguồn]
Chúng tôi bán
Bài viết liên quan
Caffeine ảnh hưởng đến giấc ngủ của bạn như thế nào
Caffeine ảnh hưởng đến giấc ngủ của bạn như thế nào
Là một con nghiện cafe, mình phải thừa nhận bản thân tiêu thụ cafe rất nhiều trong cuộc sống thường ngày.
Hướng dẫn tính năng Thần Hỏa LMHT
Hướng dẫn tính năng Thần Hỏa LMHT
Thần Hỏa là một hệ thống thành tựu theo dõi chỉ số trên từng vị tướng giúp lưu lại, vinh danh và khoe mẽ nhưng khoảnh khắc thú vị trong và ngoài trận đấu
17 website hữu ích cho các web developer
17 website hữu ích cho các web developer
Giữ các trang web hữu ích có thể là cách nâng cao năng suất tối ưu, Dưới đây là một số trang web tốt nhất mà tôi sử dụng để giúp cuộc sống của tôi dễ dàng hơn
Con người rốt cuộc phải trải qua những gì mới có thể đạt đến sự giác ngộ?
Con người rốt cuộc phải trải qua những gì mới có thể đạt đến sự giác ngộ?
Mọi ý kiến và đánh giá của người khác đều chỉ là tạm thời, chỉ có trải nghiệm và thành tựu của chính mình mới đi theo suốt đời