- I have found a 2066-digit 6-Carmichael number.

As far as I know, the previous record was 827

digits by Chris Caldwell and Harvey Dubner.

My algorithm has a time-cost scaling like

digits^7, whereas the Caldwell-Dubner method

is slower, scaling like digits^8.

The prime factors are of the form

p=24*m+1

q=48*m+1

r=72*m+1

s=144*m+1

t=288*m+1

u=288*m*Q(m)/d+1

where d is a proper divisor of the quartic

Q(m) = (p*q*r*s*t-1)/(t-1)

= 2*(5971968*m^4 + 518400*m^3 + 15264*m^2 + 191*m + 1)

with discriminant D=-131*4889. The concrete solution has

m=5^55*7*17*23*31*47*61*67*79*83*89*97*101*107*113*139*\

149*151*167*179*227*251*269*307*311*317*331*349*p25*p87

p25=8857830991926784681130749

p87=58135625972960605667773529074721763464097\

8604228948251312373613096541035977392154103019

Note that m is fully factorized. Crucially, all primes up

to 367 that are not in m appear in Q(m), thanks to

algebraic number theory and the CRT. Thus there is a plethora

of possible choices for d, with no less than 20 values

d < 52000 that make u prime, namely those in the set

{292,636,779,888,1824,4541,8159,8943,9909,11124,13416,

13862,14391,16211,22591,29591,30914,44377,45799,51546}

The largest 6-Carmichael number, with d=292, has 2066 digits

and its largest prime factor, u, is titanic, with 1032 digits.

In all 20 cases, the primality of u was proven by BLS,

since u-1 was more than 37% factorized, thanks to a large

number of small primes in m and Q(m), has well as the

two ECM primes in m, p25 and p87, above, and the factors

15053*9219467779*3936112849523*58820249374652939513*

32711792972604332700617729

found in Q(m) by using ECM up to the p30 level.

The key to this construction is the use of algebraic number

theory to separate [*] all the primes up to 367 into those

for which the quartic Q(m) may have zero residue and those

for which it may not. The latter are put by hand into m;

the former appear in Q(m) thanks to a CRT constraint,

which was implemented before quintuple sieving of

p,q,r,s,t, with a bitmap ranging over a search space of

half a billion integers, each of order 10^112, and each

guaranteeing more than a million trial divisors d.

Pfgw found that one of the sieved candidates gave 5 PrPs,

ECM factorized a c112 in the resultant CRT solution

for m into p25*p87 and pulled 5 primes out of Q(m),

allowing Pfgw to prove the primality of all 6 Carmichael

factors for each of the 20 values of d above.

Finally I remark that Konyagin-Pomerance provable

prime factors of a k-Carmichael number N, with

k=5,6,7, are obtainable by a generalization of my

method that apportions primes, distinguished by an

algebraic number field, with relative contributions

(23-3*k):(3*k-13) to m and a polynomial Q(m) of degree

(k-2). Here, with k=6, one puts a hundred digits

of each into m and Q(m) and is left with another

hundred to find by ECM, in order to achieve the

KP threshold of 30% for u=O(N^(1/2))=O(10^1000).

With k=5, the balance shifts to 4:1 in favour of m,

while with k=6 it is the other way round, 1:4 in favour

of Q(m). In each of the cases k=5,6,7, one is left to

factorize a composite of order

log(N)^(k-1)*N^((3*k-13)/(20*k-20))

resulting from the large integer in m that generates small

primes in Q(m), via the CRT. Here, with k=6, the composite

was of size log(N)^5*N*(1/20), i.e. the c112=p25*p87

in m that gave N=O(10^2000). At k=5, a factorization

of a composite of size log(N)^4*N^(1/40) is needed;

at k=7 the cost is higher: log(N)^6*N^(1/15). For

k<5, BLS provability is automatic, without any ECM work,

and for k>7 there is no way of achieving even

KP-provability by working with ECM solely on the more

tractable m.

I recently found a 4000-digit 5-Carmichael number,

thus quadrupling the Caldwell-Dubner record, which

stood at 1000 digits. For this I used Primo for the

largest factor, with 2000 digits. If one wished to

find a 5-Carmichael number with 1+1+1+1+4=8 thousand

digits, one would not want to invoke Primo at 4

thousand digits. The above considerations suggest that

it might be better to try to crack a 220-digit

composite with ECM and then use KP. Here, the random

nature of factorization actually helps: while ECM is

thrashing at a c220 one can be generating another by CRT,

in the hope that it will be easier to crack. ECPP

on the other hand is more deterministic: the price

of a 4k digit Primo proof does not vary as wildly as

does the price of factorizing a c220 of unknown

constitution. It was this consideration that lead

to the present work at k=6, where Primo at 1k digits

takes merely an hour, so that nothing would have

lost had the ECM proof-route not paid off even faster

than that.

David Broadhurst

[*] Note that when working with quartics, the Jacobi symbol is

of no help; instead I used the "polrootsmod" routine of Pari-GP. - --- djbroadhurst <d.broadhurst@...> wrote:
> OK, Phil, your turn to teach, please.

Yuppers. Fortran schmortran - do it in URL or Turing Machine. You

> > half the speed of a primorial newpgen

> Please, sir, how does NewPgen economically solve

> k=1/(-m#) mod p

> No problem working out -m# mod p,

> but then how do you best find the modular inverse

> Is it just the obvious O(log(p)) Euclid job?

> In which case I can do it in Fortran, with line-numbering :-)

were aware that Fortran is as capable as a Turing machine, weren't

you ;-)

Phil

=====

--

.sig selecter broken, please ignore.

__________________________________________________

Do You Yahoo!?

Yahoo! Sports - sign up for Fantasy Baseball

http://sports.yahoo.com