Corps finis

par **ortollj** » 21 Mar 2015, 08:53

Bonjour
dans le document d'Olivier Rioul "Corps finis", jusque ici tres clair et tres bien fait.
je bute sur le paragraphe 2.4. DESCRIPTION PRIMITIVE DE FQ.

http://perso.telecom-paristech.fr/~rioul/documents/201111CorpsFinis.pdf

Appelons donc un élément dordre maximal . On va montrer que
pour tout \alpha d'ordre , n divise m. Soit d =pgcd(m,n) le pgcd des ordres m et n.
On peut trouver m' (diviseur de m) et n' (diviseur de n) premiers entre eux tels
que m'n'=mn/d (le ppcm de m et n).

bon, alors allons y essayons avec

au hazard prenons

donc n=5 =

dans la table on voit que m=10 donc pas de probleme pour trouver m', on peut prendre 2 ou 5
mais patatra n' diviseur de n !! or n=5 , comment on fait ? :hum:

Code: Tout sélectionner: ci dessous la table des puissances de [TEX] \mathbb{F}_{11}[/TEX] , en horizontal les exposants et les [TEX] \alpha[/TEX] en verticale. . 0. 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 0. 1. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 2. 1. 2. 4. 8. 5. 10. 9. 7. 3. 6. 1. 3. 1. 3. 9. 5. 4. 1. 3. 9. 5. 4. 1. 4. 1. 4. 5. 9. 3. 1. 4. 5. 9. 3. 1. 5. 1. 5. 3. 4. 9. 1. 5. 3. 4. 9. 1. 6. 1. 6. 3. 7. 9. 10. 5. 8. 4. 2. 1. 7. 1. 7. 5. 2. 3. 10. 4. 6. 9. 8. 1. 8. 1. 8. 9. 6. 4. 10. 3. 2. 5. 7. 1. 9. 1. 9. 4. 3. 5. 1. 9. 4. 3. 5. 1. 10. 1. 10. 1. 10. 1. 10. 1. 10. 1. 10. 1. ci dessous la table des omega de [TEX] \mathbb{F}_{11}[/TEX] - 0. 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 1. 0. 1. 0. 0. 0. 0. 0. 0. 0. 0. 0. 2. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 10. 3. 0. 0. 0. 0. 0. 5. 0. 0. 0. 0. 0. 4. 0. 0. 0. 0. 0. 5. 0. 0. 0. 0. 0. 5. 0. 0. 0. 0. 0. 5. 0. 0. 0. 0. 0. 6. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 10. 7. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 10. 8. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 10. 9. 0. 0. 0. 0. 0. 5. 0. 0. 0. 0. 0. 10. 0. 0. 2. 0. 0. 0. 0. 0. 0. 0. 0.

ci dessous je rajoute le code Scilab pour obtenir les elements de

Code: Tout sélectionner: // debut matrices de corps finis p=11 ma = zeros(p+1,p+1); mm = zeros(p+1,p+1); mp = zeros(p+1,p+1); momega = zeros(p+1,p+1); for i = 1 : p+1 for j = 1 : p+1 if i==1 then ma(i,j)=j-2 ; mm(i,j)=j-2 ; mp(i,j)=j-2 ; momega(i,j)=j-2 ; end if j==1 then ma(i,j)=i-2 ; mm(i,j)=i-2 ; mp(i,j)=i-2 ; momega(i,j)=i-2 ; end end end for i = 2 : p+1 for j = 2 : p+1 mm(i,j)=modulo((ma(i,1)*ma(j,1)),p) ; ma(i,j)=modulo((ma(i,1)+ma(j,1)),p) ; mp(i,j)=modulo((ma(i,1)^ma(j,1)),p) ; end end fa=figure(0); clf(fa); //fa=gcf();//figure courante fa.figure_name = "Figure n°%d" + " Table Addition dans F" + string(p); fa.color_map=cmap; xmin=0;xmax=p-1;xnumber=xmax-xmin; ymin=0;ymax=p-1;ynumber=ymax-ymin; y=linspace(ymin,ymax,ynumber); x=linspace(xmin,xmax,xnumber); plot3d1(x,y,ma(x+2,y+2),theta=45,alpha=45); cmap=hotcolormap(64); //xtitle ( "addition in field " + string(p) , "X elements " , "Y elements" ); fm=figure(1); clf(fm); //fm=gcf();//figure courante fm.figure_name = "Figure n°%d" + " Table multiplication dans F" + string(p); fm.color_map=cmap; xmin=0;xmax=p-1;xnumber=xmax-xmin; ymin=0;ymax=p-1;ynumber=ymax-ymin; y=linspace(ymin,ymax,ynumber); x=linspace(xmin,xmax,xnumber); plot3d1(x,y,mm(x+2,y+2),theta=45,alpha=45); cmap=hotcolormap(64); //xtitle ( "multiplication in field " + string(p) , "X elements " , "Y elements" ); //uicontrol(fm, "style", "text", "string", "This is a figure","position", [50 70 100 100], "fontsize",15); fp=figure(2); fp.figure_name = "Figure n°%d" + " Elements a la puissance dans F" + string(p); clf(fp); //fp=gcf();//figure courante fp.color_map=cmap; xmin=0;xmax=p-1;xnumber=xmax-xmin; ymin=0;ymax=p-1;ynumber=ymax-ymin; y=linspace(ymin,ymax,ynumber); x=linspace(xmin,xmax,xnumber); plot3d1(x,y,mp(x+2,y+2),theta=45,alpha=45); cmap=hotcolormap(64); //xtitle ( "elements a la puissance " + string(p) , "X elements " , "Y elements" ); for i = 3 : p+1 for j = 3 : p+1 if mp(i,j)==1 momega(i,j)=mp(1,j); break; end end end

