- 注册时间
- 2007-12-27
- 最后登录
- 1970-1-1
- 威望
- 星
- 金币
- 枚
- 贡献
- 分
- 经验
- 点
- 鲜花
- 朵
- 魅力
- 点
- 上传
- 次
- 下载
- 次
- 积分
- 40149
- 在线时间
- 小时
|
发表于 2024-4-11 10:29:47
|
显示全部楼层
1~89度共89个正弦值,选择其中44个互相不为余角的角度平均分配到等式两边,让它们乘积相等,到底是否存在,
即使我们不考虑45度角,那么不同选择方案还有$2^22*C_44^22$,其中$C_44^22$代表44对互为余角的角度到底哪些选择在等式左边,而$2^22$代表对于每对余角,到底选择小于45度的角还是大于45的的角,这个不同选择方案共8825230699926650880种,显然按现在计算机计算能力是很难穷举的。
而选择正弦和余弦没有什么区别,为方便起见,后面改为讨论89个角度的余弦值。
链接中得出$u=\cos(1\degree)$满足一个48次多项式m(x)。而其他88个角度的余弦值都显然可以表示为u的一个整系数多项式。所以这些一系列余弦值乘积(包含22个余弦值乘积)最终都可以表示为u的一个整系数多项式。
如果我们能够找到一个适当的有限域,把计算限制在有限域,那么这些满足条件的等式关系在对应的有限域也会成立,唯一的问题是有些不相等的关系在有限域里面也会相等。当然有限域越大,这种不相等在有限域内相等的情况会越少。如果我们找到一些足够大的有限域,那么在其中找到的相等关系会大部分原始情况也会相等,这样就可以把计算问题转移到有限域。
比如我们选择47阶有限域,我们得到对应的m(x)可以转为4个12次多项式的乘积
- [Mod(1, 47)*x^12 + Mod(44, 47)*x^10 + Mod(4, 47)*x^9 + Mod(21, 47)*x^8 + Mod(38, 47)*x^7 + Mod(37, 47)*x^6 + Mod(42, 47)*x^5 + Mod(35, 47)*x^4 + Mod(15, 47)*x^3 + Mod(37, 47)*x^2 + Mod(22, 47)*x + Mod(2, 47) 1]
- [ Mod(1, 47)*x^12 + Mod(44, 47)*x^10 + Mod(9, 47)*x^9 + Mod(21, 47)*x^8 + Mod(15, 47)*x^7 + Mod(8, 47)*x^6 + Mod(24, 47)*x^5 + Mod(8, 47)*x^4 + Mod(43, 47)*x^3 + Mod(6, 47)*x^2 + Mod(22, 47)*x + Mod(12, 47) 1]
- [ Mod(1, 47)*x^12 + Mod(44, 47)*x^10 + Mod(38, 47)*x^9 + Mod(21, 47)*x^8 + Mod(32, 47)*x^7 + Mod(8, 47)*x^6 + Mod(23, 47)*x^5 + Mod(8, 47)*x^4 + Mod(4, 47)*x^3 + Mod(6, 47)*x^2 + Mod(25, 47)*x + Mod(12, 47) 1]
- [ Mod(1, 47)*x^12 + Mod(44, 47)*x^10 + Mod(43, 47)*x^9 + Mod(21, 47)*x^8 + Mod(9, 47)*x^7 + Mod(37, 47)*x^6 + Mod(5, 47)*x^5 + Mod(35, 47)*x^4 + Mod(32, 47)*x^3 + Mod(37, 47)*x^2 + Mod(25, 47)*x + Mod(2, 47) 1]
复制代码
我们可以选择第二个因式作为新的m(x),然后求所有其它余弦值关于m(x)的余式,经计算可以知道这个有限域次数为$\frac{47^12-1}2=58095741554474289120$大概是所有需要检查的22个余弦值乘积的6.58倍。从平均效果来说,违例冲突的比例应该已经相对比较低了(还可以继续尝试选择更大的素因子的情况得到更大的有限域)。
需要注意的是这个有限域的次数58095741554474289120的所有素因子都不大(最大素因子为4021),于是这个有限域上的离散对数问题是容易计算的
也就是我们在这个有限域上,可以计算每个\(\cos(k\degree)=u^{d_k}\),其中$1\le d_k \lt 58095741554474289120$.
在得到这89个$d_k$以后,我们就可以把问题转化为从89个$Mod(d_k, 58095741554474289120)$选择44个,分布在等式两边,使得两边和相等,而且索引值之和为90的两个$d_k$不可以同时被使用。这个降级问题如果有效计算我还没有想好,但是看上去可能性是比较大,因为我们总是可以先采用58095741554474289120的因子作为模然后采用动态规划来寻找一些候选解来降低计算复杂度。 |
|