Partage
  • Partager sur Facebook
  • Partager sur Twitter

Petit Défis

C l'été ?

    11 juillet 2017 à 22:07:39

    Plop à tous !

    Voici encore un petit défis.
    Le défis ne sera pas trop dur... enfin, selon vos connaissances en 'mathématiques' !
    Si vous avez des questions, n'hésitez pas à les poser, moi si possible ou un bon samaritain de passage y répondra ;)
    On évite de donner la réponse pour permettre à tout le monde de tenter ;) Mais ça n'empêche pas d'aider bien sûr !

    Defi N°1


    Voici un fichier qui a subi le passage d'un nouveau genre de virus : le neuneuware.

    Voici ce qu'est devenu le fichier :

    992a7d62d4f1e9225b94207eaf7d9bd420f0999b200d7e20d2b77e2045b7d420447d20f0999b9b7d3e3ab4287d270b99d37d27619b2799270c617d2759207d9bd420d2617d7e20457d610c0c7d0d6220593a3a

    et voici le principe actif du "virus" en question : (disponible ici : https://ideone.com/rQHU2L )
    Seriez-vous capable de retrouver le contenu du fichier , où est-ce impossible de revenir en arrière ?



     Défis N°2

    Un peu plus complexe (mais pas beaucoup plus):
    Le paramètre multiplicateur peut être amené à changer.
    Faire une fonction permettant de déchiffrer, si possible, le message en prenant le multiplicateur en paramètre.
    Et permettant de déchiffrer le message.
    Essayer d'optimiser au maximum !

    Défis N°3

    En utilisant uniquement des type entier sur 4 octets MAXIMUM.
    Créer un algorithme de type "brut force" pour tester les 2 propriétés suivantes.

    Je prend un nombre N > 3
    Je prend tous les nombres <N et premier avec N (pgcd(nombre,N)=1)

    Les nombre peuvent ne pas être premiers ( exemple 25 premier avec 42)

    • A :La somme de tous ces nombres modulo N donne N-1
    • B :Le produit de tous ces nombres modulo N donne N-1 ou 1
    Faite un algorithme pour déterminer si ces règles sont respectées pour ces nombres : (et les valeurs de A: et B: )
    • 4
    • 42
    • 424242
    • 666666
    • 666667
    • (BONUS : attention, exécution longue) : 4294967295

    Amusez-vous bien ;) 
    Et je donnerai une solution dans un mois environs (selon mes disponibilités)

    -
    Edité par neuneutrinos 17 juillet 2017 à 9:58:46

    • Partager sur Facebook
    • Partager sur Twitter
      11 juillet 2017 à 22:23:55

      neuneutrinos a écrit:

      Plop à tous !

      Voici encore un petit défis.

      Edité par neuneutrinos il y a 11 minutes


      YOUPI !!! ;)
      • Partager sur Facebook
      • Partager sur Twitter
        12 juillet 2017 à 19:43:01

        S'il le faut, je peux donner quelques indices.

        Pour le défis N°3 , un exemple avec 18.


        5,7,11,13,17 sont premiers avec 18.


        5+7+11+13+17= 53
        5*7*11*13*17 = 85085

        53%18 = 17


        85085%18 =17

        Pour 18, les propriétés sont vérifiées ;) 



        -
        Edité par neuneutrinos 17 juillet 2017 à 9:56:09

        • Partager sur Facebook
        • Partager sur Twitter
          14 juillet 2017 à 13:16:36

          mad scientist et cauld ont réussi le défis 1&2 avec deux manières différentes ;)
          • Partager sur Facebook
          • Partager sur Twitter
            17 juillet 2017 à 10:01:40

            Petite précision pour le défis n°3

            les nombres premiers avec N ne sont pas nécessairement premier.

            exemple pour N=5.

            2,3,4 sont premiers avec 5

            et les propriétés sont vérifiée pour N=5

            -
            Edité par neuneutrinos 17 juillet 2017 à 10:02:31

            • Partager sur Facebook
            • Partager sur Twitter
              18 juillet 2017 à 9:18:27

              Bon, comme je suis pas très très bon en math, je vais quand même demander de l'aide pour le premier exercice, parcequ'il y a un truc que je pige pas ...
              Je prends une lettre chez moi. puis j'applique l'opérateur, ça me donne un nombre en binaire. A tout hasard, on va dire

              0000 0000 0000 0000 1001 1001 0011 1010

              Si par contre, j’enlève le 0xff, ça me donne
              0000 0001 0101 1001 1001 0010 0011 1010.
              Je vais les mettre l'un en dessous de l'autre

              0000 0000 0000 0000 1001 1001 0011 1010
              0000 0001 0101 1001 1001 0010 0011 1010

              Est-ce que quelqu'un peut m'expliquer pourquoi ça me donne ça? (Je sais ce que ça fait de faire &0xff, mais j'arrive pas à comprendre le résultat la..., a moins que ce soit une erreur?)

              • Partager sur Facebook
              • Partager sur Twitter

              « Je n’ai pas besoin de preuve. Les lois de la nature, contrairement aux lois de la grammaire, ne permettent aucune exception. »

                18 juillet 2017 à 9:44:23

                X&0xff ne garde que le premier octet.

                On dirait que tu as fais 0xf ou 0x0f au lieu de 0xff.

                Sans le code je ne peux pas dire autre chose malheureusement

                • Partager sur Facebook
                • Partager sur Twitter
                  18 juillet 2017 à 9:50:58

                  Comment dire ... un moment je fais :

                  int main(void)
                  {
                   int lettre;
                   const int multiplicateur=57;
                   while(scanf("%c",&lettre)==1)
                   {
                    printf("%02x",(multiplicateur * lettre)&0xff);
                   }
                  
                   // (multiplicateur * lettre)&0xff) (a) = 993a =    0000 0000 0000 0000 1001 1001 0011 1010
                   // (multiplicateur * lettre)       (a) = 159923a = 0000 0001 0101 1001 1001 0010 0011 1010
                   printf("\n");
                   return 0;
                  }
                  

                  et apres je fais

                  int main(void)
                  {
                   int lettre;
                   const int multiplicateur=57;
                   while(scanf("%c",&lettre)==1)
                   {
                    printf("%02x",(multiplicateur * lettre));
                   }
                  
                   // (multiplicateur * lettre)&0xff) (a) = 993a =    0000 0000 0000 0000 1001 1001 0011 1010
                   // (multiplicateur * lettre)       (a) = 159923a = 0000 0001 0101 1001 1001 0010 0011 1010
                   printf("\n");
                   return 0;
                  }
                  




                  • Partager sur Facebook
                  • Partager sur Twitter

                  « Je n’ai pas besoin de preuve. Les lois de la nature, contrairement aux lois de la grammaire, ne permettent aucune exception. »

                    18 juillet 2017 à 13:53:34

                    Le premier resultat devrait être 3a. Rien de plus.

                    essaie avec un format en décimal. Sinon ( &0xff == %256) mais je ne vois pas pourquoi tu trouve autre chose

                    • Partager sur Facebook
                    • Partager sur Twitter
                      18 juillet 2017 à 13:59:18

                      Je me disais que je trouvais ça bizarre!
                      Mais peut-être que j'ai trouvé une piste. Quand je fais
                      printf("%0x %0x",(multiplicateur * lettre)&0xff,(multiplicateur * lettre)&0xff);
                      le résultat est 99 993a 3a ...
                      Ce que je pensais c'était qu'il prenait mon retour chariot en compte, mais je comprends pas pourquoi il est avant, et pas après ...

                      -
                      Edité par KirbXCoucou 18 juillet 2017 à 14:08:43

                      • Partager sur Facebook
                      • Partager sur Twitter

                      « Je n’ai pas besoin de preuve. Les lois de la nature, contrairement aux lois de la grammaire, ne permettent aucune exception. »

                        18 juillet 2017 à 14:11:24

                        hmmm test en mettant multiplicateur à 1. on sera fixé sur les caractères lu
                        • Partager sur Facebook
                        • Partager sur Twitter
                          18 juillet 2017 à 14:24:11

                          ça me donne 61a
                          • Partager sur Facebook
                          • Partager sur Twitter

                          « Je n’ai pas besoin de preuve. Les lois de la nature, contrairement aux lois de la grammaire, ne permettent aucune exception. »

                            18 juillet 2017 à 14:44:59

                            tu ne devrais pas pouvoir dépasser 255. c'est le principe même du &0xff...

                            sinon fait un  %256.

                            • Partager sur Facebook
                            • Partager sur Twitter
                              18 juillet 2017 à 15:13:06

                              ça me donne la même chose :D
                              Je vais essayé de voir en flushant ma sortie avant de print
                              • Partager sur Facebook
                              • Partager sur Twitter

                              « Je n’ai pas besoin de preuve. Les lois de la nature, contrairement aux lois de la grammaire, ne permettent aucune exception. »

                                18 juillet 2017 à 19:01:40

                                Sinon J'ai eugchriss qui a réussi le défis 1&2 :)

                                -
                                Edité par neuneutrinos 18 juillet 2017 à 19:02:58

                                • Partager sur Facebook
                                • Partager sur Twitter
                                  20 juillet 2017 à 0:29:22

                                  Pour le moment le défis n°3 résiste encore toujours aux programmeurs.
                                  Non il n'est pas si trivial qu'il n'y paraît...

                                  Si personne ne trouve, je commencerai à donner quelques indices :) 

                                  • Partager sur Facebook
                                  • Partager sur Twitter
                                    25 juillet 2017 à 8:55:06

                                    plop !

                                    2 personnes ont validé le troisième défis !

                                    Leur pseudo ?

                                    fromvega et XDeath !

                                    Je ferais une correction prochainement !

                                    Pour les retardataires, vous pouvez toujours le faire pour vous !

                                    • Partager sur Facebook
                                    • Partager sur Twitter
                                      31 juillet 2017 à 15:25:04

                                      Rédaction de la correction

                                      Si vous aviez eu des points bloquants ou des questionsque je peux intégrer, faites-en part !

                                      • Partager sur Facebook
                                      • Partager sur Twitter
                                        8 août 2017 à 17:56:28

                                        voici ma solution du N°1 ;

                                        comme je suis fâché avec les maths ,j'utilise un tableau pour stocker toutes les possibilités de codage sur 1 octet (256) , puis 

                                        je boucle pour chaque nombre hexadécimal afin de retrouver sa valeur dans le tableau ....

                                        J'avoue avoir eu du mal avec sscanf(,,,) mais il y a un bout de temps que je n'avait pas codé en C et l'on sait que les chaînes 

                                        de caractères sont loin d'être le point fort de cet EXCELLENT langage !

                                        #include <stdio.h>
                                        #include <stdlib.h>
                                        #include <string.h>
                                        
                                        int main(void)
                                        {
                                            int tableau[256],i,j,tmp;
                                            const int multiplicateur=57;
                                            char* tab = "992a7d62d4f1e9225b94207eaf7d9bd420f0999b200d7e20d2b77e2045b7d420447d20f0999b9b7d3e3ab4287d270b99d37d27619b2799270c617d2759207d9bd420d2617d7e20457d610c0c7d0d6220593a3a";
                                            int longueur = strlen(tab)/2;
                                            char *clair = malloc(longueur);
                                            for(i = 0;i<256;i++) { tableau[i] = (multiplicateur*i)&0xff; }
                                            for(j=0;j<longueur;j++)
                                            {
                                                sscanf(tab+j*2,"%02x",&tmp);
                                                for(i = 0;i<256;i++) { if(tmp == tableau[i]) break; }
                                                *(clair+j) = i;
                                            }
                                            printf("%s",clair);
                                            return 0;
                                        }

                                        Pour le N°2 : On change la signature de main() 

                                        int main(int argc,char *argv[])

                                        puis plus loin :

                                        if(argc > 1) { multiplicateur = atoi(argv[1]); }

                                        En ayant pris soin de ne pas déclarer 'multiplicateur' constant.

                                        -
                                        Edité par PhilippeBeckx 8 août 2017 à 18:38:36

                                        • Partager sur Facebook
                                        • Partager sur Twitter
                                          12 août 2017 à 18:52:24

                                          Bonsoir tous.

                                          l'addition des nombres modulo 4 est : 3

                                          la multiplication des nombres modulo 4 est : 3

                                          l'addition des nombres modulo 42 est : 41

                                          la multiplication des nombres modulo 42 est : 1


                                          l'addition des nombres modulo 424242 est : 424241

                                          la multiplication des nombres modulo 424242 est : 52577


                                          l'addition des nombres modulo 666666 est : 666665

                                          la multiplication des nombres modulo 666666 est : 293063


                                          l'addition des nombres modulo 666667 est : 666666

                                          la multiplication des nombres modulo 666667 est : 0


                                          l'addition des nombres modulo 4294967295 est : 4294967292

                                          la multiplication des nombres modulo 4294967295 est : 0


                                          Visiblement ,les propriétés sont vérifiées pour 4 et 42.


                                          Voici mon code (pas très efficace car je stocke tous les nombres et appelle realloc() souvent.

                                          #include <stdio.h>
                                          #include <stdlib.h>
                                          
                                          void calculus(unsigned long n,unsigned long nbre,unsigned long *nombres)
                                          {
                                              unsigned long totalAdd = 0;
                                              unsigned long totalMul = 1;
                                              
                                              for(unsigned long j=0;j<nbre;j++)
                                              {
                                                  totalAdd += *(nombres + j);
                                                  totalMul *= *(nombres + j);
                                              }
                                              printf("l'addition des nombres modulo %lu est : %lu\n",n,totalAdd%n);
                                              printf("la multiplication des nombres modulo %lu est : %lu\n",n,totalMul%n);
                                          }
                                          
                                          int main(int argc,char *argv[])
                                          {
                                              unsigned long tmp,nombre,borneSup,divisible,index = 0,taille = 2,borneInf = 2;
                                              unsigned long *diviseur = malloc(taille*sizeof(unsigned long));
                                              unsigned long *candidats = malloc(taille*sizeof(unsigned long));
                                              
                                              if(argc < 2 || atol(argv[1]) < 4)
                                              {
                                                  printf("Usage : %s <nombre> --> nombre > 3\n",argv[0]);
                                                  exit(-1);
                                              }
                                              nombre = borneSup = atol(argv[1]);
                                              while(borneInf<borneSup)
                                              {
                                                  if(!(borneSup%borneInf))
                                                  {
                                                      borneSup = borneSup/borneInf;
                                                      *(diviseur + index++) = borneInf;//stockage diviseur
                                                      // éviter les doublons
                                                      if(borneSup>borneInf) *(diviseur + index++) = borneSup;//stockage quotient
                                                      if(index == taille)
                                                      {
                                                          taille *= 2;
                                                          if((diviseur = realloc(diviseur,taille*sizeof(unsigned long))) == NULL)
                                                          {
                                                              printf("ERREUR re-allocation mémoire ...");
                                                              exit(-1);
                                                          }
                                                      }
                                                  }
                                                  borneInf++;
                                              }
                                              if(index)
                                              {
                                                  /*printf("Diviseurs de %lu : ",nombre);
                                                  for(unsigned long j=0;j<index;j++) { printf(" %lu ",*(diviseur + j)); }
                                                  printf("\n");*/
                                                  tmp = 0; taille = 2;
                                                  for(unsigned long i=nombre-1;i>2;i--)
                                                  {
                                                      divisible = 0;
                                                      for(unsigned long j=0;j<index;j++)
                                                      {
                                                          if(!(i%(*(diviseur+j))))
                                                          {
                                                              divisible = 1;
                                                              break;
                                                          }
                                                      }
                                                      if(!divisible)
                                                      {
                                                          *(candidats + tmp++) = i;
                                                          if(tmp == taille)
                                                          {
                                                              taille *= 2;
                                                              if((candidats = realloc(candidats,taille*sizeof(unsigned long))) == NULL)
                                                              {
                                                                  printf("ERREUR re-allocation mémoire ...");
                                                                  exit(-1);
                                                              }
                                                          }
                                                      }
                                                  }
                                                  /*printf("Nombres premiers avec %lu : ",nombre);
                                                  for(unsigned long j=0;j<tmp;j++) { printf(" %lu ",*(candidats + j)); }
                                                  printf("\n");*/
                                                  calculus(nombre,tmp,candidats);
                                              }
                                              else//nombre est premier <=> pas de diviseur
                                              {
                                                  //printf("%lu est un nombre premier.\n",nombre);
                                                  candidats = realloc(candidats,(nombre-2)*sizeof(unsigned long));
                                                  for (unsigned long i=nombre-1; i>1; i--) { *(candidats+index++) = i; }
                                                  calculus(nombre,index,candidats);
                                              }
                                              
                                              return 0;
                                          }



                                          • Partager sur Facebook
                                          • Partager sur Twitter
                                            14 août 2017 à 2:08:16

                                            Plop, je suis pas mal occuppé ces temps çi.

                                            Mais j'ai écrits environs 50% du corrigé.

                                            Prière de ne pas poster ici vos, solutions, et de laisser chaque personne partir sur la même base ;) 

                                            PhilippeBeckx les résultats ne sont pas les bons, mais je vais y revenir dans le corrigé.

                                            Pour t'en convaincre : le résultat avec 666667 est assez convaincant.

                                            Tu ne multiplies que des nombre premier avec 666667 et tu arrives à 0.C'est à dire avec un nombre multiple de 666667 (donc non premier avec 66667)
                                            Comment est-ce possible ?

                                            -
                                            Edité par neuneutrinos 14 août 2017 à 2:08:39

                                            • Partager sur Facebook
                                            • Partager sur Twitter
                                              14 août 2017 à 7:33:11

                                              Une question : lorsque N est premier faut-il 

                                              considerer le produit de ses diviseurs (c'est à dire 1et N ) ou bien considéré qu'il n'a pas de diviseur et considerer se produit égal à zéro ?

                                              parce que pour le modulo ça change tout !!

                                              • Partager sur Facebook
                                              • Partager sur Twitter
                                                14 août 2017 à 8:28:42

                                                si N est premier, alors il est premier avec tous les entiers > 1 inférieur à lui.

                                                exemple : 11

                                                2,3,4,5,6,7,8,9,10

                                                Pour les nombres premiers il existe un théorème affirmant Que ce résultat sera pour la factorisation , de N-1.

                                                avec 43 je dois trouver (42,42)

                                                avec 1013 (1012,1012)

                                                etc...

                                                -
                                                Edité par neuneutrinos 14 août 2017 à 8:29:29

                                                • Partager sur Facebook
                                                • Partager sur Twitter
                                                  14 août 2017 à 17:07:44

                                                  OK. Apparement un problème de taille des données.

                                                  Pour 43 par exemple on aura probablement un nombre tel que 10^45 !?

                                                  Faut-il fabriquer un algorithme pour traiter les multiplications avec une infinité de nombre ?

                                                  • Partager sur Facebook
                                                  • Partager sur Twitter
                                                    14 août 2017 à 21:40:23

                                                    Hello PhilippeBeckx

                                                    J'vais te répondre en lieu et place de neuneutrinos (pas taper stp gars)

                                                    En fait quand tu fais ton algorithme sur 4 bits, le produit et la somme des éléments passé un certain stade sont en overflow càd qu'un entier codé sur 4 bits NE PEUT PAS stocker le résultat sans dépasser la limite (et te sort n'importe quoi, on dit qu'il est passé en comportement indéterminé (unexpected behavior))... Pour palier à ce problème, en général, on passe sur un type plus grand (8 bits, 16 bits,...). Toutefois, et c'est bien le but du défi, tu ne dois pas les utiliser (ni même caster) !

                                                    Pour ce faire tu dois créer un algorithme qui gère le dépassement tout en restant sur 4 bits et c'est là tout le problème du défi ;)

                                                    PhilippeBeckx a écrit:

                                                    Pour 43 par exemple on aura probablement un nombre tel que 10^45 !?

                                                    Sûrement pas, enfin pour le résultat de retour, vu qu'on modulo le nombre. Donc t'auras au plus nombre-1 comme valeur


                                                    PS: Les valeurs de retour du produit et de la somme sont des propriétés des mathématiques modulaires, j'vais pas dire combien elles valent, mais il n'y a pas 36000 valeurs possibles :ninja:

                                                    -
                                                    Edité par XDeath 14 août 2017 à 21:46:39

                                                    • Partager sur Facebook
                                                    • Partager sur Twitter
                                                      14 août 2017 à 21:46:08

                                                      OK XDeath ; je m'y attelle en ce moment même ...
                                                      • Partager sur Facebook
                                                      • Partager sur Twitter
                                                        15 août 2017 à 9:23:27

                                                        Pourquoi je te taperai ?Je pense terminer le corrigé pour ce week-end

                                                        -
                                                        Edité par neuneutrinos 15 août 2017 à 9:24:23

                                                        • Partager sur Facebook
                                                        • Partager sur Twitter
                                                          15 août 2017 à 9:48:07

                                                          Je crois que je vais abandonner :'( Y aurait moyen de faire en stockant les nombres sous forme de chaines mais en ne traitant que 

                                                          des entiers je vois pas ?! Le problème c'est de détecter le moment du dépassement de capacité ainsi que le stockage du résultat 

                                                          intermédiaire puis de recommencer les multiplications ; parce que je suis désolé mais pour  43 il faut multiplier tous les nombres 

                                                          avant lui ( 1,2,3,4,5, ... 42) et on arrive bien grosso modo vers 10^40 !! C'est l'enfer

                                                          • Partager sur Facebook
                                                          • Partager sur Twitter
                                                            15 août 2017 à 10:10:35

                                                            Si X%N =a
                                                            Si Y%N =b
                                                            Alors (X*Y)%N = (a*b)%N

                                                            Du coup, pour 43, mon calcul ne dépassera jamais 42² soit 1764 , loin des 10^40.
                                                            Cependant... cela n'est pas encore suffisant.

                                                            • Partager sur Facebook
                                                            • Partager sur Twitter
                                                              15 août 2017 à 11:00:10

                                                              Hahaha une tape amicale nan ? :(

                                                              N'abandonne pas, t'as jusqu'au weekend pour le finir, c'est largement suffisant :p

                                                              Indice : Y'a une technique où tu n'es pas obligé de gérer le moment où ça dépasse, renseigne-toi du côté des opérateurs du C mais je te préviens, c'est pas facile :pirate:
                                                              • Partager sur Facebook
                                                              • Partager sur Twitter

                                                              Petit Défis

                                                              × Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
                                                              • Editeur
                                                              • Markdown