factor et GF

Bugs

Modérateur : xcasadmin

Répondre
frederic han
Messages : 1137
Inscription : dim. mai 20, 2007 7:09 am
Localisation : Paris
Contact :

factor et GF

Message par frederic han » mer. oct. 03, 2007 9:38 am

Bonjour a tous,

je ne comprend pas trop factor sur F27

0>> F:=GF(3,3,['u','F'])
GF(3,u^3+2*u^2+1,[u,F],undef)

// Time 0
1>> b:=F(u)
F(u)

// Time 0
2>> b^3
F(u^2-1)

// Time 0
3>> factor(x^4-1,b)
(F(-u^2+u)*x+F(u^2-u))*(x+F(1))*(F(u)*x^2+F(u))

celui la me semble OK
// Time 0.0078125

mais
4>> factor(x^3-x-1,b)
F(-u^2+u)

a perdu les x.

parisse
Messages : 5734
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Message par parisse » mer. oct. 03, 2007 1:47 pm

j'ai un doute mathematique: je calcule d'abord le pgcd de x^27-x et x^3-x-1 (mod 3), ce qui me donne x^3-x-1, donc x^3-x-1 devrait se decomposer en produit de 3 facteurs de degre 1, correspondant a 3 racines de x^3-x-1, c'est correct? Ensuite, malheureusement quand j'evalue le polynome en x=tous les elements de GF(3^3) aucun ne semble annuler le polynome.
Bon en y regardant de plus pres, il me semble que c'est mon algo de generation d'un element de GF(3^3) qui ne les fournit pas tous.

parisse
Messages : 5734
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Message par parisse » mer. oct. 03, 2007 6:28 pm

bon, c'est juste que je generais les elements du corps avec -13..13 au lieu de 0..26.
Edite le 4/10, j'ai enleve le code qui posait d'autres problemes, il vaut mieux reprendre l'archive.

frederic han
Messages : 1137
Inscription : dim. mai 20, 2007 7:09 am
Localisation : Paris
Contact :

Message par frederic han » jeu. oct. 04, 2007 9:03 am

Oui, j'ai teste un peu hier soir ca me donnait de bonnes reponses. par ex:
X^p-X+1 est irred sur Fp et scinde sur Fp^p, ses racines se deduisent l'une de l'autre par addition par 1, mais parfois ca plantait (Ex p=7),
je vais tester en reprenant l'archive 0.7.2 car je n'avais fait qu'une compilation partielle

Merci
(edite a 12h)
Ok, j'ai teste la 0.7.2,
pour p=3 et 5 ca marche, mais p=7 c'est peut etre trop gros? ca plante:

G:=GF(7,7,[a,G])
b:=G(a)
factor(x^7-x+1,b)

mais
pari()
factorff(x^7-x+1,7,a^7-a+1) est immediat

parisse
Messages : 5734
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Message par parisse » sam. oct. 06, 2007 4:05 pm

frederic han a écrit : Ok, j'ai teste la 0.7.2,
pour p=3 et 5 ca marche, mais p=7 c'est peut etre trop gros? ca plante:

G:=GF(7,7,[a,G])
b:=G(a)
factor(x^7-x+1,b)

mais
pari()
factorff(x^7-x+1,7,a^7-a+1) est immediat
oui, il semble que mon algo de factorisation est loin d'etre optimal, en tous cas j'ai un probleme pour calculer un pgcd de x^(p^n) avec p=n=7, la taille d'un tableau local est trop grande pour la pile, il faudrait que je declare la variable dynamiquement avec new/delete.

parisse
Messages : 5734
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Message par parisse » sam. oct. 06, 2007 6:14 pm

bon, avec la correction new/delete, ca ne bugge plus, mais ca pedale. En fait c'est tout mon code de factorisation qu'il faudra revoir pour les corps de grande taille, il a été écrit pour factoriser des polynomes dans Z/pZ pour p petit...

parisse
Messages : 5734
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Message par parisse » lun. oct. 08, 2007 9:04 am

voila, j'ai fait les modifs pour que la factorisation sur des corps finis de grand cardinal marche raisonnablement. J'espere ne pas avoir introduit de bug...

frederic han
Messages : 1137
Inscription : dim. mai 20, 2007 7:09 am
Localisation : Paris
Contact :

Message par frederic han » mar. oct. 09, 2007 2:14 pm

super,
ca a l'air de marcher:
a part: le cas p^1 qui est traite comme p^2
0>> G:=GF(7,1,['a','G'])
GF(7,a^2-2*a-2,[a,G],undef)
3>> G:=GF(7,2,['a','G'])
GF(7,a^2-2*a-2,[a,G],undef)

d'autre part:
maple_mode(0);factor(x^2+x+1 mod 7)
ou
maple_mode(1);Factor(x^2+x+1) mod 7;

me donnent x^2+x+1 alors que 2 et -3 sont racines et qu'avant ca marchait.
20>> factor(x^2+x+1,G(a))
(x+G(-2))*(x+G(3)) est correct
mais pas
23>> factor(x^2+x+1,G(1))
x^2+x+1
autre ennuis:
26>> factor(x^4+1,exp(I*Pi/4))
(1-I)*(x^2+sqrt(2)*x+1)*(x^2+(-(sqrt(2)))*x+1)/(1-I)
(je suis en complex_mode:=0;) alors que c'est racine.
(NB maple aussi rale la:
> factor(x^4+1,exp(I*Pi/4));
Error, (in factor) 2nd argument, 1/2*2^(1/2)+1/2*I*2^(1/2), is not a valid
algebraic extension
)

D'un autre cote, avec cette version (Sqrt decoché)
0>> factor(x^2+x+1,I*sqrt(3))
(-I)*sqrt(3)*sqrt(3)*(2*sqrt(3)*x+sqrt(3)-3*I)*(2*sqrt(3)*x+sqrt(3)+3*I)/(-36*I)
n'est pas tres simplifie, mais correct

alors qu'avec une ancienne il ne fait rien.
Voilivoila
j'espere ne pas m'etre trop empatouille dans les maple_mode et sqrt... complex...

parisse
Messages : 5734
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Message par parisse » mar. oct. 09, 2007 2:52 pm

-> GF(p,n) commence par calculer le max de n et 2 donc GF(p,1)==GF(p,2)...

-> j'ai corrige le petit bug qui empechait de factoriser x^2+x+1 mod 7, je ne pouvais pas le voir car quand NTL est installe, c'est lui qui est appele.

-> factor(x^2+x+1,G(1)) ne fait rien parce qu'en fait je fais le produit du polynome par le second terme et c'est ca
que je factorise avant de diviser par ce
second terme. Et comme G(1)* renvoie x^2+x+1

-> il y a en effet encore quelques ameliorations a faire dans les factor sur des extension algebriques, mais je ne les
classe pas en prioritaire pour le moment...

frederic han
Messages : 1137
Inscription : dim. mai 20, 2007 7:09 am
Localisation : Paris
Contact :

Message par frederic han » mar. oct. 09, 2007 9:10 pm

OK, merci beaucoup,

ca a l'air de marcher. Pour le G(1) ou le n=1, j'avais juste essaye ca pour voir si ca permettait de contourner le probleme du molulo 7, donc maintenant ca n'est pas grave que ca ne donne rien.

a bientot

Frederic

parisse
Messages : 5734
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Message par parisse » mer. oct. 10, 2007 1:28 pm

bon, j'ai finalement un peu ameliore la resultat de la factorisation avec des extensions algebriques, au prix d'un certain nettoyage du code de factorisation, j'espere que tout marche normalement.

Répondre