求离散对数,有什么好办法?
本帖最后由 mathematica 于 2019-3-21 11:33 编辑我只知道mathematica的函数
MultiplicativeOrder
这个表示求x
\(3^x\equiv 1111 \pmod {10^{20}+39}\)
求解结果是
11 518195 851460 688003 + 100 000000 000000 000038k
这是用软件计算出来的,我就是想知道有没有好的快的办法计算出来 最近看数论高次剩余的内容,发现解方程其实就是先大整数分解,再求解离散对数,
不知道求离散对数有没有比较快的办法 mathematica 发表于 2019-3-21 11:38
最近看数论高次剩余的内容,发现解方程其实就是先大整数分解,再求解离散对数,
不知道求离散对数有没有比较 ...
23^x ≡ 1111 (mod 10^30+57)
x=20431396188147931063673575974
@.·.·. 离散对数难解是密码学的基础。如果离散对数计算容易，现在很多密码学方案都要推倒重来 本帖最后由 nyy 于 2024-1-12 12:51 编辑
mathematica 发表于 2019-3-23 08:28
23^x ≡ 1111 (mod 10^30+57)
x=20431396188147931063673575974
@.·.·.
GP/PARI CALCULATOR Version 2.15.4 (released)
amd64 running mingw (x86-64/GMP-6.1.2 kernel) 64-bit version
compiled: Jun 28 2023, gcc version 10-posix 20210110 (GCC)
threading engine: single
(readline v8.0 enabled, extended help enabled)
Copyright (C) 2000-2022 The PARI Group
PARI/GP is free software, covered by the GNU General Public License, and comes
WITHOUT ANY WARRANTY WHATSOEVER.
Type ? for help, \q to quit.
Type ?18 for how to get moral (and possibly technical) support.
parisizemax = 1600000000, primelimit = 500000
(11:12) gp > znlog(1111,Mod(3,10^20+39))
*** znlog: Warning: increasing stack size to 16000000.
%1 = 11518195851460688003
(11:12) gp > znlog(1111,Mod(23,10^30+57))
%2 = 20431396188147931063673575974
parisizemax = 400000000, primelimit = 500000
(12:44) gp > np=nextprime(10^40)
%1 = 10000000000000000000000000000000000000121
(12:44) gp > znlog(1111,znprimroot(np))
*** znlog: Warning: increasing stack size to 400000000.
%2 = 350949205016697093673070464656598622956
(12:47) gp > znprimroot(%1)
%3 = Mod(6, 10000000000000000000000000000000000000121)
这个计算用了三四分钟
上面的计算结果表明
\
页:
[1]