Discussion :

[floatNone]

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.


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.

[tbc92]

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.

[yahiko]

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.

[pseudocode]

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).

[pseudocode]

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;
}

[wiwaxia]

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