Re: Factoring Carmichael Numbers

[Paul Underwood <paulunderwood@mindless.com>]

Hi Bill,

thank you for the explanation about factor().

I have majorly increased the speed of my code, partly by incorporating factor() into it, but mostly by switching from expensive 2 selfridges Lucas sequences to 1 selfridge "Miller-Rabin" type calculations. The code now computes the maximum g.c.d of N with the "simple" algebraic factors of a^(n-1)-1.

{global(nm1);} \\obsolete
                                        
{Cf(n)=nm1=n-1;vecsort(CF(n));} // main function

{CF(N)=my(v,k,a,i,g,mx,V1,V2);v=valuation(nm1,2);while(1,
k=Mod(random(1000000)+2,N);a=k^(nm1/2^v);
mx=lift(gcd(a-1,N));for(i=0,v-1,g=lift(gcd(a+1,N));if(g>mx,mx=g);a*=a);
if(mx>1,if(ispseudoprime(mx),V1=[mx],if(#mx<3,V1=factor(mx)~[1,],V1=CF(mx)));
g=N/mx;if(ispseudoprime(g),V2=[g],if(#g<3,V2=factor(g)~[1,],V2=CF(g)));
return(concat(V1,V2))));}


> For 662.txt, it would finish in less than 5 seconds.
> For 5616.txt, it would take 7h, 6min, 216 ms.

Now:
662.txt 5 seconds
5616.txt 24mins 3515 ms.

Best

Paul Underwood