1. #1
    Nouveau Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    juillet 2017
    Messages
    1
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Vosges (Lorraine)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : juillet 2017
    Messages : 1
    Points : 1
    Points
    1

    Par défaut Fonction aléatoire particulière

    Bonjour à toutes et tous,

    Je suis actuellement à la recherche d'une fonction capable de me générer un nombre pseudo-aléatoire mais avec quelques règles supplémentaires.

    Cette fonction prendrait un argument (un entier) et retournerait un entier aléatoire associé.
    L'argument sera la seed du nombre aléatoire retourné par la fonction.

    Il faut aussi que la fonction soit bijective, c'est-à-dire que tous les entiers sont "générables" par la fonction.
    Nom : 700px-Surjection_Injection_Bijection-fr.svg.png
Affichages : 95
Taille : 32,6 Ko

    Il ne faut pas qu'on puisse voir de motif dans la génération des nombres donc on peut exclure les fonctions affines ou exponentielles et logarithmiques.
    Enfin, il faudrait que je puisse retrouver la seed depuis un nombre généré.

    Voilà un exemple de ce que je voudrais obtenir :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    fonction(45) ==> 878526
    fonction(46) ==> 245
    fonction(47) ==> 787654
    fonction(48) ==> 7883111
    
    noitcnof(245) ==> 46  // "noitcnof" = "fonction" à l'envers
    noitcnof(7883111) ==> 48
    J'ai cherché un peu sur internet avant de poser ma question ici et je suis tombé sur des articles (en anglais) qui parlaient de "bijective mapping" mais je n'ai rien trouvé de concluant en approfondissant sur cette piste.

    Merci en tout cas pour vos futures réponses, floatNone.

  2. #2
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    décembre 2013
    Messages
    1 352
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : décembre 2013
    Messages : 1 352
    Points : 2 876
    Points
    2 876

    Par défaut

    Tu veux une Bijection d'un ensemble E vers lui-même .... Et l'ensemble E, c'est ? C'est l'ensemble des entiers inférieurs à un certain nombre qu'on va choisir N.

    En tant que bricoleur en chef, on va bricoler un truc :

    Si je me souviens bien de mes cours de maths, si P1 et P2 sont 2 nombres premiers, la fonction suivante convient :
    f(x) = Modulo( P1*x, P2)

    Il faut prendre P2 très grand, plus grand que le nombre N du début.

    Et pour trouver la fonction réciproque g, il y a un nombre unique Q1 tel que P1*Q1 = 1 [modulo P2]
    La fonction réciproque serait donc g(x) = Modulo(Q1*x,P2)


    Cette fonction n'est pas totalement affine, mais elle est affine par morceaux ... c'est gênant.
    En combinant 3 ou 4 fois cette fonction, on va arriver à une fonction assez difficile à reconstituer :
    y = Modulo(P1*x, P2)
    z = Modulo(P3*y, P4)
    t = Modulo(P5*z, P6)
    f(x) = t

    Et la fonction réciproque peut-être trouvée comme dans le premier cas.

    La ""confidentialité"" est probablement faible.

    Tu peux combiner cela avec une autre fonction :
    x = 123456
    Autrement dit , x = 0000000000123456 : je complète à gauche par des 0 , pour avoir nc = 16 chiffres.
    et j'inverse : f(x) = 6543210000000000
    En combinant cette technique avec la technique précédente, tu as une fonction qui devient plus difficile à reconstituer.

    Reste à choisir les bonnes valeurs de P1 P2 P3 P4 P5 P6 et nc pour que les intervalles des fonctions soient compatibles.

    De toutes façons, quand on parle de nombres aléatoires et de cryptologie, on tourne autour des nombres premiers.
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  3. #3
    Rédacteur/Modérateur

    Avatar de yahiko
    Homme Profil pro
    Ninja
    Inscrit en
    juillet 2013
    Messages
    1 137
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ninja

    Informations forums :
    Inscription : juillet 2013
    Messages : 1 137
    Points : 6 452
    Points
    6 452
    Billets dans le blog
    43

    Par défaut

    Je ne sais pas vraiment ce que tu souhaites faire au final, mais j'ai plutôt l'impression que tu souhaites une fonction dite de hachage plutôt qu'un générateur de nombre pseudo-aléatoire. Ce n'est pas tout à fait la même chose.

    La fonction de hachage prend une donnée en entrée et la transforme de façon aléatoire, en apparence, en une autre donnée, de telle sorte que f(n) et f(n+epsilon) --- autrement dit deux données similaires en entrée --- donnent des résultats totalement différents.

    Le générateur de nombres pseudo-aléatoire, c'est différent. C'est un objet qu'on initialise au tout départ à l'aide d'une graine (seed), puis qu'on appelle ensuite, sans argument pour ce qui est de la fonction de base, et qui génère une suite de nombres en apparence aléatoires.
    Tutoriels et FAQ TypeScript

  4. #4
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    10 030
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 44
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : décembre 2006
    Messages : 10 030
    Points : 15 585
    Points
    15 585

    Par défaut

    Citation Envoyé par yahiko Voir le message
    Je ne sais pas vraiment ce que tu souhaites faire au final, mais j'ai plutôt l'impression que tu souhaites une fonction dite de hachage plutôt qu'un générateur de nombre pseudo-aléatoire.
    D'après sa description et son exemple, il veut plutôt un "block cipher" = un bijective mapping d'un champ de bits.

    Puisqu'il s'agit de transformer un entier en un autre entier aléatoire, le plus simple c'est de prendre l'algo RC5 sur 32bits (ou 64 bits, suivant la taille de l'entier).
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  5. #5
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    10 030
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 44
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : décembre 2006
    Messages : 10 030
    Points : 15 585
    Points
    15 585

    Par défaut

    Citation Envoyé par pseudocode Voir le message
    Puisqu'il s'agit de transformer un entier en un autre entier aléatoire, le plus simple c'est de prendre l'algo RC5 sur 32bits (ou 64 bits, suivant la taille de l'entier).
    S'il n'est pas nécessaire d'avoir un haut niveau de résistance à la cryptanalyse, on peut se limiter à permuter les 32 bits de l'entier.
    C'est à dire créer une bijection de (0,1,...,31) vers (0,1,..,31).

    encode(45)=2162832  /  decode(2162832)=45
    encode(46)=66704    /  decode(66704)=46
    encode(47)=2163856  /  decode(2163856)=47
    encode(48)=130      /  decode(130)=48
    On peut aussi travailler par groupe de 8 bits et créer une bijection de (0,...,256) vers (0,...,256).
    On applique alors la permutation sur chacun des 4 octets qui forment l'entier.

    Tout cela nécessite simplement de créer une table de conversion, c'est à dire créer un tableau (1...N) et de la mélanger de manière pseudo-aléatoire en fixant la seed du générateur (afin de pouvoir reconstruire la table de conversion à partir de la même seed).

    Code java : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    // Simple 32bit swapping
    int[] cipher = createCipher(314159265359L); // our seed
    int encoded  = encode(45, cipher);
    int decoded  = decode(2162832, cipher);
     
    int[] createCipher(long seed) {
    	int[] cipher = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31};
    	Random randomizer = new Random(seed);
    	for (int i = 0; i < 32; i++) {
    		int k = randomizer.nextInt(32);
    		int swap = cipher[i]; cipher[i] = cipher[k]; cipher[k] = swap;
    	}
    	return cipher;
    }
     
    int encode(int input, int[] cipher) {
    	int output = 0;
    	for (int bit = 0; bit < 32; bit++)
    		if ((input & (1L << bit)) != 0)
    			output |= 1L << cipher[bit];
    	return output;
    }
     
    int decode(int input, int[] cipher) {
    	int output = 0;
    	for (int bit = 0; bit < 32; bit++)
    		if ((input & (1L << bit)) != 0)
    			output |= 1L << indexOf(cipher, bit);
    	return output;
    }
     
    public static int indexOf(int[] array, int value) {
    	for (int i = 0; i < array.length; i++) if (value == array[i]) return i;
    	return -1;
    }
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  6. #6
    Membre éclairé

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    décembre 2010
    Messages
    363
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 70
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : décembre 2010
    Messages : 363
    Points : 734
    Points
    734
    Billets dans le blog
    5

    Par défaut Fonction aléatoire particulière

    Bonjour,

    Je viens de trouver fortuitement une collection de générateurs congruenciels linéaires, programmés dans 67 langages ... Si cela peut en intéresser quelques uns: c'est sur le site Rosetta.org


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

Discussions similaires

  1. Fonction aléatoire, une fois pour toute ...
    Par Nothingness0x dans le forum Débuter
    Réponses: 19
    Dernier message: 18/11/2008, 22h07
  2. fonction aléatoire sous l'AS 400
    Par tenah34 dans le forum AS/400
    Réponses: 6
    Dernier message: 02/09/2008, 17h08
  3. Fonction aléatoire pas ordinaire
    Par gotrunkssj dans le forum C
    Réponses: 5
    Dernier message: 21/01/2008, 13h09
  4. Excel fonction aléatoire
    Par Biker-Robby dans le forum Excel
    Réponses: 3
    Dernier message: 11/12/2007, 09h17
  5. Fonctions aléatoires pour caractères
    Par IDE dans le forum C
    Réponses: 14
    Dernier message: 13/05/2007, 15h06

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo