Nombre premier: test de primalité

Comme annoncé dans mon dernier article, concernant l’algorithme de recherche des nombres premiers, nous allons nous pencher sur différents tests de primalité d’un point de vue plus mathématique. Néanmoins, cela devrait rester abordable, nul besoin de la connaissance des espaces vectoriels pour comprendre :D.

Méthode naïve:

Il suffit de diviser le nombre n dont on veut tester la primalité par tous les nombres de 2 à √n, car si n = p * q et dans ce cas, on a: p <= √n et q<= √n. En effet, supposons que        p >= q > √n; p > √n, q > √n; p*q > √n   -> absurde car n = p*q. On peut encore améliorer le test et ne tester que les nombres impairs une fois que la division par 2 a échoué. La complexité de ce test est exp( 1/2 * log n ).

Test de Fermat:

Rappel: Si n est premier et si a < n, alors a^(n-1) ≡ 1 mod n.                                 Conséquences:
Soit a < n,  Si a ^(n-1) ≠ 1 mod n alors n n’est pas premier.                                                 Ce test élimine mais ne confirme pas. Il est possible de déterminer si le nombre n’est pas premier. La réciproque est fausse.

Test de Lucas-Lehmer:

Si p est premier, le nombre de Mersenne Mp d’indice p est défini par: Mp = 2^p  –  1 .       On définit une suite Sn par S2 = 4 et Sn = (S(n-1))² – 2.                                                        Alors, Mp est premier ssi Mp divise Sp, c’est-à-dire: Sp ≡ 0 mod p.

11 Mars 2011, une année après le drame !

Séisme Japonais

Source visuelle: « Kanpai.fr »

Il y a un an jour pour jour, au Japon. Une petite pensée pour tout ceux qui l’ont vécu ! Le tremblement de terre qui nous fait tous trembler !

Mais que pouvons-nous faire contre la nature..

Cette catastrophe tant naturelle qu’humaine (nucléaire) pousse nos gouvernements à penser à d’autres solutions viables de production d’énergie, même s’ils ne semblent pas pressés d’en trouver !

Dans un monde où l’or noir est devenu indispensable, que pouvons nous dire de l’électricité, pouvons nous nous en passer ? Sûrement pas ! Alors quelle sera l’évolution qui permettra d’en produire sans risquer la vie de milliers de personnes et de milliers de kilomètres carrés de terrains fertiles et habitables ?

Le Raspberry Pi

Un ordinateur complet pour 25 euros, de la science fiction ? Eh ben figurez vous que non, depuis quelques temps, un projet fait fureur sur le net. Il s’agit du Raspberry Pi, un Le Raspberry Piordinateur aussi petit qu’une carte de crédit.

Proposé de base avec un noyaux linux (Debian), il intègre de nombreux logiciels dédiés à la programmation, ainsi que le navigateur web Midori réputé pour être l’un des plus légers jamais conçus, il permet un navigation fluide, malgré la faible configuration de la machine.

Les concepteurs du Raspberry pi proposent deux modèles (A et B) relativement similaires.  Les deux intègrent un processeur ARM (Architecture très répandu dans l’informatique embarquée) d’une puissance 700 MHz. Pour l’affichage, nous disposons d’une sortie vidéo composite standard (RCA) ainsi que d’une sortie HDMI. Pour ce qui est de la mémoire le Raspberry Pi inclut 256 Mo de mémoire vive (SDRAM) et un port pour une carte SD qui fait office de disque dur. Pour les périphérique seul le strict nécessaire à été gardé : un ou deux ports USB (selon le modèle choisit) et une prise RJ45 pour la connexion réseau (seulement sur le modèle B). Le tout est alimenté en 5V (micro usb, ou alimentation externe).

Interessant par son prix et son bouquet software, cet ordinateur est adapté non seulement aux « grands bidouilleurs », mais aussi aux débutants. De plus, couplé avec un arduino, il offre aussi de nombreuse possibilité au niveau informatique embarquée.

Vous désirez vous en procurer un ? Désolé, mais 2h après sa commercialisation (Mercredi 29 février), les 10 000 étaient déjà tous vendus. Une seconde vague est a prévoir, alors restez patients !

Site officiel : http://www.raspberrypi.org/