[PDF] METHODES DE FACTORISATION PAR CRIBLE La m ethode de Fermat

Les méthodes de factorisation - LMRL

Les trois méthodes de factorisation qu’il faut connaître sont : la mise en évidence, les produits (identités) remarquables et le groupement de termes A La mise en évidence Rappelons la propriété de distributivité de la multiplication par rapport à l’addition et à la soustraction : a b c ab ac⋅ + = ⋅ + ⋅( )

Méthodes de factorisation des équations aux dérivées partielles

émanant des établissements d’enseignement et de recherche français ou étrangers, des laboratoires publics ou privés Méthodes de factorisation des équations aux dérivées partielles Isabelle Champagne To cite this version: Isabelle Champagne Méthodes de factorisation des équations aux dérivées partielles Equations aux

Chapitre VI - M ethodes de factorisation

Chapitre VI - M ethodes de factorisation Le probl eme de la factorisation des grands entiers est a priori tr es di cile L’e cacit e de nombreux cryptosyst emes, comme RSA, est bas e sur cette di cult e pr esum ee Le probl eme de d ecider si un entier est premier ou non, est en fait beaucoup plus simple que celui de trouver les diviseurs

La factorisation - MATHS

Le trinôme de la forme ax 2 + bx + c Pour faire la factorisation d’un trinôme de la forme ax 2 + bx +c , il faut trouver 2 nombres tel que le produit des 2 nombres égal a*c et que la somme des 2 nombres égale b Par la suite, on change b par les 2 nombres trouvés et on fait la double mise en évidence

METHODES DE FACTORISATION PAR CRIBLE La m ethode de Fermat

METHODES DE FACTORISATION PAR CRIBLE Ce texte est une introduction aux algorithmes de factorisation par crible 1 La m ethode de Fermat Fermat a remarqu e que pour trouver un facteur non-trivial d’un entier nil su t de l’ ecrire comme di erence de deux carr es En e et si n= x2 y2 alors n= (x y)(x+ y)

Méthodes informées de factorisation matricielle non-négative

Docteur de l’Universit´e du Littoral Cˆote d’Opale (Discipline : G´enie Logiciel, Automatique et Traitement du Signal) par AbdelhakimLIMEM Titre : M´ethodes inform´ees de factorisation matricielle non-n´egative Application `a l’identification de sources de particules industrielles Composition du jury Rapporteurs: Christian Jutten

Déplacement et méthodes rapides de factorisation des matrices

de la matrice A La factorisation 'an donc asp esoinb d'être alculécere ourp des systèmes qui ont la même matrice A, mais dont le seondc membre di ère Ce faisant, on gagne à la fois en e ort de alculc et en e ort de stockage arc la factorisation est stockée la où se trouve A

La factorisation de polynˆomes

est une factorisation de x2 +7x+ 1 2 • La technique de compl´etion du carr´e exige initialement un peu de pratique; mais apr`es l’avoirappliqu´ee correctement cinq ou six fois elle devient naturelle pour tout ´etudiant muni d’un peu de d´etermination Le truc, c’est de ne pas avoir peur et, face a` un

METHODES NUMERIQUES - UNIGE

– Les erreurs de troncature ou de discr´etisation qui proviennent de simplifications du mod`ele math´ematique comme par exemple le remplacement d’une d´eriv´ee par une diff´erence finie, le d´eveloppement en s´erie de Taylor limit´e, etc – Les erreurs d’arrondi qui proviennent du fait qu’il n’est pas possible de repr

[PDF] factorisation méthode horner

[PDF] factorisation mise en évidence

[PDF] question de débat sur la mondialisation

[PDF] fmi

[PDF] qrpg mercatique

[PDF] sujet qooq mercatique

[PDF] corrigé qooq stmg

[PDF] krampouz mercatique

[PDF] mercatique annales bac

[PDF] la démarche mercatique cours

[PDF] démarche mercatique définition

[PDF] factoriser forme canonique en ligne

[PDF] démarche mercatique exemple

[PDF] démarche mercatique schéma

[PDF] factoriser forme développée

M

ETHODES DE FACTORISATION PAR CRIBLE

Ce texte est une introduction aux algorithmes de factorisation par crible.

1.La methode de Fermat

