Discussion:Blum Blum Shub
- Admissibilité
- Neutralité
- Droit d'auteur
- Article de qualité
- Bon article
- Lumière sur
- À faire
- Archives
- Commons
Cet article est indexé par le projet Cryptologie.
Les projets ont pour but d’enrichir le contenu de Wikipédia en aidant à la coordination du travail des contributeurs. Vous pouvez modifier directement cet article ou visiter les pages de projets pour prendre conseil ou consulter la liste des tâches et des objectifs.
| Avancement | Importance | pour le projet | |
|---|---|---|---|
| Bon début | Élevée |  | Cryptologie (discussion • critères • liste • stats • hist. • comité • stats vues) |
Cet article ne comporte pas de liste de tâches suggérées. Vous pouvez saisir une liste de tâches à accomplir (par exemple sous forme d'une liste à puces), puis sauvegarder. Vous pouvez aussi consulter la page d'aide.
Quid de la longueur du cycle en fonction des nbs premiers et de la valeur initiale, x0 ?
modifierVisiblement il manque dans l'article ce que doit être la valeur initiale (x0) relativement à p et q (les 2 nbs premiers).
De simple petits tests donnent, pour exemples, pour la suite (xo, p,q) :
- (3, 11,19) = 3, 9, 81, 82, 36, 42, 92, 104, 157, 196, 169, 137, 168, 9, 81, 82, 36, 42, 92, 104, 157, 196, 169, 137, 168, 9, 81, 82, 36, 42, un cycle de 12 nombres
- (1234567, 11, 19) = 4, 16, 47, 119, 158, 93, 80, 130, 180, 5, 25, 207, 4, 16, 47, 119, 158, 93, 80, 130, 180, 5, 25, 207, 4, 16, 47, 119, 158, 93, qui a un cycle de 12 nombres.
Bref, savez-vous pour quelles valeurs x0, p et q la suite engendre une suite pseudo-aléatoire ayant un cycle long, et ce que l'on sait de la longueur de ce cycle relativement à x0, p et q ?
--Epsilon0 ε0 29 décembre 2013 à 22:34 (CET)
oui effectivement j'appuie cette demande , ainsi que des éléments de dimensionnement pour assurer une sécurité suffisante (quelles précos) ? j'ai fait quelques tests de cyclicité j'obtiens des résultats assez étranges par exemple avec p = 2207 et q = 4703 et x0 = 72832
j'ai p = 551 x 4 + 3 et q = 1175 x 4 + 3
donc p et q sont bien de forme 4k+3
on vérifie que M et x0 sont bien premiers entre eux enfin le PGCD de p-1 et q-1 = 2 donc les conditions de la définition sont remplies
pour ces paramètres p, q et x0, ma durée de cycle est de 47 seulement. Elle est statistiquement de 1363 si je change de graine
j'ai travaillé avec des paramètres certes petits, mais pour "sentir" l'accroissement de mes cycles au fur et à mesure que j'augmente mes valeurs de paramètres il y a de la littérature sur le sujet qui permet sans doute de répondre à ces interrogations, par exemple ce pdf http://www.cs.miami.edu/home/burt/learning/Csc609.062/docs/bbs.pdf et celui là https://www.win.tue.nl/~berry/papers/ima05bbs.pdf mais comme je suis loin d'être spécialiste, ça va me prendre un moment avant de me faire une idée
--- EDIT ---
j'ai regardé un peu plus en profondeur la relation entre M et la longueur du cycle.
alors modulo quelques conditions encore mystérieurses, mais la relation "pourrait" être linéaire, ce qui effectivement permet d'obtenir rapidement des cycles de longueur on va dire quasi-infinie d'un point de vue procédural. Evidemment si je veux aller chercher le ième élément c'est une autre histoire au cas où quelqu'un en éprouve le besoin...
toujours est il que cette relation n'est pas remplie pour tous les nombres M. Pour certains nombres M, la cyclicité est bien trop faible. Il doit donc à mon sens manquer une conditio sur M dans la définition, autre que produit de deux nombres premiers de la forme 4k+3 donc le pgcd des indicatrices d'Euler est "faible" — Le message qui précède, non signé, a été déposé par l'IP 89.83.239.206 (discuter), le 21 novembre 2019 à 00:14 (CET)
EDIT n°2 ----
après quelques approfondissement, il apparait qu'il y a une relation qui relie la longueur du cycle à lambda(lambda(M)) où lambda est l'indicatrice de Carmichael j'avais effectivement remarqué cette similitude entre les courbes mais j'ai effectivement eu confirmation par exemple ici
j'ai commencé à étudier cette histoire d'ordre, et j'ai effectivement remarqué une très forte corrélation entre la longueur des cycles et le nombre de facteurs premiers de p-1 et q-1
cela dit, la seule connaissance du nombre de facteur ne fournit qu'un indicateur grossier du nombre de cycle, manifestement il faut s'intéresser à chaque diviseur l de (p-1).(q-1) pour en tirer un ordre de grandeur de la longueur du cycle.
j'ai été jeté un oeil aux wikis dans d'autres langues, il ne sont guère plus avancé ils tiennent à préciser que Phi(p) = p-1 et Phi(q) = q-1 donc ça pourrait être une petite modif à passer ? — Le message qui précède, non signé, a été déposé par l'IP 2A04:CEC0:1099:840:40EC:3CE6:269D:608A (discuter), le 27 novembre 2019 à 18:57 (CET)
— Le message qui précède, non signé, a été déposé par l'IP 77.157.180.59 (discuter), le 19 novembre 2019 à 14:27 (CET)
EDIT n°3 -------
il y avait une erreur dans l'article j'ai donc fini par corriger en fait la condition pour un cycle long c'est que le pgcd de phi(p-1) et de phi(q-1) doit être petit et pas phi(p) et phi(q) cela dit l'erreur est sans doute un copier coller depuis la page en anglais
évidemment il est bcp plus difficile de calculer phi(p-1) que phi(p) avec p premier... je crois pas qu'il existe des algorithmes vraiment efficaces