伪素数基本理论及伪素数的应用

yangchuanju

请验证2047是一个以2为基的强伪素数！
要验证一个整数是不是强伪素数，需要用米勒法检验，
已知2047=23*89合数，2047-1=2046=2*1023，2的指数s=1，奇数t=1023，1≤j≤s-1，j不存在，没有对应的2^(2^j )(mod 2047)；
随后应计算2^1023 (mod 2047)的模余数，直接计算数值太大，可按以下简化法计算；
2^1,2^2,…2^11 (mod2047)=2,4,8,16,32,64,128,256,512,1024,1；2^11,2^22,…2^1023 (mod 2047)=1；
2^1023 (mod 2047)=1；通过了米勒检验，故2047是一个以2为基的强伪素数。（2047是一个以2为基的最小强伪素数）

请验证1373653是一个以2和3为基的强伪素数！
已知1373653=829*1657合数，1373653-1=1363652=2^2*343413=2^2*(3^3*7*23*79)，s=2，t=343413，j=1；
因j=1，直接计算2^343413、3^343413模1373653的余数和2^686826、3^686826模1373653的余数——
经计算知2^207 (mod 1373653)=483061，2^414 (mod 1373653)=1373652，2^621 (mod 1373653)=890592，2^828 (mod 1373653)=1，
……2^343413 (mod 1373653)=483061，2^686926 (mod 1373653)=1373652=-1；指数等于2t时模余为-1
3^207 (mod 1373653)=1，……3^343413 (mod 1373653)=1；指数等于t时模余为1
可知1373653是一个以2和3为基的强伪素数。

yangchuanju

整数1373653是一个以2为基的强伪素数吗？
AI智能回答
是
1373653是一个以2为基的强伪素数。
根据搜索结果，如果用2和3两个数进行测试，最小的强伪质数为1373653，大于10^6。
这意味着1373653在以2为基的测试中会通过强伪素数的检验，因此可以判定它是一个以2为基的强伪素数。
此外，有讨论提到1373653是否为强拟素数的问题，但未提供否定的证据，进一步支持了它作为强伪素数的身份。

yangchuanju

强伪素数，2为基的判定标准是什么?
AI智能回答
强伪素数的判定标准是：如果一个数n满足a^(n-1)≡1(mod n)，
并且在将n-1分解为2^r*k（其中k为奇数）时，存在某个i (0≤i<r)使得
a^(k*2^j) ≡-1(modn)，那么 n称为以a为基的强伪素数。
具体到以2为基的强伪素数，判定标准如下：
费马小定理：如果p是素数，且a是小于p的正整数，那么a^(p-1)≡1 (mod p)。
然而，有些合数也能满足这个条件，这些合数被称为伪素数。

二次探测定理：如果p是素数，x是小于p的正整数，且x^2≡1 (mod p)，
那么x的取值只能是1或者p-1。
如果存在x≠1且x≠p-1使得x^2 ≡1 (mod p)，则p不是素数。

Miller-Rabin素性测试：将n-1分解为2^r*k，其中k为奇数。
如果a^k≡1(mod  n) 或者存在某个j  (0≤i<r）使得a^(k*2^j) ≡-1(modn),
那么n称之为以a为基的强伪素数。

以2为基的强伪素数的判定步骤如下：
1、将n-1分解为2^r*k，其中k为奇数。
2、计算 2^k mod p，如果结果为1或n-1，则n是以2为基的强伪素数。
3、如果2^k mod n≠1且≠n-1，则不断平方2^k并取模，直到得到2^(k*2^i) mod n为n-1或者i=r。
如果在过程中得到n-1，则n是以2为基的强伪素数。

例如，341是一个合数（341=11*31），但它满足
2^340≡1 (mod 341)。通过进一步计算
2^170 mod 341和2^85 mod 341，可以发现341不是素数。

综上所述，判断一个数是否为2的强伪素数，需要通过上述步骤进行验证。

yangchuanju

请检验3215031751是不是以2357为基的强伪素数！
3215031751=151*751*28351
3215031750=2*3*3*3*3*5*5*5*7*37*613
先用2检验，余数循环周期是70875，2^70875模3215031751余1，
全程45362个余数1，半指数余1；
次用3检验，余数循环周期是6750，3^6750模3215031751余1，
全程476301个余数1，半指数余-1；
三用5检验，余数循环周期也是70875，5^70875模3215031751余1，
全程45362个余数1，半指数余1；
最后用7检验，余数循环周期是47250，7^47250模3215031751余1，
全程68043个余数1，半指数余-1；
被检数n减1的分解式中只有1个2，奇数t等于(n-1)/2；
根据2,5的半指数余1、3,7的半指数余-1即可断定n是一个以2,3,5,7为基的强伪素数。

yangchuanju

请检验134670080641是不是以234为基的强伪素数！
134670080641=211873*635617
134670080640=2*2*2*2*2*2*2*3*5*61*521*2207=2^7*1052110005
先用2检验，余数循环周期是105936，2^105936模134670080641余1，
全程1271240个余数1，半指数余1；
次用3检验，余数循环周期也是105936，3^105936模134670080641余1，
全程1271240个余数1，半指数余1；
经查对，被检数是399号以2和3为基的强伪素数。
最后用4检验，余数循环周期是52968，4^56968模134670080641余1，
全程2542480个余数1，半指数余1。

被检数n减1的分解式含7个素因子2，j=1,2,3,4,5,6，商需检验2^t、3^t、4^t及2^(t*2^j)、3^(t*2^j)、4^(t*2^j)模134670080641余数中有没有1或-1；
以下仅对4进行检验——
t=1052110005，模52968余6621，查4^6621模134670080641余73763545187（11位），
推知4^1052110005模134670080641余73763545187；
以下应该平方、平方、再平方，看一看有没有余-1的出现。
73763545187       
5441060598554590864969        28152089099
792540120638034631801        134670080640
从计算知平方二次后模余数是-1，       
从而得知被检数是以4为基的强伪素数，       
进一步得知被检数是以2,3,4为基的强伪素数。