Re: Factoring Carmichael Numbers

[Paul Underwood <paulunderwood@mindless.com>]

Bill wrote:

> By curiosity, why would you need to factor such numbers ? They are almost always
> built from their factorisation.

I am factoring Carmichael numbers for fun!


> You can probably speed up your code by skipping ispseudoprime until the factor
> are fairly small (or fail to factor).

Thanks for the idea.

My latest code, which I am trying to make more parallel, is:

{CfMR(n)=e=valuation(n-1,2);nm1bye=(n-1)>>e;export(e,nm1bye);vecsort(CFMR(n));}  

{CFMR(N)=my(a,i,g,V=[],v,R=[],r);while(#R==0,
a=0;while(gcd(a,N)!=1||a%N==1,a=random(10000000)+2);a=Mod(a,N)^nm1bye;
g=lift(gcd(a-1,N));if(g>1,V=concat(V,g));
i=e;while(1,i--;g=lift(gcd(a+1,N));if(g>1,V=concat(V,g));if(i<0,break,a*=a));
parforeach(V,v,ispseudoprime(v),r,if(r,R=concat(R,v),R=concat(R,CFMR(v)))));R;}

Can you see how to make it truly parallel (apart from the first exponent)?

Best

Paul