探求大Carmichael数的一种方法

SEARCHING FOR LARGE CARMICHAEL NUMBERS

如果奇合数m满足:对每一个整数a,(a,m)=1,均有a^(m-1)≡1(mod m),则m称为Carmichael数.本文给出一种探求大Carmichael数的方法,并给出一些超过10^(8300)的Carmichael数.

Let m be an odd composite number. If for every integer a relatively prime to m, the congruence am-1=1 (mod m) holds, then m is called a Carmichael number.In this paper, we give an algorithm which searches for large Carmichael numbers with many prime factors effectively and some Carmichael numbers larger than 108300 are given.Algorithm.i) Take a suitable integer L=p1a1p2a2…p3a3, where pi is the i -th prime, such that L/2 has as many divisors as possible, not increasing the value of L . The numbers like L/2 were called highly composite by S. Ramanujan.ii) For every divisor d of L/2 , check the primality of g=2d+1.If g is a prime and qxL, then put q in a set S.iii) Sort the elements of S , obtainingwhere qi<qi+1.Partition S into two subsetswhere the value of subscript t belongs to a suitable interval. For example, n/3≤t≤n/2.iv) For every subset T of S, which has n-t-h elements (h=0,1,2,…). calculate f and g according to the congruencesfg=1(mod L),0<f,g<L.Using the Chinese Remainder Theorem subroutine, arithmetic modulo L can reduce to arithmetic modulo piai(i=1,2,…,s).v) Check by trial division if for some integer j(j=0,1,…)g+Lj=r1r2…rk,where r1< r2<…<rk and ri ∈ S1(1≤i≤k). If this is true, thenis a Carmichael number.