Counter-examples to is_carmichael(n)

[trizen]

For large enough inputs (>10^50), is_carmichael(n) uses a probable test to determine if n is probably a Carmichael number.

However, there are counter-examples to this approach (see also A285549), which makes the function to return true even if n is not a Carmichael number.

An example for such a number (see on factordb):

85474748242379385366094816268973624888150242213226622180749138318386315935863212081942773317297904345474600957207428590062778602152519956800727219132027890643383467070099011582284945709124001108514764722966245494493169941622314836646386558535398146857006553207552461902964756053556805850282748662504578139090961477044287402823322355055911488039369571766331538282989461368172866093039969460784972736481613017667409050543252201255683285242294097740381698721

The prime factors of the above number are:

p = 206730196442584779649621482864996679457396164999826860005439642699126532367829802133495310863905565334850031426826557127649035216408610689106208254316971417542056134302026422176146550376860493876672577460870441427154185011695841
q = 413460392885169559299242965729993358914792329999653720010879285398253064735659604266990621727811130669700062853653114255298070432817221378212416508633942835084112268604052844352293100753720987753345154921740882854308370023391681

One possible solution would be to use large random prime bases (rather than consecutive small prime bases) or to use the Miller-Rabin factorization method described in #19 which is very fast at factoring Fermat pseudoprimes.

Here's a list of 13 more non-Carmichael numbers that are reported as Carmichael numbers by is_carmichael(n): non-Carmichael.txt

[danaj]

Great catch. Working on it.