par **ortollj** » 21 Mar 2015, 15:16

Appelons donc un élément dordre maximal. On va montrer que
pour tout d'ordre , n divise m. Soit d =pgcd(m,n) le pgcd des ordres m et n.
On peut trouver m' (diviseur de m) et n' (diviseur de n) premiers entre eux tels
que m'n'=mn/d (le ppcm de m et n).

Ooops :marteau: je viens juste de penser a un truc !, comme ca n'est pas precisé, est ce que les calculs ci dessus doivent etre faits dans

ou dans

?

par **Skullkid** » 23 Mar 2015, 12:04

Bonjour, on peut renverser ta question : peux-tu donner un sens au pgcd ou à la division euclidienne sur un corps fini ? L'ordre d'un élément est défini comme étant un entier, donc les calculs se font en effet chez les entiers.

Pour ton exemple n = 5 et m = 10, on peut prendre m' = 2 et n' = 5 ou m' = 10 et n' = 1.

par **ortollj** » 24 Mar 2015, 20:18

Skullkid a écrit:Bonjour, on peut renverser ta question : peux-tu donner un sens au pgcd ou à la division euclidienne sur un corps fini ? L'ordre d'un élément est défini comme étant un entier, donc les calculs se font en effet chez les entiers.

Pour ton exemple n = 5 et m = 10, on peut prendre m' = 2 et n' = 5 ou m' = 10 et n' = 1.

ok merci Skulkid
je pensais (benoitement) que quand on disait diviseur de x implicitement c'etait differend de x et de 1 ! :hum:

m'=1 n'=5 m'*n'=5

m'=2 n'=1 m'*n'=2

m'=2 n'=5 m'*n'=10

m'=5 n'=1 m'*n'=5

m'=5 n'=5 m'*n'=25

m'=10 n'=1 m'*n'=10

m'=10 n'=5 m'*n'=50

pgcd(m,n)=pgcd(10,5)=5

comme m'n'=ppcm(m,n)=m*n/pgcd(m,n)=10

ou m'=10 n'=1
alors

9^5=1 ! => 1^1,1^2,1^3,1^4 d'ordre 1

donc il reste m'=2 n'=5
alors

9^1=9, 9^2=4, 9^3=3, 9^4=5 sont d'ordre 5

dans notre cas

peut prendre les valeurs 2,6,7 ou 8

avec les

2^5=10 ou 6^5=10 ou 7^5=10 ou 8^5=10 qui sont effectivement d'ordre m'=2
ca a l'air de coller.

par **Ben314** » 25 Mar 2015, 16:54

Salut,
Le fond du problème, c'est que le truc affirmé dans l'article comme si c'était "une évidence", à savoir que, si m et n sont deux entiers naturels et d=pgcd(m,n) alors il existe m' et n' tels que m'|m ; n'|n et dm'n'=mn , ben ce truc là.... c'est tout sauf une évidence...
Soit il a proprement prouvé ce résultat dans les parties précédentes de l'article (que j'ai la flemme de lire), soit son truc est vraiment pas sérieux.

par **ortollj** » 27 Mar 2015, 06:14