Fermat a remarque que pour trouver un facteur non-trivial d'un entiernil sut de l'ecrire comme dierence de deux carres. En eet sin=x2y2alors n= (xy)(x+y). Par exemple pour factorisern= 1524157896661027288525081 on ajoute an les carres successifs 1, 4, 9, ...et on regarde si la somme obtenue est un carre. gp > n=1524157896661027288525081 %1 = 1524157896661027288525081 gp > for(k=1,20,if(issquare(n+k^2),print([k,sqrt(n+k^2)]))) [12, 1234567898765.000000000000000] Doncn=122+ 12345678987652= 12345678987531234567898777. Cette methode ne fonctionne que si l'un des deux carres est petit. Dans ce cas, on peut penser que l'autre carre est tres proche depn. On peut donc aussi bien calculer l'entierrimmediatement superieur apnet voir sir2nest aussi un carre. gp > round(sqrt(n))^2-n %2 = 144 Si l'on parvient a ecrire un multiple dencomme dierence de deux carres, on peut encore esperer trouver un facteur non trivial den. En eet, six2=y2modn on peut esperer que le pgcd denetxyest non-trivial. On peut donc appliquer les calculs precedents aux premiers multiples den. Cette methode ne reussit que pour desnparticuliers, mais elle est ecace pour de petitsn. Dans le cas general, pour trouver des solutions non triviales a la congruence x

2y2= 0 modn

on ne sait pas faire mieux que de chercher des congruences entre nombres friables a un carre pres, c'est-a-dire des congruences de la formeY ip i=x2modn ouxest un entier quelconque et lespisont des nombres premiers plus petits qu'une borneBdonnee. Une fois collectees de nombreuses relations telles que celle ci-dessus, on peut, par elimination lineaire, obtenir une congruence entre deux carres. Dans les deux sections suivantes nous presentons deux algorithmes de ce type. 1 2 M

ETHODES DE FACTORISATION PAR CRIBLE

2.Le crible lineaire de Dixon

On choisit un residuxmodulonau hasard et on calculey, le reste de la division euclidienne dex2parn. On a doncx2=ymodn. On espere queyestB-friable. Si tel est le cas, on obtient une congruence entre un carre et un nombreB-friable. On collecte susamment de telles relations et on termine selon le principe general expose ci-dessus. Par exemple supposons que l'on veuille factorisern= 7081. On choisitB= 3. Les nombresB-friables sont les entiers de la forme2a3b.

Apres quelques t^atonnements on trouve

4486

2=2:3 modn;

1857

2= 2 modn;

2645

2=3 modn:

On associe a ces trois congruences la matrice 33 a coecients dansF2suivante1 2 344861 1 1

18570 1 0

26451 0 1

On verie que la ligne [1;1;1]2F32est annulee par la matrice. On en deduit la congruence entre les deux carres (4486:1857:2645)2= (2:3)2modn: Le pgcd denet 4486:1857:2645 + 6 est 73. On a donc trouve un facteur non- trivial.

3.Le crible quadratique

Cet algorithme est d^u a Carl Pomerance. Nous nous contentons de l'illustrer sur un exemple. Soit n= 21311 = 101:211 le nombre a factoriser. On choisit un entiermproche de la racine carree den m=bn1=2e= 146: On forme des congruences modulonen observant que pour tout entiera, (m+a)2(m2n) +a2+ 2am(modn) = 5 +a2+ 292a(mod 21311); ou l'on note quem2nest de l'ordre depn. M

ETHODES DE FACTORISATION PAR CRIBLE 3

On se donne une borneB= 13 et l'on cherche de petits entiersatels que

5 +a2+ 292asoitB-friable. Par exemple pouracompris entre60 et 60 on

trouve a5 + 292a+a2272:52:11:13

52:5:11:13

12:11:13

05 605
3:132 On porte dans une matrice la parite des valuations :1 2 5 11 13271 1 0 1 1

51 1 1 1 1

11 1 0 1 1

00 0 1 0 0

600 0 1 0 0

On forme des carres a partir des lignes annulees par cette matrice. L'ensemble de ces lignes est un espace vectoriel dont une base est donnee par les trois lignes de la matrice suivante

2751 0 601 0 1 0 0

1 1 0 1 0

1 1 0 0 1

La premiere ligne du tableau donne la congruence

