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

郭先抢

修改后的证明可以到 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<q_2<q_3$
我们选择q_1=1,那么得出$q_3|3q_2-1$,所以$q_3=3q_2-1$或$2q_3=3q_2-1$
对于$q_3=3q_2-1$,由$q_2|3q_3-1$得出$q_2|9q_2-4$,所以$q_2|4$,于是只能$q_2=2$或$q_2=4$
其中$q_2=4$对应$p_2=15$不是素数淘汰，所以我们得出一个候选解$q_1=1,q_2=2,q_3=5$
对应$p_1=3,p_2=7,p_3=19,n=399$
现在我们要选择$a+bi$,
任意选择高斯整数1+2i,我们得出
$a+bi=(1+2i)^2 = i(mod 3)$ (这里实部为零有点让人不满意，但是3太小了，如果都是大一定素数就可以避免了）
$a+bi=(1+2i)^6=5+2i(mod 7)$
$a+bi=(1+2i)^18=7+3i(mod 19)$
由此得出$a+bi=159+79i(mod 399)$
然后可以验证$(159+79i)^399=159-79i(mod 399)$

郭先抢

如果允许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可以变动的时候反例是很容易构造的。