判断素性

medie2005

设$n=a*b+1,0<a<=b+1$,若对b的任一素因子p,都存在一个整数x,使:
$x^{n-1} mod n=1$以及$gcd(x^{(n-1)/p}-1,n)=1$,则n是素数.
而10^785 + 3有小素因子4337107.
因此,问题很简单了.

gxqcn

谢谢！学到了。

这里有更多的介绍：http://primes.utm.edu/prove/prove3_1.html

mathe

原帖由 gxqcn 于 2008-12-26 21:13 发表
谢谢！学到了。

这里有更多的介绍：http://primes.utm.edu/prove/prove3_1.html

Theorem 2:  Suppose n-1 = FR, where F>R, gcd(F,R) is one and the factorization of F is known.  If for every prime factor q of F there is an integer a>1 such that
$a^n-1=1(mod n)$, and
gcd(a(n-1)/q-1,n) = 1;
then n is prime.
(Notice that different a's can be used for each prime q.)  Theorem 2 can be improved even more: if F<R, but either every factor of R is greater than $sqrt(R/F)$; or $n<2F^3$, R=rF+s, 0<s<F, and r is odd or $s^2-4r$ is not a square; then n is prime.  If you are interested in these theorems, then it is well worth going to the source: [BLS75].
所以对于$n=(10^785 + 3)*10^785+1$
取$F=10^785,R=10^785+3$,那么R=1*F+3, 所以$s=3,r=1,s^2-4r=5$不是平方数。
所以只要找到一个a,使得$a^{n-1}=1(mod n)$,但是$a^{{n-1}/2}-1$和$a^{{n-1}/5}-1$都同n互素就可以了

gxqcn

直接用11# 的结论证明楼主的数是不行的，因为前提条件不满足，
后来我找了些资料，才知道允许 F < R 的一些前提，这才是我们需要的，也就是 mathe 上面叙述的。

mathe

11#的结论也可以用，不过复杂一些。
用11#的结论，由于已经得出$4337107|10^785 + 3$,取$F=4337107*10^785$就可以了，只是F多了一个素因子

medie2005

呵呵,还是mathe懂我.

无心人

我有疑惑
every是任何的意思吧
就是说光一个似乎不行吧

medie2005

F=4337107*10^785.
F的素因子只有2,5,4337107.
因此,只要对某个a,计算:
gcd(a^(n-1)/2-1,n)
gcd(a^(n-1)/5-1,n)
gcd(a^(n-1)/4337107-1,n)
就行了.

无心人

哦

明白了