Alors, commençons par poser les définitions :
-
https://fr.wikipedia.org/wiki/Key_signing_party
-
http://www.bortzmeyer.org/pgp-session.html
Rappel de l'algorithme des deux rangées (source :
http://www.bortzmeyer.org/pgp-session.html) :
« Il reste à vérifier les identités des participants. Un algorithme simple serait que chacun vérifie successivement l'identité de chacun. C'est ainsi qu'on procédait autrefois. Mais cet algorithme est en o(n^2). On utilise désormais un algorithme parallèle. Les participants sont rassemblés en deux rangs qui se font face à face, chacun vérifie l'identité de son vis-à-vis. Puis on se décale d'un cran, avec passage des personnes d'extrémité dans l'autre rang, et on recommence (en essayant de ne pas éclater de rire devant le joli ballet que ça représente). »
Pour un nombre impairs de personnes, c'est facile et ça marche out-of-box. Ici, avec 5 participants à notre signing party :
1 2 3
4 5
----------
2 3 5
1 4
----------
3 5 4
2 1
----------
5 4 1
3 2
----------
4 1 2
5 3
----------
1 2 3
4 5
Condition d'arrêt : chaque personne revient à sa place initiale.
Donc, on a les combinaisons :
1 - 4
2 - 5
----------
2 - 1
3 - 4
----------
3 - 2
5 - 1
----------
5 - 3
4 - 2
----------
4 - 5
1 - 3
Donc :
1 a vu : 2 (2e étape), 3 (dernière étape), 4 (1ère étape), 5 (3e étape)
2 a vu : 1 (2e étape), 3 (3e étape), 4 (4e étape), 5 (1ère étape)
3 a vu : 1 (dernière étape), 2 (3e étape), 4 (2e étape), 5 (4e étape)
4 a vu : 1 (1ère étape), 2 (4e étape), 3 (2e étape), 5 (dernière étape)
5 a vu : 1 (3e étape), 2 (1ère étape), 3 (4e étape), 4 (dernière étape)
Conclusion : tout le monde a vu tout le monde et peut donc vérifier l'identité de tout le monde.
Par contre, avec un nombre pair de participants, ça ne marche pas :
1 2 3
4 5 6
----------
2 3 6
1 4 5
----------
3 6 5
2 1 4
----------
6 5 4
3 2 1
----------
5 4 1
6 3 2
----------
4 1 2
5 6 3
----------
1 2 3
4 5 6
Des personnes ne se sont pas vues : 1 - 3, 1 - 5, 1 - 7 pour ne citer qu'elles. Et pire, les mêmes personnes se sont vues plusieurs fois.
On se dit alors que l'on peut tenter de revenir à une solution connue : pas le même nombre de personnes dans chaque rangée :
1 2 3 4
5 6
On remarque un décalage de deux personnes obligatoirement. Je vous laisse résoudre : ça ne marche pas.
On peut exclure une personne de la signing party mais c'est dommage. :D On peut ajouter une personne et ça c'est mieux. Mais pas facile à trouver.
Finalement, la solution qui marche (on déplace d'un demi cran à chaque fois : ne pas faire changer de rang les personnes tout de suite) :
1 2 3
4 5 6
1 2 3
4 5 6
2 3 6
1 4 5
2 3 6
1 4 5
3 6 5
2 1 4
2 6 5
2 1 4
6 5 4
3 2 1
Condition d'arrêt : 1 et 6 ont échangées leur place dans les diagonales.
Donc, on a les combinaisons :
1 - 4
2 - 5
3 - 6
----------
2 - 4
3 - 5
----------
2 - 1
3 - 4
6 - 5
----------
3 - 1
6 - 4
----------
3 - 2
6 - 1
5 - 4
----------
6 - 2
5 - 1
Donc :
1 a vu : 2 (3e étape), 3 (4e étape), 4 (1ère étape), 5 (dernière étape), 6 (5e étape)
2 a vu : 1 (3e étape), 3 (5e étape), 4 (2e étape), 5 (1ère étape), 6 (dernière étape)
3 a vu : 1 (4e étape), 2 (5e étape), 4 (3e étape), 5 (2e étape), 6 (1ère étape)
4 a vu : 1 (1ère étape), 2 (2e étape), 3 (3e étape), 5 (5e étape), 6 (4e étape)
5 a vu : 1 (dernière étape), 2 (1ère étape), 3 (2e étape), 4 (5e étape), 6 (3e étape)
6 a vu : 1 (5e étape), 2 (dernière étape), 3 (1ère étape), 4 (4e étape), 5 (3e étape)
Conclusion : tout le monde a vu tout le monde et peut donc vérifier l'identité de tout le monde.
Merci à lulu pour la solution qui fonctionne. :)