求离散对数,有什么好办法?

mathematica

我只知道mathematica的函数
MultiplicativeOrder[3, 10^20 + 39, 1111]

这个表示求x

\(3^x\equiv 1111 \pmod {10^{20}+39}\)

求解结果是

11 518195 851460 688003 + 100 000000 000000 000038k

这是用软件计算出来的,我就是想知道有没有好的快的办法计算出来

mathematica

最近看数论高次剩余的内容,发现解方程其实就是先大整数分解,再求解离散对数,
不知道求离散对数有没有比较快的办法

mathematica

mathematica 发表于 2019-3-21 11:38
最近看数论高次剩余的内容,发现解方程其实就是先大整数分解,再求解离散对数,
不知道求离散对数有没有比较 ...

23^x ≡ 1111 (mod 10^30+57)
x=20431396188147931063673575974
@.·.·.

mathe

离散对数难解是密码学的基础。如果离散对数计算容易，现在很多密码学方案都要推倒重来

nyy

mathematica 发表于 2019-3-23 08:28
23^x ≡ 1111 (mod 10^30+57)
x=20431396188147931063673575974
@.·.·.

1.                   GP/PARI CALCULATOR Version 2.15.4 (released)
   
2.           amd64 running mingw (x86-64/GMP-6.1.2 kernel) 64-bit version
   
3.            compiled: Jun 28 2023, gcc version 10-posix 20210110 (GCC)
   
4.                             threading engine: single
   
5.                  (readline v8.0 enabled, extended help enabled)
   
6. 
   
7.                      Copyright (C) 2000-2022 The PARI Group
   
8. 
   
9. PARI/GP is free software, covered by the GNU General Public License, and comes
   
10. WITHOUT ANY WARRANTY WHATSOEVER.
    
11. 
    
12. Type ? for help, \q to quit.
    
13. Type ?18 for how to get moral (and possibly technical) support.
    
14. 
    
15. parisizemax = 1600000000, primelimit = 500000
    
16. (11:12) gp > znlog(1111,Mod(3,10^20+39))
    
17.   *** znlog: Warning: increasing stack size to 16000000.
    
18. %1 = 11518195851460688003
    
19. (11:12) gp > znlog(1111,Mod(23,10^30+57))
    
20. %2 = 20431396188147931063673575974
    

复制代码

1. parisizemax = 400000000, primelimit = 500000
   
2. (12:44) gp > np=nextprime(10^40)
   
3. %1 = 10000000000000000000000000000000000000121
   
4. (12:44) gp > znlog(1111,znprimroot(np))
   
5.   *** znlog: Warning: increasing stack size to 400000000.
   
6. %2 = 350949205016697093673070464656598622956
   
7. (12:47) gp > znprimroot(%1)
   
8. %3 = Mod(6, 10000000000000000000000000000000000000121)
   

复制代码

这个计算用了三四分钟

上面的计算结果表明
\[6^{350949205016697093673070464656598622956}\equiv 1111 \pmod {10^{40}+121}\]