Indicatrice d'euler, etc

[invitee17aeca5]

Salutations

Ne sachant pas vraiment oû poster ce genre de question (assez vague à vrai dire) je viens quérir votre aide à propos de l'indicatrice d'euler et de diverses joyeuseries à propos des nombres premiers.

Tout d'abord, il ne s'agit pas de questions scolaires, par conséquent, ne vous retenez pas, je n'utiliserai pas vos réponses pour éviter de réflechir...

Je m'intéresse, donc, aux nombres premiers. En parcourant un peu les articles sur le sujet, je suis tres vite tombé sur de grands mots, de grandes phrases assez répugnantes, comme "Algorithme d'Euclide étendu", "Arithmétique modulaire", "Théorème d'Euler", "Indicatrices d'euler"....
Et en cherchant des infos sur ces sujet, je n'ai trouvé que de grosses équations bizares et des termes étranges, voir meme d'autre théories - passionnante, je n'en doute pas - mais qui ne menent qu'a d'autres références... et, là, je me perdrait si je voulais tout savoir *-*

Bref, pourrirez vous me dire, avec de vrais mots, à quoi correspond "une indicatrice d'euler", "la théorie d'euler", "Algorithme d'Euclide étendu", "Arithmétique modulaire" ... ?

Je suis probablement assez vague, je ne souhaite guere plus que quelques pistes pour continuer mes investigations...

voilà, merci, ++ Tixlegeek
-----

[invitef1b93a42]

Bonjour,
L'indicatrice d'Euler souvent notée donne la quantité de nombres premiers avec n. Par exemple, . Cette fonction est très utilisée dans l'arithmétique de niveau asez élevé mais on peut l'aborder en Terminale. L'arithmétique modulaire est l'arithmétique qui est basée sur le reste dans la divisions euclidienne. On étend le reste de la division euclidienne, dès la Terminale, en congruences, qui se base sur les modules. C'est-à-dire deux entiers, on dit que a est congru à b modulo n si le reste dans la division euclidienne de a par n est le même que le reste de la division euclidienne de b par n. On note . Illustration : donc, dans la division euclidienne de 6 par 3, le reste est 0, ainsi . donc, . Toute l'arithmétique modulaire, comme son nom l'indique, traite des entiers par congruences et modules, tel ci-dessus. Enfin, l'algorithme d'Euclide est, lui aussi, basé sur les reste de division euclidienne. Cet algorithme consiste à enchaîner les divisions euclidiennes pour trouver le PGCD (plus grand diviseur commun.). On prend un nombre et un autre . On note le plus grand diviseur commun à n et à p, par exemple , . Voici en quoi consiste l'algorithme d'Euclide : on effectue la division euclidienne de n par p avec r le reste dans la division euclidienne de n par p (on a ) ; puis on fait la division euclidienne de p par r : avec ; ensuite la division euclidienne de r par r' : avec ainsi de suite, jusqu'à trouver un certain reste r=0, et alors avec r' le dernier reste dans les divisions euclidiennes successifs qui n'est pas égal à 0. Prenons un exemple, on veut calculer . On applique l'algorithme d'Euclide : , puis puis . Donc, 1 est le dernier reste dans les divisions euclidiennes successives qui n'est pas nul. Ainsi, . Voilà en quoi consiste l'algorithme d'Euclide. L'algorithme d'Euclide étendu s'applique pour calculer les coefficients de Bézout, qui est directement lié au théorème de Bézout très utilisé en arithmétique modulaire : deux entiers, si , alors il existe deux entiers u,v qui vérifient . On effectue l'algorithme d'Euclide sur a et b jusqu'à trouver le reste r=1. Ensuite, on fait le procédé inverse de l'algorithme d'Euclide, c'est-à-dire que, ayant trouvé suite à l'algorithme d'Euclide, , on transforme pour avoir . On fait ça en remontant les lignes de calcul que l'on avait faites pour trouver r=1 jusqu'à obtenir et donv U,V sont appelés coefficients de Bézout.

[invitee17aeca5]

Merci énormément, voilà qui m'éclaire déjà plus. Je suis rassuré, ca devait pas etre si compliqué que ca !

Et, pour faire une indicatrice d'euler, par exemple de 1 à ...64000... ou plus. Comment font les gens qui s'y connaissent? Je pense qu'on peut oublier les cribles, et que le PGCD n'est pas d'une aide formidable...

