Cho G là tập hợp tuần hoàn hữu hạn n phần tử. Giả sử nhóm viết dưới dạng nhân. Cho b là phần tử sinh của G, do đó mỗi phần tử g của G viết dạng g = bᵏ với k nguyên.
Hơn nữa, bất kỳ hai số nguyên nào định nghĩa g sẽ đồng dư modulo n. Ký hiệu hàm logb: G → Zn (Zn vòng số nguyên modulo n) bằng gán cho g lớp đồng dư k modulo n. Hàm này là đồng cấu nhóm gọi là logarit rời rạc cơ sở b.
Trong toán học, đặc biệt đại số trừu tượng và ứng dụng, logarit rời rạc là đối ứng lý thuyết tập của logarit thường. Cụ thể, logarit thường loga(b) là nghiệm phương trình aˣ = b trên số thực/phức.
Tương tự, nếu g và h là phần tử nhóm tuần hoàn hữu hạn G thì nghiệm x của phương trình gˣ = h gọi là logarit rời rạc cơ sở g của h trong nhóm G.
Logarit rời rạc có lịch sử lâu trong lý thuyết số. Ban đầu dùng chủ yếu tính toán trường hữu hạn. Tuy nhiên, khá mơ hồ chỉ như Bài toán Phân tích Thừa số Nguyên tố (IFP).
Công cụ chủ chốt triển khai hệ mật mã khóa công khai là Bài toán Logarit Rời rạc (DLP). Một số thuật toán mật mã hiện đại phổ biến dựa an ninh trên DLP. Dựa trên độ phức tạp bài toán này. Diffie-Hellman đề xuất scheme trao đổi khóa Diffie-Hellman nổi tiếng 1976.
Ví dụ
Logarit rời rạc dễ hiểu nhất trong nhóm (Zp). Nhóm lớp đồng dư (1,...,p-1) dưới nhân modulo số nguyên tố p.
Nếu cần tìm lũy thừa k của số trong nhóm này, làm bằng tìm lũy thừa k như số nguyên rồi lấy phần dư chia p.
Quá trình này gọi là lũy thừa rời rạc (discrete exponentiation).
Ví dụ, xét (Z17)ˣ. Tính 3⁴ trong nhóm, tính 3⁴=81, chia 81 cho 17 dư 13.
Do đó, 3⁴ = 13 trong nhóm (Z17)ˣ. Logarit rời rạc chỉ là phép nghịch. Ví dụ, giải 3ᵏ = 13 (mod 17) tìm k.
Ở đây k=4 là nghiệm. Vì 3¹⁶ ≡ 1 (mod 17), nếu n nguyên tử thì 3⁴⁺¹⁶ⁿ ≡ 13×1ⁿ ≡ 13 (mod 17).
Do đó phương trình có vô số nghiệm dạng 4+16n. Hơn nữa, vì 16 là số nguyên dương nhỏ nhất m thỏa 3ᵐ ≡ 1 (mod 17), tức 16 là cấp (order) của 3 trong (Z17)ˣ, chỉ có những nghiệm đó. Tương tự, nghiệm ký hiệu k ≡ 4 (mod 16).
Không có thuật toán hiệu quả tính logarit rời rạc tổng quát logbg.