如下方法是一个确定性的素性检验方法吗

wsc810

35# mathe


注意到在这个反例中有$N(i)=1 (mod 3) ,N(5+2i)=1 (mod 7),N(7+3i)=1 (mod 19)$

$N(159+79i)=1 (mod 399)$ ,因为 $N(2+3I)=13$，它的范数比较小

所以满足$(2+3I)^n=2-3I(mod n)$ 的合数解有可能是不存在的。

mathe

39# mathe


可惜这个结果是错的。
In[1]:= PowerMod[294306 + 392408 I, 490511, 490511]
Out[1]= -154002 - 155724 I
我想知道对于(2+3I)^n=2-3I(mod n)有没有解。因为a+bI可以变动的时候反例是很容易构造 ...
lsrong314 发表于 2012-12-23 16:39

对的，是qi算错了

mathe

35# mathe


注意到在这个反例中有$N(i)=1 (mod 3) ,N(5+2i)=1 (mod 7),N(7+3i)=1 (mod 19)$

$N(159+79i)=1 (mod 399)$ ,因为 $N(2+3I)=13$，它的范数比较小

所以满足$(2+3I)^n=2-3I(mod n)$ 的合数解有可 ...
wsc810 发表于 2012-12-23 18:13

这个条件是我构造时特意选取的，为了更方便
当然如果你指定底，构造难道会大很多，不论什么底都一样。主要问题在于必须要求这个高斯整数模素数是个合适的冪，由于周期大，构造所以难度大

wsc810

对的，是qi算错了
mathe 发表于 2012-12-23 18:46

正确的qi是多少？