Ben314 a écrit:Salut,
Le fond du problème, c'est que le truc affirmé dans l'article comme si c'était "une évidence", à savoir que, si m et n sont deux entiers naturels et d=pgcd(m,n) alors il existe m' et n' tels que m'|m ; n'|n et dm'n'=mn , ben ce truc là.... c'est tout sauf une évidence...
Soit il a proprement prouvé ce résultat dans les parties précédentes de l'article (que j'ai la flemme de lire), soit son truc est vraiment pas sérieux.

d'au temps plus, que ca n'a pas l'air vrai, sauf erreur (possible, pas encore a l'aise avec Scilab :crash: ) dans le code ci dessous.

Code: Tout sélectionner: sizem=10; m=grand(sizem,sizem,'uin',1,10000); n=grand(sizem,sizem,'uin',1,10000); count=0 countold=0 fd_w = mopen('outfile.txt', 'wt'); for i = 1 : sizem for j = 1 : sizem [d,U] = gcd([m(i,j) n(i,j)]); fm=factor(m(i,j));fn=factor(n(i,j)); // add 1 and m (1 and m are also divider of m !) // remark:in case of primary number m is added twice but don'tcare ! fm=[1,fm];fm=[m(i,j),fm];fn=[ 1 ,fn];fn=[n(i,j),fn]; // disp( "fm:", fm ," fn:", fn); mnDivByd=m(i,j)*n(i,j)/d ; for k = 1 : length(fm) for l = 1 : length(fn) if modulo(m(i,j),fm(k))==0 & modulo(n(i,j),fn(l))==0 then // m'|m et n'|n if fn(l)*fm(k)==mnDivByd then // here m'*n'=m*n/d ; count=count+1; mfprintf(fd_w,'m:%d n:%d d:%d mnDivByd:%d m'':%d n'':%d count:%d \n',m(i,j),n(i,j),d,mnDivByd,fm(k),fn(l),count); break; // m' and n' has been found, stop research end end end end // here no m' n' were found if countold==count then mfprintf(fd_w,'NOT FOUND ! m:%d n:%d d:%d mnDivByd:%d count:%d \n',m(i,j),n(i,j),d,mnDivByd,count); end countold=count; end end mclose(fd_w);

par **Doraki** » 27 Mar 2015, 07:00

Si tu définis f(x,y) = x si x>y, 0 sinon ; et g(x,y) = y si y>=x, 0 sinon,
Tu peux prendre m'= produit des p^f(vp(m),vp(n)) et n' = produit des p^g(vp(m),vp(n))

par **ortollj** » 27 Mar 2015, 18:32

Bonjour Doraki
mes trois neurones sont maintenant saturés :stupid:

STP est ce que tu pourrais etre plus explicite, pour

p^f( vp(m),vp(n) )

c'est quoi p , le nombre premier du corps ? et vp() c'est quoi ?.

par **Ben314** » 28 Mar 2015, 01:22

