Discussion :

[sloshy]

Bonsoir,
Désolé si le titre n'est pas claire, j'ai du mal à mettre un nom sur ce que je cherche à faire
J'essaie de créer une fonction qui prend en paramètre une clef et un index maximum.

Le but du jeu est que

• La fonction retourne un nombre entre 1 et index_maximum.
• Si la fonction est appelée deux fois avec la même clef, le retour soit identique.
• Que la dispersion soit bonne. (si j'ai 1 000 000 de clef différente et que j'ai un index_maximum à 5, j'aimerai qu'il y ai approximativement autant de 1 que de 2 que de 3 que de 4 et que de 5).

J'ai eu beau faire quelque essais mais soit je n'arrive pas a avoir une bonne dispersion, soit je n'arrive pas à retourner deux fois la même chose pour une clef identique.
Je fais donc appels à vous

[edfed]

pour generer de l'aleatoire, il existe plein de methodes.

bientot, la generation de nombres aleatoires sera directement supportée par les CPU intel avec l'instruction RDRAND.

en attendant, il existe des tonnes d'algorithmes ayant plus ou moins d'instructions elementaires.
il faut essayer diverses combinaisons d'instructions logiques et arithmetiques de base, et observer le resultat avec divers programmes de test.

le but est, en partant d'une graine G, de toujours obtenir la meme sequence S{...}.
et si on va plus loin en faisant un XOR de la sequence avec un fichier, ça ressemble à de la cryptographie.

je ne sais pas quel langage utiliser pour ça en dehors de l'assembleur, surtout s'il faut aller vite.

[Jimmy_]

et si on va plus loin en faisant un XOR de la sequence avec un fichier, ça ressemble à de la cryptographie.

Oui c'est tout à fait normal. Tous les algorithmes modernes de cryptographie sont d'excellent générateur de nombre pseudo-aléatoire, puisque si l'on parviens à trouver un biais statistique au niveau de leur sortie, cela indique une faiblesse exploitable pour l'attaquer.

Sinon Java à la base utilise la fonction suivante pour générer des nombres pseudo aléatoires, s étant le seed.

sqrt(-2 * log(s) / s);

[pseudocode]

Je ressors un vieux code déjà posté ici :

Code java :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
/* return a pseudo-random number between 0 and 1 */
public static double rnd(int x) {
	x = (x<<13)^x;
	return ((x*(x*x*15731+789221)+1376312589) & 0x7fffffff) / 2147483648.0;
}

Manque une petite transformation pour avoir un entier entre 1 et N, et le tour est joué.

Code java :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
/* return a pseudo-random integer between 1 and N */
public static int rnd(int x, int N) {
	x = (x<<13)^x;
	return 1 + ((x*(x*x*15731+789221)+1376312589) & 0x7fffffff) % N;
}

[sloshy]

Merci pour les réponses rapides.
Ma clef n'est pas du tout numérique (c'est un hash type MD5).
Niveau performance il faut que ça reste correcte (c'est dans un langage interprété, tout est relatif) car cette fonction sera appelée à répétition.

En gros, je dispose de plusieurs serveur, contenant chacun une bases de donnée, composée elles même de plusieurs tables (au schéma identique).

Chaque donnée est identifiée par une clef,
Lorsque je veux ajouter une information, je créer la clef, je la passe dans la fonction dont je vous parle, et ça me sors un premier nombre entre 1 et x (suivant le nombre de serveur), puis je vais réutiliser la fonction pour choisir une table (entre 1 et y).
Lorsque je veux lire une information, je possède sa clef, je la passe dans la fonction dont je vous parle et ça me retourne le bon serveur et la bonne table.

Voilà ce que j'essaye de faire en fait.

[pseudocode]

Merci pour les réponses rapides.
Ma clef n'est pas du tout numérique (c'est un hash type MD5).

Un hash MD5 est une valeur numérique (sur 128 bits).

La fonction random que j'ai donné prend en paramètre une valeur sur 32 bits.
En découpant le hash MD5 en 4*32bits, on peut appeler 4 fois la fonction random, en cascadant les résultats/paramètres (par exemple un XOR).

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
/* return a pseudo-random positive integer */
public static int rnd_int32p(int x) {
	x = (x<<13)^x;
	return ((x*(x*x*15731+789221)+1376312589) & 0x7fffffff);
}
 
// 4 calls
int rnd = 0;
rnd = rnd_int32p(rnd ^ md5_bits1_32);
rnd = rnd_int32p(rnd ^ md5_bits33_64);
rnd = rnd_int32p(rnd ^ md5_bits65_96);
rnd = rnd_int32p(rnd ^ md5_bits97_128);
 
// rescale in 1...N
rnd = 1 + (rnd % N);

[sloshy]

Merci j'ai compris l'idée (oui bon le code est à retoucher mais l'idée est compris)

[edfed]

sympa la solution C, mais il y a 3 multiplications, au moins une division, et un pourcentage en cas de mise à l'echelle, ça mange du CPU tout ça.
voici une fonction random sans multiplication, ni division, ni autre operation math trop gourmande.
elle prend en seed une clé de longueur variable, et la taille de la clé est utilisée dans le calcul du nombre aleatoire 32 bits.
le but etait de chiffrer un fichier à partir d'une clé de longueur variable, testé avec des clés de 32000 bits sans perte notable de vitesse. après, c'est très lent.

Code asm :

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
 
.rnd:
;edx = seed(size,[key])
;return eax = rnd
        push ebx ecx
        xor eax,eax
        mov ecx,[edx]
        shr ecx,2
        dec ecx
        jl .not
        push ecx
        stc
        xor ebx,ebx
@@:
        sbb eax,[edx+ecx*4]
        xor eax,ecx
        lea ebx,[eax*4+ecx+127]
        loop @b
        xor eax,ecx
        stc
        pop ecx
@@:
        adc [edx+ecx*4],eax
        adc eax,[edx+ecx*4]
        adc ebx,eax
        xor eax,ebx
        ror eax,cl
        loop @b
.not:
        pop ecx ebx
        ret
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

je serais curieux de savoir comment on pourrait traduire ce code en C ou en pseudo code.
ça permettrais de partager le meme systeme de chiffrement avec d'autres programmes, dans d'autres langages.

pour generer un nombre entre X et Y, on peu faire un pourcentage, mais aussi un modulo.
le pourcentage demande une multiplication et une division, alors que le modulo ne demande qu'une division. sur un nombre aleatoire, le modulo est aussi aléatoire que le pourcentage.