## Re: [PrimeNumbers] Carmichael numbers of order 2

Expand Messages
• 2009/3/31 David Broadhurst ... Using L=50227322745600 smooth number, |P(2,L)|=60, the above man-in-the-middle approach in c program:
Message 1 of 12 , Apr 1, 2009
• 0 Attachment

>
> > 97723892848682923994567734100095132801 =
> > 59*67*71*79*89*101*113*191*233*239*307*349*379*911*2089*5279
>
> A Pari-GP script for producing 246 such pseudoprimes is
>
> \\ erdos2.gp
> L=2^7*3^3*5^2*7*11*13*17*19*29; \\ super-smooth seed
> mp=sqrtint(L+1);A=[];B=[];C=[];k=0;sa=[1];sb=[1];
> {forprime(p=1,mp,if(gcd(L,p)==1&&L%(p^2-1)==0,
> k=k+1;if(k%2,A=concat(A,p),B=concat(B,p))));}
> for(k=1,#A,sa=concat(sa,sa*A[k]));
> for(k=1,#B,sb=concat(sb,sb*B[k]));
> st=vecsort(concat(sa%L,vector(#sb,k,(1/sb[k])%L)));
> for(k=3,#st,r=st[k];if(r==st[k-1],C=concat(C,r)));
> {for(k=1,#C,if(k%10==0,print("\\\\ done "k));c=C[k];
> for(j=1,#sa,if(sa[j]%L==c,t=sa[j];break));d=(1/c)%L;
> for(j=1,#sb,if(sb[j]%L==d,t=t*sb[j];break));C[k]=t;)}
> C=vecsort(C);print("{C=[");for(k=1,#C,print(C[k]","));
> print(#C"];}");print(round(gettime/10^3)" seconds");
>
> but take care: I allocated 3GB of core.
>
> This generates pseudoprimes N such that, for every prime p
> dividing N, both p-1 and p+1 divide N-1. The full output,
> comprising 246 "Carmichael numbers of order 2", is in
> and was obtained in 675 seconds, using 2.7 GB of core.
> The largest pseudoprime, found with the seed L, was
>
> 127905790005702291893660711189034208857122374296\
> 660769359758600083769407029360111561601
> =
> 23*31*41*43*53*67*71*79*89*109*113*131*181*199
> *239*271*307*349*379*419*449*463*521*571*701
> *1217*1429*1871*2089*2551*4159*5279*5851*9281
>
> and has 34 prime factors.
>
> This Erdos-type algorithm was outlined in a talk
> entitled "Higher-order Carmichael numbers",
> given by Everett W. Howe in December 2006:
> alumnus.caltech.edu/~however/talks/FortCollins.pdf<http://alumnus.caltech.edu/%7Ehowever/talks/FortCollins.pdf>
>
>
>
>

Using L=50227322745600 smooth number, |P(2,L)|=60, the above
man-in-the-middle approach in c program:
#P=26 and #Q=34 was possible using 1GB Ram in about half a day. The expected
number of solutions is 2^60/eulerphi(L)=143643, in fact it has been found

[Non-text portions of this message have been removed]
• I have sent an on-line message to Robert Gerbicz mooting the possibility to a distributed search for a Carmichael number of order 3. [Actually, I intended it
Message 2 of 12 , Apr 1, 2009
• 0 Attachment
I have sent an on-line message to Robert Gerbicz
mooting the possibility to a distributed search
for a Carmichael number of order 3.

[Actually, I intended it to go the list,
but forgot that this is not the default,
so I don't have a copy my own suggestion :-(
Perhaps Robert might post my lost message, here?]

David (not used to this unfriendly on-line default option)
• ... I have tested these. And every single one of them is right! http://www.springerlink.com/content/km644472gh145147/ Congrats to Robert David
Message 3 of 12 , Apr 1, 2009
• 0 Attachment
Robert Gerbicz <robert.gerbicz@...> wrote:

> 144153 Carmichael numbers of order 2

I have tested these.
"And every single one of them is right!"

Congrats to Robert

David
• I was lazy and did not use binary indexing for products of primes. Yes, I used long long int (8bytes) to store the residue (L
Message 4 of 12 , Apr 2, 2009
• 0 Attachment
"I was lazy and did not use binary indexing for products of primes."

Yes, I used long long int (8bytes) to store the residue (L<2^63), and int (4
bytes) to store the offset of the prime divisors (there were 26 primes in P
so it was enough).

Searching for Carmichael number of order 3 would be very hard:
by the following quick code:
generatesmooth(n)=T=1;forprime(p=2,n,q=p;while(q*p<=n,q*=p);T*=q);return(T)
this is generating super smooth numbers, but for example for n=1000 this is
giving only P(3,T)~225 numbers
, the last 3 of them in order what I have found are:
153572717
217815289
264982051
So there are very few larger primes in P(3,T) set. Say there are another 25,
then the expected number of solutions are
2^250/eulerphi(generatesmooth(1000))=3*10^(-357), and it would require about
2^200 multiplications/divisions (using man-in-the middle algorithm #P=25,
#Q=200). Obviously using smaller n gives larger but still very small
probability to find a 3 order number. So we have to increase the value of n:

For example: L=generatesmooth(20000) gives P(L,3)>30000 primes and this
means that it generates many Carmichael numbers of order 3:
2^30000/eulerphi(L)>>1. But to find even one solution using this L value is
still very hard.

[Non-text portions of this message have been removed]
• In a talk http://alumnus.caltech.edu/%7Ehowever/talks/FortCollins.pdf given in December 2006, Everett Howe posed this Open Problem : What are the first 3
Message 5 of 12 , Apr 2, 2009
• 0 Attachment
In a talk
http://alumnus.caltech.edu/%7Ehowever/talks/FortCollins.pdf
given in December 2006, Everett Howe posed this "Open Problem":

"What are the first 3 Carmichael numbers of order 2?"

443372888629441
39671149333495681
842526563598720001

• ... Richard Finch calls these unusually strong Lucas-Carmichael-minus (uLC-) numbers, with p^2-1|N-1, for every prime p|N. See:
Message 6 of 12 , Apr 3, 2009
• 0 Attachment

> "What are the first 3 Carmichael numbers of order 2?"
>
> 443372888629441
> 39671149333495681
> 842526563598720001

Richard Finch calls these
"unusually strong Lucas-Carmichael-minus" (uLC-) numbers,
with p^2-1|N-1, for every prime p|N. See:
http://www.chalcedon.demon.co.uk/rgep/p20.pdf

I found the third of these by mining Richard's file of
Carmichael numbers between 10^17 than 10^18.
http://www.chalcedon.demon.co.uk/rgep/cartable.html

Richard classified
582920080863121 = 41 * 53 * 79 * 103 * 239 * 271 * 509
as a "strong", but not "unusually strong",
Lucas-Carmichael-minus number
since in this case both p-1 and p+1
divide N-1, for each prime p|N, but p^2-1
does not divide N-1 in the cases p = 79, 239, 271,
where p^2 = 1 mod 2^5
whilst N = 17 mod 2^5.

If we ask merely that p-1 and (p+1)/2 divide N-1,
then the following 3 numbers also occur, for N < 10^18:
28295303263921
894221105778001
2013745337604001
making 7 in all, of which only

842526563598720001
= 17 * 61 * 71 * 89 * 197 * 311 * 769 * 2729

occurs for 10^18 > N > 10^17.

Finally, I remark that Richard found precisely one
"unusually strong Lucas-Carmichael-plus" (uLC+) number,
with p^2-1|N+1, for prime p|N and N < 10^13, namely

79397009999 = 23 * 29 * 41 * 43 * 251 * 269.

David
• Oh dear, another silly typo: I meant Richard Pinch, of course.
Message 7 of 12 , Apr 3, 2009
• 0 Attachment
Oh dear, another silly typo: I meant Richard Pinch, of course.
Your message has been successfully submitted and would be delivered to recipients shortly.