Discussion :

[je®ome]

Quelqu' un connaît-il un algo pour calculer ceci :

3*x^3-7*x^2+5*x+11 congru à 0 modulo 100

merci d'avance

[jobherzt]

a priori, la methode generale quand tu as un polynome a coefficient entier modulo N :

- tu factorise N = p1^a1 * p2^a2 .... avec p1.. pk des nombres premiers, et ai la puissance maximal avec laquelle pi apparait dans la decomposition. pour 100 ca te donne 2^2*5^2 .

- pour chacun des pi tu factorise ton polynome modulo pi grace a berlekamp, puis tu remontes la factorisation dans pi^ai grace au lemme d'hensel.

-enfin, grace au theoreme chinois tu en deduis les solutions modulo N.

[je®ome]

ok, jte remercie

jvais aller voir comment fonctionne berlekamp et le lemme de hensel

merci encore

[jobherzt]

je t'en prie :-)

berlekamp n'est pas trop compliqué, c'est du bidouillage sur des matrices, hensel est un peu plus hardcore, pas compliqué en soi, mais c'est une suite de theoreme avec des demos construtives, et ca peut etre un peu prise de tete de les convertir en algorithme...

[jobherzt]

jste pour etre sur : tu n'as donné ce polynome que comme exemple ? si tu n'en a vraiment qu'un a resoudre, fait le a la main, ou utilise un logiciel de calcul formel, genre pari-gp (libre et gratuit), ou maxima (idem).

[Zavonen]

Peut être n'ai je pas bien compris l'ennoncé.
Il existe un petit thm d'arithmétique qui dit :
Si P(n) est un polynôme à coeffs entiers et si p est un entier:
P(n)%p=(P(n%p))%p
x%y signifie ici reste de x dans la division par y (opérateur du C).
Donc si je cherche les solutions en x entier de l'équation proposée il suffit de trouver celles entre 0 et 99 (inclus)
Un petit programme trouve qu'il n'y en a aucune.

[jobherzt]

certes, mais la complexité de cette methode est enorme.. en travaillant modulo 100 c'est faisable, mais avec de plus grands entiers ca devient beaucoup plus bourrin.. meme si on ne connait pas encore d'algo vraiment efficace pour factorise un entier, ils sont quand meme beaucoup plus rapides qu'une recherche exhaustive. et derriere, surtout si N a de petits facteurs, berlekamp est tres efficace. pour des N vraiment tres grand, par contre, il n'y pas de methode miracle, mais en utilsant l'algorithme LLL on peut trouver les "petites" solutions de cette equation.