求解离散对数问题的Terr算法
春秋十二月发表于 2024-08-15 14:35:00
基本原理
再来看Terr算法用到的如下定理
定理 （基于参考文献1改正后的描述）对每一正整数t，存在唯一确定的一组整数k和j，0<=k<j，使得t=Tj+1-k，其中T0=0，Tn=Tn-1+n-1，n>=1
定理 （基于参考文献1改正后的描述）对每一正整数t，存在唯一确定的一组整数k和j，0<=k<j，使得t=Tj+1-k，其中T0=0，Tn=Tn-1+n-1，n>=1
如果t=0，则j在区间[0,1)，故只能取0，此时k=0与条件k<j矛盾，所以参考文献1中原来定理的描述“对每一非负整数t”是错误的。下面列举一些实例验证
t=1 => j=1, k=0
t=2 => j=2, k=1
t=3 => j=2, k=0
t=4 => j=3, k=2
t=5 => j=3, k=1
t=6 => j=3, k=0
算法伪代码
例子测验
参考文献
算法伪代码
例子测验
参考文献
[1] 代数学基础与有限域 林东岱