Bonjour à tous et à toutes,

Je souhaite intégrer l'algorithme de BBS à un cryptosystème.

L'algorithme étant très simple, j'ai donc souhaité l'analyser un peu, sur des paramètres certes petits mais qui m'amènent à quelques interrogations.

tout l'intérêt de BBS est sa cyclicité élevé, c'est à dire que la suite de bit ne se répète pas avant longtemps.

j'ai donc voulu m'assurer de la grande cyclicité et donc calculé mes longueurs de cycles pour des nombres RSA jusqu'à 100 000. C'est peux j'en conviens mais ça me donne déjà un aperçu...

j'ai donc pris soin de bien restreindre mes paramètres avec les bons critères, le nombre RSA "M" produit de deux nombres premiers de la forme 4k+3, et pgcd des indicatrices d'euler de p et q petit (j'ai retenu les 2, et les 6)

enfin je me suis assuré que ma graine était bien première avec M (en fait j'ai tester avec plusieurs graines parce que j'ai également des effets chelous sur certaines graines, où la cyclicité s'effondre également donc je dois avoir une pièce manquante au puzzle de ce côté là aussi mais passons, car la majorité des graines colle bien au cycle max)

dans la plupart des cas, j'observe une relation linéaire entre la longueur du cycle, et la valeur de mon nombre RSA (le M du modulo)


sauf que pour certains M, et bien la cyclicité devient très mauvaise.


Nom : longueur_cycle.jpg
Affichages : 64
Taille : 58,7 Ko

en bleu lorsque le pgcd des indicatrices d'euler de p et q vaut 2 (on peut pas faire moins^^) et en orange quand il vaut 6
bêtement, comme p et q sont premiers, leurs indicatrices d'Euler valent respectivement p-1 et q-1
je précise en abscisse ma valeur de M (nombre RSA produit de p et q) et en ordonnée la longueur de mon cycle max (obtenu sur la plupart d'un échantillon de graines, j'oublie les graines qui déconnent à ce stade)

bref on voit bien que pour pas mal de point, ma cyclicité s'effondre...

donc ok je peux me dire que c'est qu'un effet du fait que je travaille avec des paramètres ridiculement petit, et que ça va s'estomper si j'augmente la valeur des paramètres, mais ça va être de plus en plus compliqué à vérifier, parce que je pourrai pas calcul des cycles de longueurs démesurés, vu que le temps de calcul d'un cycle est proportionnel à sa longueur... vous voyez ce que je veux dire (à moins que quelqu'un connaisse une technique magique pour calculer une longueur de cycle en tant plus court mais intuitivement ça me ferait mal)

bref, j'ai l'impression ou qu'il me manque une condition, alors ça veut dire que je vais devoir approfondir de la littérature mathématique et harceler des chercheurs pour comprendre, ou alors plus bêtement j'ai travaillé avec des paramètres trop petits pour pouvoir me prononcer...


voilà donc je sais pas s'il y a des gens un peu calé dans ce domaine par ici

merci beaucoup,
Gorz