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.

Algorithme de recherche des nombres premiers

Aujourd’hui, nous nous intéressons aux nombres premiers et à la façon de les trouver. Pour cela, voilà un algorithme assez simple qui permet de trouver un nombre n de nombre premier. Dans sa première version, l’algorithme recommençait à calculer à partir de 5 (si ma mémoire est bonne ;) ) à chaque exécution. Dans sa version actuelle, nous pouvons maintenant reprendre les calculs à partir du dernier nombre premier trouvé. Quelques améliorations pourront néanmoins être apporter comme la possibilité d’interrompre le programme alors qu’il teste des nombres et de le relancer sans avoir à repartir du dernier nombre premier, la gestion des grands nombres pourrait être à revoir. Nous pouvons également envisager la division du fichier contenant les nombres premiers en plusieurs autres fichiers tous les x nombres.

L’algorithme est présenté en code C et repose sur ce que mon professeur de sécurité désignait il y a quelques jours comme la « méthode naïve »; puisqu’il existe d’autres méthodes, permettant de s’assurer qu’un nombre n’est pas premier entre autres (mais pas d’équivalence ici, si le nombre n’est pas premier, le théorème ne permet pas de monter qu’il l’est) et dont je parlerais certainement dans un autre article.

Au jour d’aujourd’hui, notre fichier fait 969 376 620 octets et est trop grand pour être ouvert par certains éditeur de texte :D.  Pour déterminer si un nombre est premier, l’algorithme va regarder le résultat de la division du nombre testé par les nombres premiers déjà présent dans le fichier. Si le reste vaut 0, le nombre testé est divisible par un autre nombre que 1 ou lui-même, il n’est donc pas premier. On peut arrêter ce test, lorsque le nombre premier utilisé dans la division euclidienne est supérieur à la racine carré du nombre testé et ainsi gagner du temps. De même, l’incrémentation des nombres testés de 2 en 2 à partir d’un entier impair permet de ne jamais tester les nombres pairs puisque nous les savons tous divisibles par 2. Le lien vers un dossier contenant le code et les fichiers qu’il utilise: Algorithme Nombres Premiers. Place maintenant au programme:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int premier(int test);

int main(void)
{
    /*VARIABLE:
      recherche: le nombre de nombre premier à rechercher
      dernier: le dernier nombre testé
        lors de l'appel précédent au programme,
        contenu dans dernier.txt*/

    int recherche, dernier;
    FILE *fichier_dernier_nbr;
    FILE  *fichier;
    recherche=100;
    dernier=0;

    /*Initialisation du dernier nombre testé
      dernier est obligatoirement impair*/
    fichier=NULL;
    fichier_dernier_nbr = NULL;
    fichier_dernier_nbr = fopen("dernier.txt", "r+");

    if (fichier_dernier_nbr != NULL)
    {
        fscanf(fichier_dernier_nbr, "%d", &dernier);
        fclose(fichier_dernier_nbr);
    }

    /*On recherche autant de nombre premier
       que le contenu de recherche*/
    while(recherche>0)
    {
        if(premier(dernier))
        {
            /*Le nombre testé est premier*/
            /*printf("%d:Premier\n", dernier);*/
            /*On enregistre le nombre à la fin du fichier*/
            fichier = fopen("test.txt", "r+");
            fseek(fichier, 0, SEEK_END);
            fprintf(fichier, "%d\n", dernier);
            fclose(fichier);
            /*On décrémente le nombre de nombre premier
              encore à trouver*/
            recherche--;
        }
        dernier=dernier+2;
    }
    /*On enregistre le dernier à la fin du fichier*/
    fichier = fopen("dernier.txt", "w+");
    fseek(fichier, 0, SEEK_SET);
    fprintf(fichier, "%d", dernier);
    fclose(fichier);

    printf("Operation effectuee avec succes.\n");

    return EXIT_SUCCESS;
}