V_p, c'est la valuation p-adique : Si n est un entier naturel non nl, V_p(n) c'est l'exposant de p dans la décomposition en facteurs premiers de n.
Et le p dont il parle n'a rien a voir avec le p du corps en question vu qu'il fait le produit sur tout les p premiers (c'est donc une variable muette).

Dit de façon plus élémentaire, si

et

, alors, il suffit de prendre

et

avec

pour avoir

,

et

par **ortollj** » 28 Mar 2015, 08:45

Ben314 a écrit:V_p, c'est la valuation p-adique : Si n est un entier naturel non nl, V_p(n) c'est l'exposant de p dans la décomposition en facteurs premiers de n.
Et le p dont il parle n'a rien a voir avec le p du corps en question vu qu'il fait le produit sur tout les p premiers (c'est donc une variable muette).

Dit de façon plus élémentaire, si et , alors, il suffit de prendre et avec pour avoir
, et

ok merci Doraki et Ben314 ! je me trompais, quand je disais not found
je m'etais encore betement limité a un seul des facteurs !! :triste:

NOT FOUND ! m:54 n:44 pgcd(m,n)=2 mn/d=1188
m' : 54 1 2 3 3 3
n' : 44 1 2 2 11

en fait je peux avoir par exemple m'=3^3 * 2 et n'=2*11

Oh la la, je pars me cacher :hum:
enfin plutôt n'=2^2 *11 et m'=3^3 (m' et n' si on les veut premier entre eux !)

par **ortollj** » 08 Avr 2015, 18:53

Bonjour
En fait pour demontrer que l'ordre d'un element est forcement inferieur ou egale a q-1 ( q le nombre premier du corps)
je viens de m'apercevoir que ca coule de source avec le Petit theoreme de Fermat.

par contre au risque de passer pour un affreux pinailleur.

Appelons donc un élément dordre maximal. On va montrer que
pour tout d'ordre , n divise m. Soit d =pgcd(m,n) le pgcd des ordres m et n.
On peut trouver m' (diviseur de m) et n' (diviseur de n) premiers entre eux tels
que m'n'=mn/d (le ppcm de m et n).

Lélément est alors clairement
dordre n'. En effet, puisque est dordre n, les n' puissances ,
k = 1, ... ,n'- 1, sont 1 et

example pour le corps 17 avec m:16 n:8 d:8 mnDivByd:16
diviseurs de m : 1 2 2 2 2 16 ; diviseurs de n : 1 2 2 2 8
m':16 n':1
les n' puissances

k = 1, ... ,n'- 1, sont de 1 ?????
ca n'est pas le cas avec k=1,

ci dessous la table des puissances pour F_17

Code: Tout sélectionner: - 1. 0. 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 0. 1. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 2. 1. 2. 4. 8. 16. 15. 13. 9. 1. 2. 4. 8. 16. 15. 13. 9. 1. 3. 1. 3. 9. 10. 13. 5. 15. 11. 16. 14. 8. 7. 4. 12. 2. 6. 1. 4. 1. 4. 16. 13. 1. 4. 16. 13. 1. 4. 16. 13. 1. 4. 16. 13. 1. 5. 1. 5. 8. 6. 13. 14. 2. 10. 16. 12. 9. 11. 4. 3. 15. 7. 1. 6. 1. 6. 2. 12. 4. 7. 8. 14. 16. 11. 15. 5. 13. 10. 9. 3. 1. 7. 1. 7. 15. 3. 4. 11. 9. 12. 16. 10. 2. 14. 13. 6. 8. 5. 1. 8. 1. 8. 13. 2. 16. 9. 4. 15. 1. 8. 13. 2. 16. 9. 4. 15. 1. 9. 1. 9. 13. 15. 16. 8. 4. 2. 1. 9. 13. 15. 16. 8. 4. 2. 1. 10. 1. 10. 15. 14. 4. 6. 9. 5. 16. 7. 2. 3. 13. 11. 8. 12. 1. 11. 1. 11. 2. 5. 4. 10. 8. 3. 16. 6. 15. 12. 13. 7. 9. 14. 1. 12. 1. 12. 8. 11. 13. 3. 2. 7. 16. 5. 9. 6. 4. 14. 15. 10. 1. 13. 1. 13. 16. 4. 1. 13. 16. 4. 1. 13. 16. 4. 1. 13. 16. 4. 1. 14. 1. 14. 9. 7. 13. 12. 15. 6. 16. 3. 8. 10. 4. 5. 2. 11. 1. 15. 1. 15. 4. 9. 16. 2. 13. 8. 1. 15. 4. 9. 16. 2. 13. 8. 1. 16. 1. 16. 1. 16. 1. 16. 1. 16. 1. 16. 1. 16. 1. 16. 1. 16. 1.

par **Skullkid** » 08 Avr 2015, 21:18

ortollj a écrit:Bonjour
En fait pour demontrer que l'ordre d'un element est forcement inferieur ou egale a q-1 ( q le nombre premier du corps)
je viens de m'apercevoir que ca coule de source avec le Petit theoreme de Fermat.

Dans le poly, q n'est pas forcément un nombre premier, c'est le cardinal du corps. Le poly dit juste "je ne peux pas trouver plus de q-1 éléments distincts parmi les q-1 éléments non nuls du corps". Le petit théorème de Fermat parle d'un a entier et d'un q premier. Même dans le cas où q est effectivement premier et où on peut facilement identifier les éléments du corps à des entiers, Fermat me semble être de l'artillerie lourde par rapport à l'argument du poly.

Pour ta seconde remarque, ouais on peut considérer ça comme du pinaillage puisque le cas n' = 1 est trivial (si n est l'ordre de a, a^n = 1 est évidemment d'ordre 1) et l'utilisation d'une notation telle que "k = 1, ... , n'-1" sous-entend que l'ensemble décrit par k est vide si n' = 1.

par **ortollj** » 09 Avr 2015, 03:26

Je m'apercois que finalement j'ai loupé mon epoque et ma vocation.
j'aurais du etre fonctionnaire tatillon dans le regime Sovietique,
afin de pouvoir passer mes journées a pinailler pour ralentir les procedures !. :bad2:

Corps finis

Corps finis

Qui est en ligne