Je reviendrai poster de nouvelles questions d'ici peu. Merci bien

++ Tixlegeek

[invitee17aeca5]

Ha !

J'ai demandé quelques informations à mon proffesseur de mathématique qui, apparemment s'est pas mal intéressé au probleme, et, il m'a dit, si j'ai bien tout compris, que l'indicatrice d'euler n'était pas exacte... Qu'en dites vous ?

Sauriez vous comment savoir, dirrectement, si un nombre quelconque ets premier ?

merci, ++ Tix.

[A voir en vidéo sur Futura]

[invite4ef352d8]

L'indicatrice d'euleur vérifie certaine identité qui permette de la calculer plus facilement :

par exemple : si n=P1^a1 * P2^a2 *...*Pk^ak est la décomposition en facteur premier de n, alors Phi(n) =(1-1/P1)*..*(1-1/Pk)*n = (p1-1)*...*(pk-1) *p1^(a1-1)*...*pk^(ak-1)

mais calculer phi(n) est à peu pres aussi compliqué que de calculer la factorisation de n en nombre premier : en fait, dans beaucoup de cas c'est équivalent (typiquement, les grand nombres qu'on veut factoriser sont ceux utilisé dans la cryptographie et sont de la forme n=pq avec p et q des grand nombre premier, dans ce cas phi(n)=(p-1)(q-1), et donc connaitre n et Phi(n) donne deux equation à deux inconu pour déterminer p et q...)



pour savoir si un nombre n est premier ou non, il existe effectivement des algorithme efficace, dans le sens ou le temps de calcule dépend du nombre de chiffre n élevé à une certaine puissance (6 ou 7 je crois), et n'on pas de la valeur de n directement. mais ces algorithme sont peut-etre un peu trop compliqué pour ton niveaux actuelle (enfin, ceci dit, si tu es motivé, je t'encourage à regarder ! )
il y en à essentiellement deux :
-Miller / Rabin-Miller : d'un point de vue purement théorique il ne fait que dire si un nombre n'est pas premier, si il ne répond rien c'est que le nombre est "tres probablement premier" (sachant que la propabilité d'erreur peut-etre réduit exponentiellement à volonté et est vraiment tres faible) de plus si l'hyhpothèse de Riemann (la fameuse conjecture) est vrai, alors on en donner une version qui ne se trompe jammais.

- AKS pour Agrawal-Kayal-Saxena) lui ne se trompe jammais, mais est un peu plus lent que rabin-miller.

(en pratique, tous le monde utilise Rabin-Miller)

note que le si l'entier n est effectivement composé, il est en revanche beaucoup plus compliqué d'en donner une factorisation : pour ce problème il n'existe pas d'algoritme vraiment efficace, et c'est d'ailleur la dessus que repose toute la cryptographie moderne : il est facile de trouver des grand nombres premier grace à Rabin-Miller, de les multiplier, mais en revanche il est extremement compliqué de factoriser le nombre obtenu, dans l'algoritme de cryptage RSA : trouver deux nombres premier et les multiplier permet de générer une clée de codage, factoriser le nombre obtenu revient à caser la clée de codage (et donc décoder le message "sans autorisation" )

[invite4ef352d8]

tous ca pour dire : pour savoir si un nombre est premier on demande à un ordinateur et lui il sais répondre. pour factoriser un entier, si il est pas trop grand (... actuellement, moins d'une cinquantaine de chiffre je crois) on demande à un ordinateur qui répond en quelque seconde, et pour des nombres "un peu plus grand " (jusqu'à 200 ou 300 chiffre je crois) il faut un super calculateur de l'armé qui tourne pendant plusieur mois, et au dela ca devient impossible

PS : j'ai pas vérifier les chiffre que je donne, mais je pense que l'ordre de grandeur est correcte...

[invitee17aeca5]

Salut, merci beaucoup pour ta réponse !

Bien, à vrai dire, jusqu'à il y a assez peu, mes centres d'intérets étaient plus du genre équations paramétriques, et petites farces dans les reperes... J'ai un peu laissé tomber les nombres :/

Pourrais tu m'en dire plus sur la décomposition en plusieurs facteurs des nombres "intéressants" ? (je ne crois pas avoir réellement compris ce que ça implique)

voilà, merci encore !

++ Tix.

[invitee17aeca5]

salutations

bon, j'upp un petit coup pour voir

++