[HACK] 23707-digit 19-Carmichael number

[Jesus Cea Avion]

Para la gente realmente interesada en estar al día en teoría de números
(obviamente primero tendrán que aprender lo básico) existe una lista de
correo de bastante bajo tráfico sobre novedades y nuevos descubrimientos
en ese campo, de los propios autores.

Y alguna vez que les he hecho alguna pregunta inteligente, me han
respondido de forma precisa, correcta y amable.

La lista está en "NmbrThry at listserv.nodak.edu".

Os adjunto un mensaje recibido hoy. No apto para espíritus sensibles :-)
:

>>>>>

Proposition: Let N be either a Carmichael number or a prime.
Let L be the least number such that P-1|L for every prime P|N.
Suppose that (N-1)/L=a*d and that Q=1+b*d*L and R=1+c*d*L are
distinct primes that do not divide N. Then M=N*Q*R is a
Carmichael number if and only if b|a+c*N and c|a+b*N.

Proof: M is a Carmichael number if and only if
(M-1)/(d*L)=a+(b+c+b*c*d*L)*N is divisible by both b and c.

Using this method, with b=1 and b=2, I found an all-titanic
23707-digit 19-Carmichael number, whose prime factors have
1132, 1132, 1162, 1171, 1193, 1199, 1201, 1205, 1214, 1230,
1244, 1246, 1279, 1286, 1300, 1310, 1366, 1412, 1435 digits.

The challenge consisted in a judgement of how to balance
ECM-GMP effort, to factorize (N-1)/L=a*d, against OpenPFGW effort,
to find primes of the form Q=1+b*d*L and R=1+c*d*L.

After some trial and error, I opted for massive use of OpenPFGW
effort, with modest ECM-GMP effort, to find a single 12-Carmichael
number with good factorization potential for (N-1)/L, followed by
massive use of ECM-GMP, with modest OpenPFGW effort, to extend this
to the 23707-digit all-titanic 19-Carmichael number proven in
http://physics.open.ac.uk/~dbroadhu/cert/carm19a.zip
which gives the factorization of the sole 19-Carmichael number that
I was able grow from an initial database of 35,000 3-Carmichael
numbers, each with about 3,400 digits. En route, ECM-GMP
extracted, inter alia, a p27 from a composite with 13k digits,
a p25 from one with 18k digits and a p22 from one with 21k digits.

This strategy sits between the Loeh-Niebuhr method for generating
Carmichael numbers with huge numbers of factors and the approach in
http://listserv.nodak.edu/scripts/wa.exe?A2=ind0212&L=nmbrthry&P=R2
yielding a 60351-digit Carmichael number with merely 3 prime factors.

David Broadhurst

<<<<<

-- 
Jesus Cea Avion                         _/_/      _/_/_/        _/_/_/
jcea at argo.es http://www.argo.es/~jcea/ _/_/    _/_/  _/_/    _/_/  _/_/
                                      _/_/    _/_/          _/_/_/_/_/
PGP Key Available at KeyServ   _/_/  _/_/    _/_/          _/_/  _/_/
"Things are not so easy"      _/_/  _/_/    _/_/  _/_/    _/_/  _/_/
"My name is Dump, Core Dump"   _/_/_/        _/_/_/      _/_/  _/_/
"El amor es poner tu felicidad en la felicidad de otro" - Leibniz