找回密码
 欢迎注册
查看: 13520|回复: 5

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

[复制链接]
发表于 2018-1-16 16:08:09 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?欢迎注册

×
我们知道,
$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的时候引入的
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-1-17 08:49:04 | 显示全部楼层
嗯,确实是一个有难度,且有研究价值的问题
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-1-17 09:07:03 | 显示全部楼层
这个应该可以用群论来分析。正常8次多项式的加洛瓦群是8阶置换群(一个8!阶的群),而楼主给出的8次多项式的加洛瓦群都是$Z_2^3$
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2018-1-17 12:19:24 | 显示全部楼层
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$

点评

我还是先看看群论好了 才发现自己对$Z_2^3$的理解可能存在问题 以为只要都是整数根置换群就一样的  发表于 2018-1-17 12:36
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2022-2-25 01:06:39 | 显示全部楼层
我忽然想到了一个作死方法……取模然后枚举
取模的结果告诉我,符合条件的结果如果存在,会满足一个神奇的规律:

对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,可能会出现,平方之后要减的第一个数字是它们的倍数
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-29 02:38 , Processed in 0.044059 second(s), 17 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表