海里游 发表于 2011-11-16 09:45:26

用程序运行几种伪素数与大家共享

用程序运行几种伪素数,请大家鉴赏:
构造下面每一类奇伪素数都不到一分钟,时间越长越多,但根据输入的数据不同有时多,有时少。寻找偶伪素数就没有奇伪素数那么快了,有时一两个小时甚至几小时才找到一个十位数的偶伪素数
1、以2为底的伪素数
(1)、下面的伪素数都能整除2^60-1(也就是2^60-1能被下面的这些伪素整除),其中前面带*的是绝对伪素数,并且还不止这些,
*2821= 7 × 13 × 31
4681 = 31 × 151
10261 = 31 × 331
13741 = 7 × 13 × 151
13981 = 11 × 31 × 41
30121 = 7 × 13 × 331
*41041 = 7 × 11 × 13 × 41
49981 = 151 × 331
68101 = 11 × 41 × 151
80581 = 61 × 1321
149281 = 11 × 41 × 331
*172081 = 7 × 13 × 31 × 61
285541 = 31 × 61 × 151
625921 = 31 × 61 × 331
*838201 = 7 × 13 × 61 × 151
*852841 = 11 × 31 × 41 × 61
1837381 = 7 × 13 × 61 × 331
2503501 = 7 × 11 × 13 × 41 × 61
3048841 = 61 × 151 × 331
3726541 = 7 × 13 × 31 × 1321
4154161 = 11 × 41 × 61 × 151
6183601 = 31 × 151 × 1321
9106141 = 11 × 41 × 61 × 331
13554781 = 31 × 331 × 1321
18151861 = 7 × 13 × 151 × 1321
18468901 = 11 × 31 × 41 × 1321
39789841 = 7 × 13 × 331 × 1321

(2)、下面的伪素数都能整除2^140-1
5461 = 43 × 127
129921 = 3 × 11 × 31 × 127
1018921 = 71 × 113 × 127
1275681 = 3 × 11 × 29 × 31 × 43
1534541 = 43 × 127 × 281
6118141 = 71 × 86171
10004681 = 29 × 43 × 71 × 113
34540801 = 281 × 122921
36507801 = 3 × 11 × 31 × 127 × 281
2、以3为底的伪素数,并且下面的伪素数都能整除3^60-1
121 = 11^2
2821 = 7 × 13 × 31
7381 = 112 × 61
8401 = 31 × 271
15841 = 7 × 31 × 73
24661 = 7 × 13 × 271
138481 = 7 × 73 × 271
172081 = 7 × 13 × 31 × 61
278221 = 61 × 4561
341341 = 7 × 112 × 13 × 31
402721 = 11 × 31 × 1181
512461 = 31 × 61 × 271
551881 = 112 × 4561
966301 = 7 × 31 × 61 × 73
1016521 = 112 × 31 × 271
1182181 = 7 × 11 × 13 × 1181
1504321 = 7 × 13 × 61 × 271
1916761 = 7 × 112 × 31 × 73
3、以2为底并且因子中都含有因子331的伪素数
10261= 31 × 331
30121= 7 × 13 × 331
49981= 151 × 331
149281= 11 × 41 × 331
258511(= 11 × 71 × 331
476971= 11 × 131 × 331
625921= 31 × 61 × 331
983401= 331 × 2971
1023121= 11 × 281 × 331
1549411= 31 × 151 × 331
1837381= 7 × 13 × 61 × 331
1857241= 31 × 181 × 331
1896961= 11 × 331 × 521
2780731= 31 × 271 × 331
3048841= 61 × 151 × 331
3316951= 11 × 331 × 911
3763801= 83 × 137 × 331
5193721= 13 × 17 × 71 × 331
5551201= 31 × 331 × 541
5859031= 31 × 331 × 571
4、目前世界上比较稀少的偶伪素数
除现在网上能查得到的四个偶伪素
161038
215326
2568226
143742226
外,本人又找到13个现公布5个
7866046
9115426
213388066
377994926
1066079026
借助下面的网站测试一下,前面可能有错的,但只可能是笔误,不是运行问题。
http://wims.math.ecnu.edu.cn/wims/wims.cgi?session=MMC0178AE1.2&+lang=cn&+module=tool%2Farithmetic%2Fbezout.cn
http://wims.math.ecnu.edu.cn/wims/wims.cgi?session=JSC3E48A1F.2&+lang=cn&+module=tool%2Falgebra%2Ffactor.cn

利用这个网站的测试可能有限,对于指数超过四位可能运行不了。
下面说一种不常规的测试方法,信不信由你。
我先介绍一个带指数的整除性,
若D^n-1(D、n为非负整数)被a整除,则对于任何非负整数m都能使D^(n*m)-1被a整除.
前面关于1、中(1)所有伪素数(设伪素数为T)减去1(即:T-1)都能被60整除,因为T能整除2^60-1,T也就能整除2^(T-1)-1.即:T是以2为底的伪素数。
前面关于1、中(2)及2都是如此。
关于3每一个T都有一个能整除T的数据暂没提供这个数据,有条件的只能用:看2^(T-1)-1能否被T整除来测试了。
关于偶伪素数必须用:看2^T-2能否被T整除,即:看2*(2^(T-1)-1)能否能被T整除。
偶伪素数也是每个数都有一个测试数据,下面只给两个供测试用。

161038要用261测试,因为161038-1能被261整除并且2*(2^261-1)能被161038整除,
则:2*(2^161037-1)也能被161038整除。

213388066的测试数据是495,因为213388066-1能被495整除,并且2*(2^495-1)能被213388066整除,
则:2*(2^213388065-1)也能被213388066整除。
页: [1]
查看完整版本: 用程序运行几种伪素数与大家共享