Bài viết này giới thiệu phương pháp tính logarit rời rạc trên trường hữu hạn Zp của Danied Shanks và của Polig-Hellman. Dựa trên phương pháp của Danied Shanks, chúng tôi phát triển nó để giải bài toán logarit rời rạc trên vành Zn. | Phát triển thuật toán của Danied Shank để giải bài toán logarit rời rạc trên vành Zn Nghiên cứu khoa học công nghệ PHÁT TRIỂN THUẬT TOÁN CỦA DANIED SHANK ĐỂ GIẢI BÀI TOÁN LOGARIT RỜI RẠC TRÊN VÀNH Zn Lê Văn Tuấn1*, Bùi Thế Truyền2 Tóm tắt: Bài viết này giới thiệu phương pháp tính logarit rời rạc trên trường hữu hạn Zp của Danied Shanks và của Polig-Hellman. Dựa trên phương pháp của Danied Shanks, chúng tôi phát triển nó để giải bài toán logarit rời rạc trên vành Zn. Kết quả nghiên cứu được ứng dụng vào phân tích độ an toàn của lược đồ chữ ký số trên bài toán logarit rời rạc trong vành Zn Từ khoá: Vành hữu hạn, Trường hữu hạn, Bài toán logarit rời rạc. 1. MỞ ĐẦU Tương tự bài toán phân tích số nguyên lớn ra thừa số, bài toán logarit rời rạc thuộc lớp bài toán khó giải. Hiện nay, một lớp hệ mật khóa công khai và biến thể của nó được xây dựng dựa trên độ khó của bài toán này. Tuy nhiên, bài toán logarit rời rạc không phải khó giải trong mọi trường hợp. Chính vì thế, các nhà khoa học đã lợi dụng những trường hợp không khó của bài toán để xây dựng các thuật toán giải bài toán logarit rời rạc. Một thực tế cho thấy, đa số các thuật toán giải bài toán logarit rời rạc hiện nay, chỉ áp dụng được trên trường hữu hạn Zp. Trong khi đó, một số hệ mã khóa công khai và các biến thể của nó được xây dựng trên cấu trúc vành Zn. Với mục tiêu nhằm loại bỏ những mầm mống không an toàn cho các hệ mật khoá công khai và các hệ chữ ký số dựa trên độ khó của bài toán logarit rời rạc trên vành Zn, trên cơ sở tìm hiểu những thuật toán giải bài toán logarit rời rạc đã được công bố trên thế giới[2][3][5] và một số công trình liên quan đến bài toán logarit rời rạc trên vành Zn,[1][4][8], chúng tôi phát triển thuật toán Baby step Giant Step của Danied Shanks để giải được bài toán logarit rời rạc trên vành Zn. Giả sử nhóm cyclic G= là nhóm con của nhóm nhân và cỡ bậc của g là m bit. Khi đó bậc của g thuộc đoạn [2m-1,2m-1] và khoảng tìm giá trị .