(2:5:11:13)2(14627)2:(1461)2(mod 21311): On calcule alors le plus grand diviseur commun de 2:5:11:13(14627):(146

1) =15825 et de 21311. On trouve le facteur non trivialp= 211 den= 21311 et

son cofacteur 101. Un test de primalite prouve aisement quepetqsont premiers. En quoi cet algorithme est il meilleur que celui de Dixon? La seule dierence reside dans la maniere de trouver des relations de congruences. Dans le crible de Dixon, le residu dex2modulonest un entier aleatoire entre 1 etn1. On espere que cet entier est friable. Dans le crible quadratique le nombre suppose friable est de l'ordre depn. La probabilite de succes est donc bien plus grande. 4 M

ETHODES DE FACTORISATION PAR CRIBLE

4.Le crible algebrique, presentation generale

Le crible algebrique est un algorithme invente par Pollard et Lenstra. Les frontieres de cet algorithme ne sont pas nettes. De nombreuses variantes existent pour chacune des etapes qui le constituent. Nous donnons une presentation aussi generale que possible de cet algorithme. Nous donnons un exemple dans la section suivante. On appelle toujoursnl'entier a factoriser etmun entier auxiliaire qu'il convien- dra de preciser plus tard. Pour tout corps de nombresKon noteOKson anneau des entiers etK(n) l'anneau local ennc'est-a-dire l'ensemble des elements deKdont le denominateur est premier an. Soientfi(X) pour 1iIdes polyn^omes irreductibles unitaires a coecients entiers et de discriminants premiers an. On suppose aussi quefi(m) =n. Cette derniere condition se traduit algebriquement par l'egalite de tous les ideaux (X m;f i(X)) et de (Xm;n) dansQ(n)[X]. AppelonsKi=Q[X]=fi(X) le corps de nombres associe afi. L'egalite entre ideaux ci-dessus implique la commutativite du diagramme suivant pour tout couple (i;j) d'entiers compris entre 1 etI. Q (n)[X] i zz j $$K i;(n) i$$K j;(n) jzzZ=nZ Les echesisont des quotients par les polyn^omesfiet lesisont des substi- tutions deXparm. Voici comment le crible algebrique utilise le diagramme ci-dessus. Observons d'abord que les trois etages du diagramme sont de natures arithmetiques tres dierentes. DansQ[X], la plupart des elements sont irreductibles et tres peu sont inver- sibles. DansZ=nZc'est l'inverse. Il y a une majorite d'elements inversibles et tres peu d'elements irreductibles puisqu'ils correspondent aux facteurs den. Les corpsKisont les seuls ^etres intermediaires que l'on puisse intercaler entre les deux precedents. Prenons maintenant un elementA(X) deZ[X]. Pour touti, on dit que i(A) =A(X) modfi(X) est friable s'il se factorise dans le groupe multiplicatifKien M

ETHODES DE FACTORISATION PAR CRIBLE 5

A(X) modfi(X) =Y

k pei;k i;k ou lespi;ksont une base de friabilite, c'est-a-dire un systeme de generateurs d'un sous-groupe deKique l'on noteKi;s. On choisit en general le groupe forme des elements dont la norme est un rationnelB-friable, c'est-a-dire divisible unique-

ment par des nombres premiers plus petits queB. SiOKiest principal, lespi;kpeuvent ^etre des generateurs de petits ideaux premiers et des unites fondamen-

tales. On a alors, i(i(A(X))) =A(m) (modn) =Y k i(pi;k)ei;k Sii(A) etj(A) sont friables on obtient une congruence modulon

A(m) (modn) =Y

