所谓的伪素数是指满足费马小定理的合数.
Fermat 小定理: 设 $p$ 是一个素数, 且 $0 < a < p$, 则有 $a^{p-1}\equiv 1\pmod p$.
举出10000以内的所有伪素数. 比如1000以内的伪素数只有三个: 341, 561, 645.
10000 以内的pseudo prime 有:
341
561
645
1105
1387
1729
1905
2047
2465
2701
2821
3277
4033
4371
4681
5461
6601
7957
8321
8481
8911
------------
Total: 21
[10000, 20000] 以内的伪素数
10261, 10585, 11305,12801,13741,13747,13981,14491,15709,15841,16705,18705,18721,19951
1
>> 2^340
in> 2^340
out> 2239744742177804210557442280568444278121645497234649534899989100963791871180160945380877493271607115776
------------------------
>> 2^340 mod 341
in> 2^340@341
out> 1
------------------------
>> isprime(341)
in> isprime(341)
num=341
341 is a composite number.
It has a divisor: 11
------------------------
>> factorise(341)
in> factorise(341)
11*31
2
>> 2^560
in> 2^560
out> 3773962424821541352241554580988268890916921220416440428376206300245624162392148852086126725177658767541468375030763844899770584629924792632561434251432696043649395326976
------------------------
>> 2^560 mod 561
in> 2^560@561
out> 1
------------------------
>> isprime(561)
in> isprime(561)
num=561
561 is a composite number.
It has a divisor: 3
------------------------
>> factorise(561)
in> factorise(561)
3*11*17
3
>> 2^644
in> 2^644
out> 72999049881955123498258745691204661198291656115976958889267080286388402675338838184094604981077942396458276953177510516971019275542007007972042581115555427012031914789764239201325987075945660416
------------------------
>> 2^644 mod 645
in> 2^644@645
out> 1
------------------------
>> isprime(645)
in> isprime(645)
num=645
645 is a composite number.
It has a divisor: 3
------------------------
>> factorise(645)
in> factorise(645)
3*5*43
4
>> 2^1104
in> 2^1104
out> 217327764647901735884376228537482684576559015509079127959763147156450094840678695795286273331320969476777252207261558135600619608691758879538488773484810059550172215990502245308525826306634891692269394568419570824204774972354079304853684576515249286092412155717123183761518144065105857969346366006994938535479442383180648843906646016
------------------------
>> 2^1104 mod 1105
in> 2^1104@1105
out> 1
------------------------
>> factorise(1105)
in> factorise(1105)
5*13*17