Bài viết này giới thiệu thuật toán của Pollard để giải bài toán phân tích số và bài toán logarit rời rạc. Dựa trên thuật toán của Pollard, chúng tôi xây dựng thuật toán để tính cấp của một phần tử trong Zn. | Phát triển thuật toán của Pollard tính cấp của phần tử trong Zn Công nghệ thông tin & Cơ sở toán học cho tin học PHÁT TRIỂN THUẬT TOÁN CỦA POLLARD TÍNH CẤP CỦA PHẦN TỬ TRONG Lê Văn Tuấn1*, Lều Đức Tân2 Tóm tắt: Bài viết này giới thiệu thuật toán của Pollard để giải bài toán phân tích số và bài toán logarit rời rạc. Dựa trên thuật toán của Pollard, chúng tôi xây dựng thuật toán để tính cấp của một phần tử trong . Kết quả nghiên cứu được ứng dụng vào phân tích độ an toàn của các lược đồ chữ ký số có độ an toàn dựa trên tính khó giải của bài toán logarit rời rạc trong vành Zn. Từ khóa: Bài toán phân tích số; Bài toán logarit rời rạc; Cấp của phần tử. 1. MỞ ĐẦU Hiện nay, hệ mật khoá công khai cùng các biến thể của nó, có độ an toàn dựa trên tính khó giải của bài toán logarit rời rạc trên vành Zn, đang được các nhà khoa học trong nước và trên thế giới nghiên cứu và phát triển [1] [2] [4]. Đồng thời, việc nghiên cứu và phát triển các thuật toán giải bài toán logarit rời rạc trên vành Zn cũng được quan tâm bởi các nhà khoa học. Bởi vì những thuật toán giải bài toán logarit rời rạc trên vành Zn là cơ sở để xây dựng tham số an toàn cho hệ mật cùng các biến thể có độ an toàn dựa trên tính khó giải của bài toán này. Việc nghiên cứu ra các thuật toán để giải bài toán logarit rời rạc trên trường GF(p) đã được nhiều nhà khoa học nghiên cứu, phát triển và đang được ứng dụng trên thực tế, tiêu biểu là tác giả Pollard với thuật toán mang tên Rho Pollard [6]. Tuy nhiên, cho đến nay vẫn chưa có thuật toán nào trên thế giới và trong nước được công bố để giải bài toán logarit rời rạc trên vành Zn. Một điều hiển nhiên rằng, nếu tính được cấp của các phần tử trên thì hầu hết các thuật toán giải bài toán logarit rời rạc trên trường GF(p) có thể áp dụng để giải bài toán logarit rời rạc trên vành Zn. Vậy, để giải bài toán logarit rời rạc trên vành Zn, thì việc tính cấp của của phần tử thuộc nhóm có vai trò quyết định. Trong lý thuyết .