k i(pi;k)ei;k=Y k j(pj;k)ej;k; soit encore Y k i(pi;k)ei;kY k j(pj;k)ej;k= 1 (modn): On se xe une base de friabilite dans chacun des corpsKi. Si pour un polyn^ome Adonne et deux entiersi6=j,i(A(X)) etj(A(X)) sont friables on obtient une congruence utile comme ci-dessus. Lorsque le nombre de ces congruences excede le cardinal de la reunion de toutes les bases de friabilite, on obtient une congruence entre 2 carres modulonet donc une chance de factorisernpour chaque relation excedentaire. En general, lesOKine sont pas factoriels, aussi on adopte un point de vue dual. On sait queKi;sest un groupe de type ni engendre par a peu pres(B) generateurs. Ces generateurs ne sont pas canoniques et on ne sait pas les calcu- ler. En revanche on sait que le groupe des elements friables modulo les carres K i;s=(Ki;s)2est un groupe commutatif d'exposant deux et de type ni, donc un espace vectoriel surZ=2Zde dimension voisine de(B). On associe a chaque ideal la valuation associee ou plut^ot le residu modulo deux de cette valuation. On obtient ainsi un certain nombre de formes lineaires deKi;s=(Ki;s)2a valeurs dans Z=2Z. On ajoute a ces formes quelques caracteres construits a partir de residus quadratiques. Ces derniers, en nombre susant, servent a tuer l'obstruction pro- venant du groupe de classe et du groupe des unites. On suppose que la collection des valuations et des caracteres engendre le dual deKi;s=(Ki;s)2. Autrement dit, si toutes ces valuations et caracteres s'annulent en un nombrea2Ki;s, alors ce nombre est un carre. Une relation elementaire est alors denie par un polyn^omeA(X) et deux en- tiersietjtels quei(X) etj(X) soient friables chacun dans son corps. Une combinaison de relations est caracterisee par deuxI-uplets (Gi)1iIet (Di)1iI 6 M

ETHODES DE FACTORISATION PAR CRIBLE

ou chaqueGi2Kiest le produit de tous les membres de gauche des relations elementaires du type (i;) etDj2Kjest le produit de tous les membres de droite des relations elementaires du type (;j). En tenant compte des valeurs prises par les valuations et les caracteres, on obtient des combinaisons telles que tous lesGi=Di=Cisoient des carres dansKi. Chacune de ces relations donne une congruence entre carres modulon. Pour cela, il reste a calculer les racines carreesRitelles queR2i=Ci. C'est un probleme en soi que nous n'aborderons pas ici. La relation s'ecrit Y i i(Ri))2= 1 (modn): Remarque: En general, on choisit une unique polyn^omeftel quef(m) =net on denit le corps de nombreK=Q[X]=fet les quatre morphismesalg:K(n)! Z=nZ,rat:Q(n):!Z=nZ,rat:Q(n)[X]!Q(n), etalg:Q(n)[X]!K(n) parrat(n) = 0,alg(Xmodf) =m,rat(X) =m,alg(X) =Xmodf. Ces applications forment un diagramme commutatif, algalg=ratrat:

5.Un exemple de crible algebrique general

Soit toujours

n= 21311 = 101:211 le nombre a factoriser. Posons m=bn1=2e= 146 et ecrivonsnen basem n= 14625 =f(n) avec f(X) =X25: Le polyn^omef(X) etant irreductible, on denit le corps de nombres

K=Q[X]=f(X)

qui est un corps quadratique reel. Doncd= 2. On se donne une borne de friabilite B= 20 et on dit un nombre premier petit s'il est inferieur aB. On noteOl'anneau

Z[X]=f(X).

Venons en maintenant a la determination de la base de friabilite. Elle se com- pose d'une base algebrique et d'une base rationnelle. La base rationnelle comprend

1, c'est a dire le signe et les nombres premiers inferieurs aB= 20 soit

M

ETHODES DE FACTORISATION PAR CRIBLE 7

B rat=f1;2;3;5;7;11;13;17;19g: Pour construire la base algebrique on factorise les nombres premierspentre

2 et 19 dans l'anneauO. On ne s'interesse qu'aux facteurs de degre residuel 1.

Pour les trouver, on cherche les racines def(X) modulop.A chaque racinec on associe l'ideal premier (p;Xc) deO, que l'on note aussipc. Plut^ot que ces ideaux, ce sont les valuations associees qui nous seront utiles. Nous considerons ces valuations modulo 2. On ajoute deux caracteres a la base ainsi obtenue. Dans notre cas nous choisi- rons les deux caracteres a l'inni c'est a dire les deux fonctions1et2denies par

1(a+bX) =signe(a+bp5);

et

2(a+bX) =signe(abp5):

On trouve donc la base

B alg=f1;2;21;50;117;114;199;1910g:

A tout elementa+bXdeOon associe sa norme

N(a+bX) =N(a;b) =f(a=b)bd:

Soitp3 un nombre premier. Pouraetbpremiers entre eux, on sait que a+bXa un facteur commun avecpsi et seulement siN(a;b) est divisible parp.quotesdbs_dbs5.pdfusesText_10