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

郭先抢

修改后的证明可以到 mathoverflow 去看，点标签 数论 素数 ，在第一页就可以找到。我相信稍有数学水平的人都可以看懂我的证明。 wsc810 发表于 2012-12-20 11:17

把链接发过来吧,这样简单一些

wsc810

已有人指出我的证明是错误的，看来该问题的难度是我等人无法企及的。

mathe

最主要是这一类问题通常应该是不成立的，只是构造反例通常比较难，需要计算机和人工结合花费大量的时间

郭先抢

已有人指出我的证明是错误的，看来该问题的难度是我等人无法企及的。 wsc810 发表于 2012-12-21 08:39

呵呵,其实我在4#就指出了, 比如取虚部b=0,然后问题就转化成 a^2=a^(N+1)(modN), 当a与N互质的时候,就变成1=a^(N-1)(modN) 这其实就是费马伪素数的, 呵呵

mathe

如果允许a或b为0，自然反例很容易构造，不然，要困难一些，今天有空算了一下，发现也不算太难，基本手工就可以构造了。 我们看看能否构造出$n=p_1p_2p_3$的最简单情况，其中$p_1,p_2,p_3$都是模4为3的素数。 由于高斯整数环关于素数$p_i$的乘法群是$p_i^2-1$阶，由于$p_i^2-1$阶比较大，我们看能否选择一个它的因子作为候选周期，比如对于周期$p_i-1$我们很熟悉，就是所有整数（虚部为0）关于模$p_i$的周期都是$p_i-1$,由于这些数已经被楼主淘汰了，于是我们可以选择$a+bi$以$p_i+1$为周期即可，那么在这种情况下 由于$(a+bi)^{p_i+1}=1(mod p_i)$,而且我们知道$(a+bi)^{p_i}=a-bi(mod p_i)$ 而选择$a+bi$只要任意选择一个高斯整数取$p_i-1$次方即可 所以我们要求$n= -1(mod p_i+1)$ 为了方便起见，我们记$p_i=4*q_i-1$,而且我们不妨限定$q_1,q_2,q_3$两两互素，由此我们得出 $q_1q_2q_3|n+1=(4q_1-1)(4q_2-1)(4q_3-1)+1$ 所以$q_1|4q_2q_3-q_2-q_3$等。不妨设$q_1

郭先抢

如果允许a或b为0，自然反例很容易构造，不然，要困难一些，今天有空算了一下，发现也不算太难，基本手工就可以构造了。 我们看看能否构造出$n=p_1p_2p_3$的最简单情况，其中$p_1,p_2,p_3$都是模4为3的素数。 由于高 ... mathe 发表于 2012-12-23 13:14

王磊同学提出的算法的想法还是比较多的,但是 一个好的素性判定算法的提出,还是很不容易的吧, 不过他可以再接再厉

郭先抢

mathe的数学功底还是有的

郭先抢

我觉得应该算比较容易能找到反例的,只是不知道王磊为什么没有找到

mathe

题目中$q_1,q_2,q_3$两两互素可以去除，只要求$q_1|4q_2q_3-q_2-q_3$并且轮换即可 由此对于$q_1=2$可以构造出$q_1=2,q_2=20,q_3=222$对应$p_1=7,p_2=79,p_3=887,n=490511$ 同样，选择$a+bi=(1+2i)^6=5+2i(mod 7)$,$a+bi=(1+2i)^78=31+15i(mod 79)$,$a+bi=709+354i(mod 887)$ 得出$a+bi=294306+392408i(mod 490511)$ 不过结果我就不验证了，pari/gp简单计算要溢出。 我们只需要验证$(294306+392408i)^490511=294306-392408i(mod 490511)$即可

lsrong314

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