---
title: 離散對數
tags: crypto
lang: zh_tw
---

* [筆記總覽](https://hackmd.io/@LJP/rkerFdnqS)

[TOC]

# 離散對數
參考 [wiki: Discrete logarithm](https://en.wikipedia.org/wiki/Discrete_logarithm)

簡單來說, 在 Group $G$ 中, 兩個元素 $a, b \in G$

使得 $b^k = a$ 成立的 k 就說是 **discrete logarithm of a to the base b**

也就是 $k = log_ba$

## 離散對數難題
Discrete Logarithm Problem (DLP)

求 $k$ 的難易度取決於 Group $G$

若 $G$ 是 [整數模n乘法群](https://zh.wikipedia.org/wiki/%E6%95%B4%E6%95%B0%E6%A8%A1n%E4%B9%98%E6%B3%95%E7%BE%A4)，求 $k$ 就蠻困難的
若 $G$ 是 [橢圓曲線群](https://en.wikipedia.org/wiki/Elliptic_curve)，則是更困難的