Programmation niveau supérieur

[musyk]

Sans & il calcul 5^10 puis le modulo 3, c'est à dire 5^10 = 9765625 modulo 3 = 1.

Avec il &, il calcul modulo par modulo, cad :

5^1 = 5 modulo 3 = 2
puis 2*5 = 10 modulo 3 = 1
puis 5*1 = 5 modulo 3 = 2 etc ... et on obtient aussi 5&^10 mod 3 = 1.

[musyk]

Les tests précédents utilisent une condition nécessaire mais non suffisante. Ainsi, il existe des entiers p non premiers tel que pour tout a compris entre un et p - 1, a p - 1 est toujours congru à un modulo p. Le nombre 1729 est un exemple. De tels nombres sont appelés nombre de Carmichaël.

Les tests indiqués au paragraphe précédent sont tous statistiques, au sens ou il existe toujours une probabilité, parfois très faible pour le nombre ayant passé le test ne soit néanmoins pas premiers. Ces nombres sont appelés pseudopremiers et sont attachés à des tests particuliers.

Xklr_65 :



En effet, 1729/13 = 133 ...........

[erd]

OK. Alors maintenant, nouvelle question : comment générer des nombres de Carmichael. Y en a-t-il beaucoup ? Donnez en les premiers ? Avez-vous un algorithme pour tester si un entier est de Carmichael ?

[Xklr_65]

Théorème (Korselt 1899) : Un entier positif composé n est un nombre de Carmichaël si et seulement n est sans carré et, pour chaque diviseur premier p de n, p − 1 divise n − 1.

Il découle de ce théorème que tous les nombres de Carmichaël sont des produits d'au moins trois nombres premiers impairs différents.

Liste des premiers nombres de Carmichaël ayant moins de 13 chiffres

[erd]

Je repose ma question : comment tester/générer un nombre de Carmichael. (procédure C ou Maple)

[musyk]

Il y avait plusieurs questions

Y en a-t-il beaucoup ? Donnez en les premiers ?

Les autres questions demandent un peu plus de temps ...

[musyk]

Ne comprenant que vaguement ces nombres, j'ai surfé sur le net à la recherche d'une explication pour trouver le fil conducteur de la procédure.

Je suis tombée sur <a href="http://www.math.jussieu.fr/~keller/capes/capes03-2.pdf">ce site</a>.

Au IV, il y a un exercice qui amène à comprendre la caractérisation de ces nombres ... Donc à mon sens intéressant à faire avant de se lancer dans l'écriture du programme ... je dis bien à mon sens ...

[musyk]

L’objet de cette partie est la caractérisation de certains nombres, appelés nombres de Carmichaël.
On rappelle que pour tout entier naturel premier p, et tout a entier premier avec p, ap−1  1 mod p.
La réciproque n’est pas vraie ; un nombre n est appelé nombre de Carmichaël si :
a) n n’est pas premier
b) pour tout nombre a premier avec n, an−1 est congru à 1 modulo n.
1. Montrer que si n = p1 × p2 × .... × pk où p1, p2, ...., pk sont des nombres premiers deux à deux distincts tels que (pi − 1)
divise (n − 1) pour tout i de {1, 2, ..., k}, alors n est un nombre de Carmichaël.
Montrer en particulier que 561, 10585 sont des nombres de Carmichaël.

Bon alors déjà petite remarque : deux entiers sont premiers entre eux s'ils n'ont aucun entier (autre que 1) en commun. (Elle ne vaut peut être que pour moi, mais bon ) Et on trouve ça avec <a href="http://fr.wikipedia.org/wiki/Identit%C3%A9_de_B%C3%A9zout">l'identité de Bézout</a>

1.

Idée :
- si n est un nombre de Carmichaël, alors il n'est pas premier.
- théorème de Fermat (qui dit que si p est un nombre premier et a un entier naturel non divisible par p, alors[tex]{a}^{p-1}\equiv 1 (mod p) [/tex])

[erd]

Bon. Ca avance dans la bonne direction.

Une première idée très très naïve pourrait consister à dire : si je veux générer un nombre de Carmichael de taille supérieure à N, je prends n au hasard supérieur à N, je le factorise (pour l'instant avec un fonction intégrée, d'où MAPLE ou une librairie de théorie des nombres en C), je teste si pour tous ses facteurs premiers p, on a bien p-1 | n-1. Si ça marche j'ai gagné, sinon, je recommence. Faisons cela pour commencer et voyons...

[musyk]

Non non, je ne suis pas têtue

1.

Hypothèse : Supposons que a soit premier avec n, alors a est premier avec tous [tex]{p}_{i}[/tex]. On peut ainsi écrire [tex]{a}^{{p}_{i}-1} \equiv 1 mod ({p}_{i})[/tex] selon le Théorème de Fermat. ( Pour tout i = 1,2,3, ... , k).

Preuve : On a [tex]({p}_{i}-1)\left|(n-1)\Leftrightarrow n-1 = {q}_{i} * ({p}_{i}-1)[/tex].

On peut donc écrire [tex]{a}^{n-1}\equiv mod 1 ({p}_{i})[/tex],
puis [tex]{p}_{i} \left| {a}^{n-1}-1[/tex].

On sait que les [tex]{p}_{i}[/tex] sont des nombres premiers deux à deux distincts, ainsi [tex]{p}_{1},{p}_{2}, ..., {p}_{k}\left| {a}^{n-1}-1[/tex] et donc ................................................. [tex]{a}^{n-1}\equiv 1 mod n[/tex] ( = [tex]{a}^{n-1}[/tex] est congru à 1 modulo n ).

Conclusion : n est un nombre de Carmichaël




Je laisse le soin à quelqu'un d'autre d'écrire en écriture maple (ou C), ce qu'erd à demander ............

[musyk]

2. Dans toute cette question, on suppose que n est un nombre de Carmichaël et l’on désire établir la réciproque du résultat obtenu
en question 1.
(a) On suppose tout d’abord que n est une puissance de 2, n = 2, où est un entier
2.
Quel est le cardinal de (Z/nZ)

? En déduire que pour tout entier a impair a(2 −1) ne peut être congru à 1 modulo n
sauf si a est congru à 1 modulo n ; que peut-on conclure ?

... si quelqu'un a des idées , des hypothèses ou la réponse .... qu'il n'hésite pas !

[Xklr_65]

J'ai trouvé une procédure MAPLE pour tester si un nombre est de Carmichael ou pas (en utilisant la fonction ifactors, ce qui peut être hasardeux pour des grand nombres).

Code: Tout sélectionner

> carmichael:=proc(N)
printf("Parti potasser son bouquin...");
end:


[erd]

Il semble que votre "copier-coller" ait mangé la moitié du code....

[musyk]

A la fin du "end", ne serait ce pas un ";" sous maple?!

Et la Musyk elle ne potasse pas, elle abandonne !

[Xklr_65]

En fait il n'existe pas beaucoup de différence entre : et ;
Ils servent tous les deux à terminer une ligne de commande, à la différence que le point virgule force Maple à afficher le résultat. Mais dans certains cas ça n'est pas forcément utile. Par exemple, lorsque l'on fait un plot pour pouvoir l'afficher après: comme:

Code: Tout sélectionner

f:=plot(sin(x),x=0..Pi)

Mettre un point virgule à la fin nous affiche une grande série de chiffres, ce qui est inutile. Dans ces cas là il vaut mieux finir sa ligne de commande sans afficher le résultat.