数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究信息安全中的离散对数问题是什么？
设 G 是一个具有 n 个元素的有限循环集。假设该群用乘法表示。设 b 是 G 的一个生成元，因此 G 的每个元素 g 都可以写成 g = bk 的形式，其中 k 是某个整数。
此外，任何两个定义 g 的此类整数都将模 n 同余。可以通过将 k 模 n 的同余类创建到 g 来表示一个函数 logb: G → Zn（其中 Zn 表示模 n 的整数环）。此函数是一个群同构，称为以 b 为底的离散算法。
在数学中，特别是在抽象代数及其应用中，离散对数是普通对数的集合论类似物。具体来说，普通对数 loga(b) 是实数或复数上方程 ax = b 的解。
同样，如果 g 和 h 是有限循环群 G 的元素，则方程 gx = h 的解 x 在群 G 中称为 h 以 g 为底的离散对数。
离散对数在数论中有着悠久的历史。最初，它们主要用于有限域中的计算。然而，它们相当模糊，就像整数分解问题 (IFP) 一样。
离散对数问题 (DLP) 是实现公钥密码系统必不可少的首要工具。一些流行的现代密码算法基于 DLP 来保证其安全性。它基于此问题的复杂性。Diffie-Hellman 在 1976 年提出了著名的 Diffie-Hellman 密钥协商方案。
示例
离散对数在群 (Zp) 中最容易学习。这是模素数 p 下的乘法群中的同余类 (1,…., p – 1)。
如果需要找到该群中某个数字的 k 次幂，则可以通过将其 k 次幂作为整数找到，然后找到除以 p 后余数。
此过程称为离散指数。
例如，考虑 (Z17)x 。为了在该群中计算 34，可以先计算 34 = 81，然后将 81 除以 17 得到余数 13。
因此，在群 (Z17)x 中，34 = 13。离散对数只是逆运算。例如，可以针对 k 求解方程 3k = 13 (mod 17)。
在这种情况下，k = 4 是一个解。由于 316 ≡ 1(mod 17)，因此如果 n 是整数，则 34+16n ≡ 13 x 1n ≡ 13 (mod 17)。
因此，该方程有无限多个形式为 4 + 16n 的解。此外，因为 16 是满足 3m ≡ 1 (mod 17) 的最小正整数 m，即 16 是 (Z17)x 中 3 的阶，所以只有这些解。类似地，该解可以定义为 k ≡ 4 (mod)16。
没有已知的计算一般离散对数 logbg 的有效算法。
4K+ 阅读量
