Re: peculiar galoisinit() behavior

[Igor Schein <igor@txc.com>]

On Mon, Jun 14, 2004 at 05:44:17PM +0200, Bill Allombert wrote:
> On Fri, Jun 11, 2004 at 07:13:35PM -0400, Igor Schein wrote:
> > Hi,
> > 
> > using latest CVS,
> > 
> > {galoisinit(
> > x^64 - 224*x^62 + 23552*x^60 - 1546848*x^58 + 71168328*x^56 - 2436833952*x^5
> > 4 + 64407288512*x^52 - 1346248726816*x^50 + 22638605928092*x^48 - 3100404236
> > 90592*x^46 + 3482991142252160*x^44 - 32107751441411296*x^42 + 24044849215906
> > 9432*x^40 - 1419156581985832480*x^38 + 6021441872671174464*x^36 - 1123013514
> > 6026525344*x^34 - 82256825364060916154*x^32 + 1006806032298827456352*x^30 - 
> > 5675649698314152988928*x^28 + 16929909843292332382944*x^26 + 514728199833124
> > 8762616*x^24 - 319192745820875674502624*x^22 + 1645617652634320066338112*x^2
> > 0 - 4509318893445328263106912*x^18 + 6060765603004828811362460*x^16 + 159543
> > 3811519440861448928*x^14 - 17237571860589604851458432*x^12 + 155539333684122
> > 61315069024*x^10 + 11439096820765481332943688*x^8 - 248990211573927140987579
> > 84*x^6 + 12932816995946524978942144*x^4 - 2199266291848578048793312*x^2 + 20
> > 628044238087844473601
> > )}
> > 
> > takes much longer than it should (IMO) before realizing the field is not Galois.
> 
> galoisinit() was designed on the premices that the input is a Galois
> polynomial and does not go out of its way to catch non-Galois polynomial
> sooner.
> 
> If you want a probabilistic check, use numberofconjugates:
> install("numberofconjugates","lGD0,L,");
> numberofconjugates(P)
> %1 = 32
> (So P has (at most) 32 automorphisms, and hence is not Galois).
> 
> In this specific case, galoisinit() is unlucky: none of the fourty
> prime numbers it tried shows that P is not galois.

So is this polynomial an equivalent of a Carmichael number in some sense? :)
What is the apriori probability of such scenario?

Igor