Casser un GCL

Générateur

m = 2^15 - 1;

\(\(gcl[x_] := 
        Module[{a = 143, b = 532}, 
Mod[a\ x + b, 
            m]
];\)\)

suite = {234};
n = 10;
For[i = 2, i <= n, 
        AppendTo[suite, 
          gcl[Last[suite]]]; i++];
suite

cas 1: m connu

y = {};
For[i = 1, i < 3, 
        diff = AppendTo[y, 
            suite[[i + 1]] - 
              suite[[i]]]; i++];
y

a = 
        Mod[y[[2]]*PowerMod[y[[1]], -1, m], 
          m];
b = 
        Mod[suite[[2]] - a*suite[[1]], 
          m];
Print["a=", a, "    b=", b]

cas 2: m inconnu

Méthode de (Madame) Plumstead-Boyar

y = {};
For[i = 1, i < n, 
        y = AppendTo[y, 
            suite[[i + 1]] - 
              suite[[i]]]; i++];
y

Si le résultat ci-dessous est > 1, il faut prendre plus de termes.

GCD[y[[1]], y[[2]], y[[3]], y[[4]], y[[5]], 
      y[[6]]]

Le PGCD étendu ExtendedGCD[m, n] renvoie une liste{g, {r, s}} dans laquelle g est le plus grand commun diviseur de m et n, et r et s sont des entiers tels que g=r·m+s·n (identité de Bezout). Le PGCD étendu permet de trouver les solutions entières des équations diophantiennes linéaires.

coeff = 
      ExtendedGCD[y[[1]], y[[2]], y[[3]], y[[4]], y[[5]], 
        y[[6]]]
c = coeff[[2]];
long = Length[c];
a = 0;
For[i = 1, i <= long, 
        a += c[[i]]*
            y[[i + 1]]; i++];
a

yy = {Infinity};
aa = {a};
mm = {Infinity};
i = 2;
While[
        i == 2 || 
          mm[[i - 1]] ≠ mm[[i - 2]], 
{If[
            i > 2, AppendTo[yy, 
              Mod[aa[[i - 1]]*y[[i - 1]], mm[[i - 1]]]], 
            AppendTo[yy, 
              aa[[i - 1]]*diff[[i - 1]]]]; 
If[
            i > 2, AppendTo[mm, 
              GCD[mm[[i - 1]], yy[[i]] - y[[i]]]], 
            AppendTo[mm, 
              yy[[i]] - y[[i]]]]; 
AppendTo[aa, 
            Mod[aa[[i - 1]], 
              mm[[i]]]];
}; 
i++];
mmm = Last[mm];
a = Last[aa];
b = 
        Mod[suite[[2]] - a*suite[[1]], 
          mmm];
Print["m=", mmm, "  a=", a, "  b=", b]