陶宏指数逆元恒等式

标签: 科学计算

taohong 2026-05-21 08:43:15

N是奇整数,Y ≡ 2⁻ˣ(mod N)
那么:Y * 2ˣ = A * N + 1,这个A会是”什么“?为了消掉 Y ,两边模一下2ˣ,
0  ≡  A * N + 1 (mod 2ˣ)
A * N ≡ -1 (mod 2ˣ)
A ≡ -N⁻¹(mod 2ˣ)
进而:A ≡ (-N)⁻¹(mod 2ˣ),Y = (A * N + 1) / 2ˣ 
代码公式:Y = (A * N + 1) >> x,我暂且命名为”陶宏指数逆元恒等式“
如果我告诉你,A 是”全息量子数“,那么开启”经典模拟shor“的时代,超越”二次筛法“、”数域筛法“指日可待!

回复

回复

重置 提交