factor et GF
Modérateur : xcasadmin
-
- Messages : 1137
- Inscription : dim. mai 20, 2007 7:09 am
- Localisation : Paris
- Contact :
factor et GF
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.
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.
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.
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.
-
- Messages : 1137
- Inscription : dim. mai 20, 2007 7:09 am
- Localisation : Paris
- Contact :
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
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
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.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
-
- Messages : 1137
- Inscription : dim. mai 20, 2007 7:09 am
- Localisation : Paris
- Contact :
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...
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...
-> 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...
-> 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...
-
- Messages : 1137
- Inscription : dim. mai 20, 2007 7:09 am
- Localisation : Paris
- Contact :