J´ai un petit travail à effectuer pour l´école et j´ai besoin de petits renseignements.
Je recopie un texte trouvé sur Internet : (j´ai uniquement un problème de compréhension sur la remarque finale)

----------------------------------------------
formule de récurence : x(n+1)=a*x(n)+c modulo(m)

Condition nécessaire et suffisante pour que la suite de termes renvoyée par un générateur linéaire congruentiel décrive un cycle sur l´ensemble des valeurs de [[0 , M-1]] :

Il faut et il suffit que :
1. c soit premier avec m.
2. pour tout p entier naturel premier, si p divise M alors p doit diviser (a-1).
3. si M est divisible par 4, alors 4 doit diviser (a-1).

Remarque : Pour m = 2^k, il suffit donc que c soit impair, mais il est encore plus facile est d’assurer cette condition si m est premier. Pourtant, On choisit souvent m = 2^k où k est le nombre de bits dans un entier standard car ainsi, l’opération module est gratuite.

------------------------------------------------

Je comprend mal "l’opération module est gratuite".

Prenons par exemple m=32.

Prenons n un entier. n s´écrit en binaire :
n=a(u+1)a(u)...a(2)a(1)a(0) (quelquesoit i, a(i)=0 ou 1)

donc pour avoir son écriture en base 10 :

n=sum[(a(k)*2^k),k=0..u] (somme des ak*2^k où k varie de 0 à u) où les ak sont des entiers dans {0,1} et u un entier.

donc on en déduit n modulo 32 :
n mod(32)=sum(a(k)*2^k,k=0..31)
autrement dit on obient en écriture binaire :
n mod(32)=a(31)a(30)....a(1)a(0)

mais en quoi cette opération est "gratuite" ?
en gros cela reviens à une troncature, donc si j´ai bien compris l´ordinateur va calculer a*x(n)+c, puis comme la taille du nombre sera trop grande pour le type entier "standard", il va lui même ne garder que le début (ce qui revient à faire modulo m=32)

Cela se passe-t-il toujours comme ca ? ne peut-on pas envisager des cas où l´ordinateur ne garderait par exemple que la fin du nombre ?

un bien long post, pour une si petite question, ceci uniqument dans un soucis de clarté.

merci.

Sur une machine 32 bits, les entiers font 32 bits.
Si tu fais 2^32 -1 +1 tu obtiens 0.

Si m= 2^32, tu n´as pas besoin de faire 2^32 puisque c´est automatiquement fait par ton processeur qui ne retient toujours que les 32 bits de poids faible

en clair, lorsque tu crois que ton proceseur fait des calcul normaux, il fait en réalité toujours (ou générallement) des calcul modulo 2^32. Donc tout est calcul se fait modulo 2^32, ce qui fait que tu n´a pas besoin d´une opération de plus pour avoir le résultat, c´est le mode par défaut de calcul.

a... d´accord. Donc finalement c´est bien une troncature du nombre : le processeur ne garde que les 1ers chiffres qu´il peut contenir en mémoire.

godrik -> qu´entends-tu par "poids faible", c´est une expression que j´ai souvent lu dans mes recherches, mais sans pouvoir mettre une réelle définition dessus : je pense que ce sont les premiers chiffres du nombre, c´est bien ca ?

Poids fort, poids faible sont le poids des bits du format de calcul. Prenons un exemple de format 8 bit

d7 d6 d5 d4 d3 d2 d1 d0

d7 est le bit codant le nombre le plus élevé, soit le poids fort. Il vaut soit 2^7=128 soit 0. On le nomme en Anglais MSB.

d0 est le bit codant le nombre le plus faible, soit le poids fort. Il vaut soit 2^0 = 1 soit 0. On le nomme en anglais LSB.

Correction du post précédent :

Poids fort, poids faible sont le poids des bits du format de calcul. Prenons un exemple de format 8 bit

d7 d6 d5 d4 d3 d2 d1 d0

d7 est le bit codant le nombre de pondération le plus élevé, soit le poids fort. Il vaut soit 2^7=128 soit 0. On le nomme en Anglais MSB.

d0 est le bit codant le nombre de pondération le plus faible, soit le poids faible. Il vaut soit 2^0 = 1 soit 0. On le nomme en anglais LSB.

c´est bien ce qu´il me semblait, merci pour ces précisions