|
|
吴代业以乘代除判断某整数的素合性
假定我们并不知道9973是合数还是素数,由于9973的平方根小于100,我们用100以内的所有素数2,3,5,7……97逐个试除之,
25步试除法都除不尽,从而断定9973是一个素数。
再用“吴代业以乘代除”法判断——
两吴代业数的乘积模30余数表
* 1 7 11 13 17 19 23 29
1 1 7 11 13 17 19 23 29
7 7 19 17 1 29 13 11 23
11 11 17 1 23 7 29 13 19
13 13 1 23 19 11 7 29 17
17 17 29 7 11 19 23 1 13
19 19 13 29 7 23 1 17 11
23 23 11 13 29 1 17 19 7
29 29 23 19 17 13 11 7 1
9973模30余13,30k+13类合数可能是(30m+1)*(30n+13)、(30m+7)*(30n+19)、(30m+11)*(30n+23)或(30m+17)*(30n+29)的乘积;
对于(30m+1)*(30n+13),当m=1,2,3……11时分别乘以30n+13(试乘时n至少取10或11、5或6、3或4……1或2,各两个n,一个积小于9973另一个积大于9973),至少试乘22次;
其它3式类似,总试乘次数不少于88次,各次试乘之积中都没有9973,最后才能确定9973是素数;
当然如果试乘之中有一个乘积等于9973,那么就能确定9973不是素数,进而找到9973的2个因子或素因子。
|
|