怎样求如下高次同余方程

hujunhua

不是巧合。中国剩余定理保证的。

zgg___

为什么是45113呢？莫非楼主在研习传说中的GNFS。呵呵。
http://scholar.lib.vt.edu/theses ... nrestricted/etd.pdf
这篇Matthew E. Briggs的硕士论文是一片非常好的介绍GNFS的论文。

mathe

不是巧合。中国剩余定理保证的。
在最一般的情况下，模为pq(两个不同的素数之积)的一元3次同余方程有9个根。
对模p,  这9个根可分成3组，每组3根。每组内3根两两之差都是p的倍数。
对模q，亦成如此。不过组合不同 ...
hujunhua 发表于 2010-4-10 22:29

有限域中方程的解在扩充域里面也称虚根吗？

hujunhua

不，是我搞错了。
由于5#是机器分解的结果，我相信x²+46x+81≡0(mod229)是无解的。由于没有检查二次式的判别式，我以为方程会有复根，故有此说。
经你一提醒，实际解了一下，原来根在$Z(\sqrt 2)$中, 不是虚根 。2不是229的平方剩余，所以$\sqrt 2$在F₂₂₉也无法开出，方程在Z中(或者说在F₂₂₉中)无解。

mathe

有限域里面讨论二次式的判别式应该是没有意义的。比如这里我们可以将
$x^2+46x+81-=0(mod 229)$改写成$(x+23)^2-=219(mod 229)$或$(x+23)^2-=-10(mod 229)$
由于219或-10不是模229的二次剩余，于是无解。

hujunhua

有限域F_p里二次式是否可约也是用判别式来判别的，看Legendre符号(Δ/p)。(Δ/p)=-1时不可约，(Δ/p)=1时可约。
mathe批评的对，这时就sign(Δ)来谈判别式是没有意义的。

由于mathe的质疑，我才认真考虑了一下F_p里不可约二次式的虚根问题，原来当且仅当p在z(i)中也是素数时，F_p里不可约二次式才有虚根，即在扩充的F_p里可约。扩充的F_p里有p²-1个元素(同余组)。

对于任意自然素数p，p也是Z(i)中的素数<=>p≡-1(mod 4)<=>Legendre符号(-1/p)=-1. 对这样的p及F_p中的不可约二次式f(x)，虽然(Δ/p)=-1使$\sqrt{\Delta}$在F_p内不可开方，但(-Δ/p)=(-1/p)(Δ/p)=1使$\sqrt{-\Delta}$可开方。由$\sqrt{\Delta}=i\sqrt{-\Delta}$知f(x)≡0(mod p)在Z(i)内有解。

例如：p=239时，x²+46x+81在F_p是不可约的，因为判别式Δ=46²-4×81=16²×7, (Δ/p)=(7/239)=-(1/7)=-1.
$\sqrt{\Delta}=16\sqrt{7}=16\sqrt{-7}i$≡2×35i. 所以[-23±35i]_p 是x²+46x+81≡0(mod p)的根。

另一方面，对于任意自然素数p，p不是Z(i)中的素数<=>p≡1(mod 4)<=>Legendre符号(-1/p)=1. 对这样的p及F_p中的不可约二次式f(x)，(Δ/p)=-1，而且(-Δ/p)=(-1/p)(Δ/p)=-1，还是无计可施。