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

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : juillet 2017
    Messages : 2
    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 : 140
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 533
    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 533
    Points : 3 188
    Points
    3 188

    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 144
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ninja

    Informations forums :
    Inscription : juillet 2013
    Messages : 1 144
    Points : 6 534
    Points
    6 534
    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 039
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 45
    Localisation : France, Hérault (Languedoc Roussillon)

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

    Informations forums :
    Inscription : décembre 2006
    Messages : 10 039
    Points : 15 637
    Points
    15 637

    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 039
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 45
    Localisation : France, Hérault (Languedoc Roussillon)

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

    Informations forums :
    Inscription : décembre 2006
    Messages : 10 039
    Points : 15 637
    Points
    15 637

    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 éprouvé

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    décembre 2010
    Messages
    486
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 71
    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 : 486
    Points : 943
    Points
    943
    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

  7. #7
    Nouveau Candidat au Club
    Homme Profil pro
    Chercheur en informatique
    Inscrit en
    mars 2014
    Messages
    1
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Chercheur en informatique

    Informations forums :
    Inscription : mars 2014
    Messages : 1
    Points : 1
    Points
    1

    Par défaut

    Ce que tu cherche est une permutation aléatoire (sur ton ensemble d'entier). Grosso modo une permutation ca décrit une table de correspondances entre les différents éléments de ton ensemble. Une permutation aléatoire c'est une permutation prise au hasard dans l'ensemble des permutations qui existe.

    A partir de là tu a deux manières de procéder:
    Tu génère un permutation aléatoire, ce qui revient bêtement à génerer ta table de correspondances. Tu peux le faire par exemple avec leMélange de Fisher-Yates, mais ca veut dire que tu dois stocker toute la table en mémoire (donc si tu veux faire tous les nombres sur 32 bits par exemple ca va être chaud).

    Sinon tu peux génerer ta table au fur et a mesure. C'est à dire que tu commence avec ta table vide, et tu la remplis avec un nombre aléatoire à chaque fois qu'il y a une requète pour un nombre qui n'a pas encore été demandé. Mais la encore si tu as plein de requètes sur plein de nombres différents, ça consome de la mémoire.

    Dans tous les cas la table de correspondance se fera avec une Bidirectional map, pour garantir la bijection et pour pouvoir récupérer les clés à partir des valeurs. Il y a rien de magique la-dedans, c'est essentiellement deux tables de hachages dont les clés de l'une sont les valeurs de l'autre, et inversement.

    Après avoir lu ton message, j'ai plus l'impression que ton but c'est de mettre en relation deux nombres (peu importe lesquels) de façon à ce que personne ne puisse prédire les prochaines associations, même connaissant les associations actuelles. Dans ce cas tu as une solution simple: tu génère une clé privée (et qui le reste !), et tu chiffre/déchiffre ton nombre avec un algo de chiffrement à flot (au hasard, ChaCha20) pour avoir les correspondances.

    Génerer un tableau est peut être plus simple a implémenter (pas besoin de lib, le tout se fait en quelques lignes de code max), mais demande un espace de stockage proportionnel au nombre d'associations que tu fais. La technique du chiffrement se fait grosso modo en temps et mémoire constant, mais ça demande un poil plus de réflexion et de recherche.

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, 23h07
  2. fonction aléatoire sous l'AS 400
    Par tenah34 dans le forum AS/400
    Réponses: 6
    Dernier message: 02/09/2008, 18h08
  3. Fonction aléatoire pas ordinaire
    Par gotrunkssj dans le forum C
    Réponses: 5
    Dernier message: 21/01/2008, 14h09
  4. Excel fonction aléatoire
    Par Biker-Robby dans le forum Excel
    Réponses: 3
    Dernier message: 11/12/2007, 10h17
  5. Fonctions aléatoires pour caractères
    Par IDE dans le forum C
    Réponses: 14
    Dernier message: 13/05/2007, 16h06

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