Discussion :

[charles_dg]

Bonjour,

Je sais pas si vous avez déjà rencontré ce problème mais je génère de grands nombres premiers aléatoires grâce à la classe BigInteger.

Cependant, le premier appel (que ce soit un grand ou un petit nombre) a généré prend énormément de temps. En l’occurrence ici 5 sec pour un nombre aléatoire de 2 bit!

Code :

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
 
BigInteger m;
long start;
long end;
long time=0;
 
SecureRandom rand = SecureRandom.getInstance("SHA1PRNG");
start = System.currentTimeMillis();
m = new BigInteger(1, rand);
end = System.currentTimeMillis();
System.out.println("random number generation time was " + (end - start) + " ms.");
 
for(int i = 1; i <= 10; i++){
	m = null;
 
	start = System.currentTimeMillis();
 
	m = new BigInteger(512, Integer.MAX_VALUE ,rand);
 
	end = System.currentTimeMillis();
 
	time += (end-start);
	System.out.println("random number " + i + " generation time was " + (end - start)+ " ms.");
 
	}
System.out.println("random number generation time was " + time + " ms. Average = " + (time/10) + " ms");

Voici les résultats

random number generation time was 5003 ms.
random number 1 generation time was 118 ms.
random number 2 generation time was 88 ms.
random number 3 generation time was 145 ms.
random number 4 generation time was 93 ms.
random number 5 generation time was 179 ms.
random number 6 generation time was 491 ms.
random number 7 generation time was 87 ms.
random number 8 generation time was 65 ms.
random number 9 generation time was 49 ms.
random number 10 generation time was 385 ms.
random number generation time was 1700 ms. Average = 170 ms


Aucune idée?

merci d'avance

[Logan Mauzaize]

Je dirais que c'est l'initialisation de ton "randomiser" qui prend du temps.

D'après Wikipedia :

Une méthode courante pour générer de l'aléa en cryptographie consiste à « accumuler de l'entropie » (via diverses sources disponibles sur un ordinateur : temps entre deux accès au disque, taille de la mémoire, mouvements du pointeur de la souris...) et à faire passer le résultat dans une fonction de hachage cryptographique comme MD5 ou SHA-1. Ce principe est utilisé par Yarrow et Fortuna qui ne génèrent un nombre que lorsque l'entropie est suffisante.

[tchize_]

C'est mon avis aussi, tu commence au 10ème à manque d'entropie et il faut du temps pour que ton système en génère correctement. Par exemple ici, pendant que j'écrit ce message, j'ai lancé la commande "dd if=/dev/random of=/dev/null" sous linux. Sur 30 secondes approximativement de fonctionnement, elle a pu générer 120 octets de hasard entropique, pas énorme

Code :

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

1
2
3
4
$ dd if=/dev/random of=/dev/null bs=1
^C120+0 enregistrements lus
120+0 enregistrements écrits
120 octets (120 B) copiés, 28,3403 s, 0,0 kB/s

[tchize_]

edit: je viens de tester ton code, j'obtiens ce genre de résultat

Code :

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
random number 496 generation time was 42 ms.
random number 497 generation time was 140 ms.
random number 498 generation time was 26 ms.
random number 499 generation time was 26 ms.
random number 500 generation time was 21 ms.
random number 501 generation time was 38 ms.
random number 502 generation time was 38 ms.
random number 503 generation time was 27 ms.
random number 504 generation time was 79 ms.
random number 505 generation time was 48 ms.
random number 506 generation time was 67 ms.
random number 507 generation time was 16 ms.
random number 508 generation time was 16 ms.
random number 509 generation time was 18 ms.
random number 510 generation time was 27 ms.
random number 511 generation time was 138 ms.

La javadoc ne parle pas d'utiliser l'entropie. Par contre, les restrictions sur l'output peuvent impliquer des calculs plus ou moins long, ce qui expliquerait les variations de temps.

[tchize_]

visiblement, je lit pas tout, c'est ton premier nombre qui est lent. Pas de comportement similaire ici:

Code :

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

1
2
3
4
5
random number generation time was 27 ms.
random number 1 generation time was 453 ms.
random number 2 generation time was 51 ms.
random number 3 generation time was 25 ms.
random number 4 generation time was 25 ms.

Par contre le premier appel est "jsute aléatoire" et les suivant sont des "probablement premiers", ce qui n'est pas la meme chose. Je pencherais plutot sur le temps d'initialisation de ton générateur aléatoire.

[charles_dg]

visiblement, je lit pas tout, c'est ton premier nombre qui est lent. Pas de comportement similaire ici:

Code :

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

1
2
3
4
5
random number generation time was 27 ms.
random number 1 generation time was 453 ms.
random number 2 generation time was 51 ms.
random number 3 generation time was 25 ms.
random number 4 generation time was 25 ms.

Par contre le premier appel est "jsute aléatoire" et les suivant sont des "probablement premiers", ce qui n'est pas la meme chose. Je pencherais plutot sur le temps d'initialisation de ton générateur aléatoire.

5 sec. me semble énorme chez moi pour l'initialisation d'un générateur non?

[charles_dg]

edit: je viens de tester ton code, j'obtiens ce genre de résultat

Code :

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
random number 496 generation time was 42 ms.
random number 497 generation time was 140 ms.
random number 498 generation time was 26 ms.
random number 499 generation time was 26 ms.
random number 500 generation time was 21 ms.
random number 501 generation time was 38 ms.
random number 502 generation time was 38 ms.
random number 503 generation time was 27 ms.
random number 504 generation time was 79 ms.
random number 505 generation time was 48 ms.
random number 506 generation time was 67 ms.
random number 507 generation time was 16 ms.
random number 508 generation time was 16 ms.
random number 509 generation time was 18 ms.
random number 510 generation time was 27 ms.
random number 511 generation time was 138 ms.

La javadoc ne parle pas d'utiliser l'entropie. Par contre, les restrictions sur l'output peuvent impliquer des calculs plus ou moins long, ce qui expliquerait les variations de temps.

Ok, tu as aussi le premier nombre à générer qui te prend plusieurs secondes? La je regarde dans SecureRandom, si la méthode setSeed(byte[] seed) peut m'aider à contourner ce problème de temps.

Par contre ton exécution est bien plus rapide que la mienne. Du à de la programmation sur javacard, j'ai du installer windows en dualboot (bootcamp) sur mon portable mac.

[tchize_]

une javacard est loin d'etre aussi puissante qu'un CPU, attendez vous à ce que le générateur soit lent

Pour le reste voir nos messages qui se sont croisés

[Logan Mauzaize]

L'implémentation par défaut semble être sun.security.provider.SecureRandom.

D'après une doc (je suppose plus ou moins officielle) :

Note that if a seed is not provided, we attempt to provide sufficient seed bytes to completely randomize the internal state of the generator (20 bytes). However, our seed generation algorithm has not been thoroughly studied or widely deployed.

This empty constructor automatically seeds the generator. We attempt to provide sufficient seed bytes to completely randomize the internal state of the generator (20 bytes). Note, however, that our seed generation algorithm has not been thoroughly studied or widely deployed.

The first time this constructor is called in a given Virtual Machine, it may take several seconds of CPU time to seed the generator, depending on the underlying hardware. Successive calls run quickly because they rely on the same (internal) pseudo-random number generator for their seed bits.

source