Re: Factoring Carmichael Numbers

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

On Thu, Apr 20, 2023 at 11:59:43AM +0200, Paul Underwood wrote:
> 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.

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

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

Cheers,
Bill.