/*Renvoi 1 si le nombre est un nombre premier*/
int premier(int test)
{
    int nb_premier;
    int borne=0;

    FILE* fichier = NULL;
    fichier = fopen("test.txt", "r+");

    if (fichier != NULL)
    {

        while(feof(fichier)==0 && borne==0)
        {    
            fscanf(fichier, "%d", &nb_premier);
            /*printf("%d\n", nb_premier);*/
            /*Nombre divisible par un nombre premier,
              premier(test)=0*/
            if(test%nb_premier==0)
            {
                fclose(fichier);
                return 0;
                }
            /*Si la racine carré du nombre testé est inférieure au
              nombre premier actuel,inutile de continuer le test*/
            if(nb_premier>sqrt(test))
            {borne=1;}
        }

        fclose(fichier);
        if(borne==1)
        {return 1;}
    }
    return 0;
}

Illustration: illustrer.fr

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 ?

Sécurité Informatique: Intro et Théorie

Principes fondamentaux

La sécurité informatique est un ensemble de moyens techniques, juridiques, organisationnels et humains pour garantir la sécurité des systèmes d’information (SI). Les critères de la sécurité des SI sont :

  • La disponibilité : Consiste à assurer l’accessibilité de la ressource informatique (utilisable en un temps de réponse acceptable) et la possibilité de mener à terme une session de travail.
  • L’intégrité : Consiste à pouvoir confirmer que les données, les traitements et les serveurs n’ont pas été altérés, modifiés ou détruits de façon intentionnelle ou accidentelle.
  • La confidentialité : Consiste en le maintien du secret des informations, à savoir que l’information est seulement accessible à ceux qui ont droits.

Remarque :

Bien que la sécurité des SI repose sur ces trois critères, le poids donné à chaque critère dépend de l’institution.

Exemple :

Banque → Intégrité

Militaire → Confidentialité

Fournisseur d’accès internet → Disponibilité

 

Deux critères s’ajoutent aux trois premiers :

  • Traçabilité : Consiste à s’assurer qu’un événement a eu lieu et que seuls les entités identifiées sont à l’origine de l’événement. On parle alors de : authentification, non-reproduction, compatibilité, journalisation.
  • Auditabilité : Consiste en la capacité du système à garantir la présence des informations nécessaires à une analyse ultérieure.

 

Périmètre de sécurité 

La sécurité des SI se décline en plusieurs périmètres de sécurité. Nous parlerons donc de :

  • Sécurité physique : Elle concerne l’environnement dans lequel se situent les systèmes et leurs moyens de maîtrise.
  • Sécurité de l’exploitation : Concerne la grande partie des aspects organisationnels, de gestion et de surveillance, qui touchent au bon fonctionnement des SI.
  • Sécurité logique : Elle concerne l’ensemble des mécanismes de sécurité par logiciel.
  • Sécurité applicative : Elle concerne la sécurité des applications installées ou en phase de réalisation.

On peut ajouter la sécurité des télécommunications et la sécurité juridique.

Exemple :

Programmer proprement ->Sécurité applicative

Configuration d’un pare-feu ->Sécurité des télécommunications

Création de configuration et des mises à jour ->Sécurité de l’exploitation

Installation d’antivirus ->Sécurité logique

Protection d’accès ( porte à code) ->Sécurité physique

Analyse des logs ->Sécurité de l’exploitation

Redondance du matériel ->Sécurité physique

 

Les 7 principes de base de sécurité

  1. Moindre privilège : Ce principe stipule que chaque utilisateur et chaque module d’un système ne doit posséder que les droits minimaux pour effectuer ses tâches.
  2. Goulet d’étranglement : Ce principe consiste à éviter tout moyen possible de contourner les points d’accessibilité.
  3. Défense en profondeur : Elle est réalisée en utilisant plusieurs mécanismes de protection redondants.
  4. Maillon le plus faible : Un système de protection n’est jamais plus efficace que son élément le plus faible.
  5. Déni par défaut : Consiste de partir du principe qui consiste à tout interdire sauf ce qui est explicitement permis.
  6. Simplicité : Plus le système de protection est simple, plus il a de chances d’être configuré et maintenu. Il est ainsi capable de fournir une sécurité presque sans faille car il est plus facile à documenter et à valider.
  7. Participation des utilisateurs : Un système de sécurité n’est efficace que si tous les utilisateurs adhèrent à ses principes.

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/