一个暴难的问题·关于快速指数运算

.·.·.

我们知道，
$x^4=(x^2)^2$
$x^8=((x^2)^2)^2$
$x^16=(((x^2)^2)^2)^2$
……
于是
$x^9=x*x^8=x*(((x^2)^2)^2)$
借助类似的思想，我们可以利用比较少的计算次数，算出一个很高的幂次

那么，针对一般多项式呢？
就比如$ax^3+bx^2+cx+d$是否会有类似的结构呢？
答案应该是否定的，因为百度说秦九韶算法是最快的多项式算法

然而，对一些特殊的f，是可以的
比如，(ax+b)^k
这类多项式有一个特点就是有重根，这也是快速指数运算能够处理的部分。
于是，我在想，能否找到一些没有重根的多项式，可以进行快速模指数运算呢？
答案是肯定的：
比如，瞎凑一个出来：$i(g(e(c(ax+b)^2+d)^2+f)^2+h)^2+j$,这是一个16次的多项式，然而我们只用了9次乘法（乘系数5次，平方4次）
仿照快速指数运算我们可以算出$(ax+b)*(c(ax+b)^2+d)*e(c(ax+b)^2+d)^2+f)*(g(e(c(ax+b)^2+d)^2+f)^2+h)*i(g(e(c(ax+b)^2+d)^2+f)^2+h)^2+j$，这是一个31次的多项式
但是，对于这样的多项式，它们的根相当混乱而且很难控制。

我在想，能否找到一些特殊的多项式，这些多项式的根都是互不相同的整数，而这个多项式的运算可以使用快速指数运算呢？(比如，$((x^2 - 130)^2 - 10116)^2-33177600$，它的8个根是正负2,8,14,16，我们只用了3次乘法就得到了一个有8个不同根的多项式)

目前，我倾向于，做不到，但不确定是否真的是这样
于是，发上来让大家一起看看

Note:凑$((x^2 - 130)^2 - 10116)^2-33177600$的时候用到了65=1^2+8^2=4^2+7^2，平方是前面省事用x^2的时候引入的

gxqcn

嗯，确实是一个有难度，且有研究价值的问题

mathe

这个应该可以用群论来分析。正常8次多项式的加洛瓦群是8阶置换群（一个8!阶的群），而楼主给出的8次多项式的加洛瓦群都是$Z_2^3$

.·.·.

mathe 发表于 2018-1-17 09:07
这个应该可以用群论来分析。正常8次多项式的加洛瓦群是8阶置换群（一个8!阶的群），而楼主给出的8次多项式 ...

虽然没学过群论但觉得用$Z_2^3$解释会有问题
本来我准备用$(x^2-1)(x^2-9)(x^2-25)(x^2-49)$做例子的，结果发现死活凑不出来
然而$(x^2-1)(x^2-9)(x^2-25)(x^2-49)$的加洛瓦群应该也是$Z_2^3$

.·.·.

我忽然想到了一个作死方法……取模然后枚举
取模的结果告诉我，符合条件的结果如果存在，会满足一个神奇的规律：

对mod p=19,23,29,43，我们发现枚举得不到正确答案

1. for(i=1,p,for(j=1,p,my(v=vector(p,x,((((x^2-i)^2-j)^2)-1)%p+1));my(counter=Vec(0,p));for(k=1,p,counter[v[k]]+=1);my(g=vecsort(counter,,4));if(g[1]+g[2]==16,print([i,j]))))

复制代码

出现这个问题的原因是，在mod 19,23,29,43下都有两个整数根同余。验算知，对50000以内的素数p，只有这四个mod会出问题：

1. parforprime(p=17,50000,my(flag=0);for(i=1,p,for(j=1,p,my(v=vector(p,x,((((x^2-i)^2-j)^2)-1)%p+1));my(counter=Vec(0,p));for(k=1,p,counter[v[k]]+=1);my(g=vecsort(counter,,4));if(g[1]+g[2]==16,/*print([p,[i,j]]);*/flag=1;break));if(flag==1,break));if(flag==0,print([p,"flag"])))
   
2. [19, "flag"]
   
3. [23, "flag"]
   
4. [29, "flag"]
   
5. [43, "flag"]
   
6. cpu time = 6min, 29,442 ms, real time = 25,988 ms.

复制代码

进一步的分析发现，对17,37和53，看上去像是碰到了fermat小定理生效的情形，计算出的表达式必须形如((x^4-j)^2-k)^2 mod p，这是不正确的，因为((x^2-j)^2-k)^2至多有8个互不相同的整数根
于是我们可以得知，这16个两两不同的根，在mod17,19,23,29,37,43,53这7个数字下存在同余。

有点可惜的是这个思路走不下去了。
因为p上千之后，总存在k,l使得(((x^2-1)^2-j)^2-k)^2-l=0(mod p)对j=1或j=2（i=1）成立，这导致枚举根本得不到任何有效的信息

补充内容 (2022-2-25 16:34):
15小时以前脑子出了点问题……比如对mod53，可能会出现(((x^2-53i)^2-j)^2-k)^2-l这样的形状，在mod53的意义下53i被消掉——也就是对17，37和53，可能会出现，平方之后要减的第一个数字是它们的倍数