Prüfen ob Wert teil eines LFSR

[Vincent H. (vinci)]

Guten Abend

Ich hab in einem VHDL Kurs unter anderem die Aufgabenstellung ein LFSR 
mit einem gegebenen Feedback-Polynom zu realisieren. Den Code hatte ich 
relativ schnell runter getippt und er funktioniert auch, lediglich eine 
Theorie-Frage bezüglich dem LFSR bereitet mir ein wenig Kopfschmerzen.

Ich soll prüfen, ob eine gewisse Zahl vom LFSR ausgegeben wird.

Konkret lautet das Polynom x^28 + x^3 + 1
Zu prüfen gilt, ob 0x2b0638b als Ausgabe vorkommt.
Als Resetwert wird das LFSR mit lauter 1ern beladen.

Woher weiß ich nun, ob 0x2b0638b vorkommt?

Grüße
Vincent

[Chris L. (chk1987)]

nach jedem schiebevorgang die folge mit diesem wert vergleichen...

[Vincent H. (vinci)]

Die Aufgabenstellung ist eine Theoriefrage. Ich bezweifle stark, dass 
der Lektor von uns verlangt einen 28Bit breiten Vektor händisch 
durchzuschieben, bis wir den gesuchten Wert erreichen...

In meiner Simulation wird der Wert trotz 100MHz Takt erst nach ~2,4s 
erreicht. Das wäre also wohl eine Lebensaufgabe.

[Detlef _. (detlef_a)]

Vincent Hamp schrieb:

>>Ich bezweifle stark, dass
> der Lektor von uns verlangt einen 28Bit breiten Vektor händisch
> durchzuschieben, bis wir den gesuchten Wert erreichen...

Kann man ja einen Rechner machen lassen. Der Wert 0x2b0638b wird 
erreicht und zwar nach 358655852 Runden.

> In meiner Simulation wird der Wert trotz 100MHz Takt erst nach ~2,4s
> erreicht. Das wäre also wohl eine Lebensaufgabe.

Meine desktop Gurke braucht für die komplette Lösung nen paar Sekunden. 
Das Polynom produziert allerdings keine maximum length sequence 
http://de.wikipedia.org/wiki/Maximum_Length_Sequence. MLS bis 168er 
Ordnung gibts hier:
http://www.xilinx.com/support/documentation/application_notes/xapp052.pdf

allerdings mit 0 als Startwert und XNOR Rückkopllung.

> Die Aufgabenstellung ist eine Theoriefrage.

Dann würde mich die Lösung dazu sehr interessieren. Ich bin leider nicht 
in der Lage zu bestimmen, ob ein Polynom eine MLS liefert oder nicht 
(außer duch Probieren, das geht aber bei z.B. 168er Ordnung nicht mehr).

math rulez!
Cheers
Detlef

PS. Ich hoffe, dass ich mich nicht verdaddelt habe, ist aber nicht 
auszuschließen.


/*******************************************************************/
int main(int  argc , char ** argv)
/*******************************************************************/
{
   unsigned char *f,c;
   unsigned long k,p;

f=(char *)malloc(1<<26);
if(f==NULL){printf("geht nich \n"); return;}

for(k=0;k<(1<<26);k++) {
  if((k&((1<<16)-1))==0) printf("%d \n",k);
  f[k]=0;
}

p=0xffffffff;

for(k=0;k<(1<<29);k++) {
  if((k&((1<<19)-1))==0) printf("%d \n",(1<<29)-k);
  p=p&((1<<29)-1);
  if(p==0x2b0638b) { printf("yo %d %x %x \n",k,p,f[p>>3]); return;}
  c=f[p>>3]&(unsigned char)(1<<(p&7));
  if(c) { printf("gibbs schon %d %x %x \n",k,p,f[p>>3]); return;}
  f[p>>3] |= (unsigned char)(1<<(p&7));
  p = (p<<1)|(((p>>28)&1)^((p>>3)&1));
}

for(k=0;k<(1<<26);k++) {
  if((k&((1<<16)-1))==0) printf("%d \n",k);
  //if(f[k] != 0xff)
  printf("xxxxxxxxxxxxxxxxxxxx %d %x \n",k,f[k]);
}
return 0;
}

[Vincent H. (vinci)]

Hallo

Danke für deine Antwort.
Die Xilinx Note hab ich auch bereits gelesen.

Weiters hab ich dann folgendes Dokument entdeckt:
http://jaja.kn.vutbr.cz/~kajan/lfsr.pdf

Interessanterweise gibt es da eine Tabelle, in der 28 und 3 als 
"Polynomial 1-Terms (Xn)" sehr wohl gelistet ist. Kurz dacht ich dann, 
dass XOR und XNOR Verknüpfungen unterschiedliche Polynome erfordern... 
das dürft aber leider auch nicht der Fall sein:
"The polynomial used to generate the maximum length sequence is the same 
for
Fibonacci/Galois implementations, and with XOR or XNOR gates for 
feedback."

Jetzt bin ich beim Überfliegen des Dokuments nicht wirklich schlau 
geworden, was der Tabelleneintrag "Polynomial 1-Terms (Xn)" überhaupt 
ist...


Hab meine Antwort aber vorerst mal so begründet, dass 28/3 sehr wohl MSL 
taps sind, sonst wär die Frage imho nicht zu beantworten.

[Klakx (Gast)]

mal andersrum gefragt:
wenn die bitbreite ausreicht, wird dann nicht alles irgendwann  beim 
LSFR erreicht? hab leider auch keine gescheite quelle gefunden

[Klakx (Gast)]

natürlich außer 0

[Vincent H. (vinci)]

Also mein Wissen hier is auch sehr lückenhaft, jedoch weiß ich, dass ein 
LFSR ausschließlich in Kombinationen mit den richtigen Feedback Taps 
(bzw. dem richtigen Feedback Polynom) eine sogenannte Maximal Sequence, 
sprich 2^n-1 states annimmt.

Was ich bisher so mitbekommen hab gibt es aber für jede Bitbreite 
etliche "richtige" Feedback Taps, die dieses Maximum erzeugen.

/edit
Hier eine der bisher besten Seiten, die ich diesbezüglich ergoogled hab:
http://www.newwaveinstruments.com/resources/articles/m_sequence_linear_feedback_shift_register_lfsr.htm

/edit2
Abhängig von der Art der Verknüpfung (XOR / XNOR) kann auch ein mit 
lauter 1ern befülltes LFSR ein gelockter State sein.

[Detlef _a (Gast)]

Es gibt jeweils einen gelockten state, bei XOR feedback alles 0, bei 
XNOR alles 1. Dass die Polynome für XOR/XNOR und Galois/Fibonacci 
feedback gleich sind war mir nicht bewußt, muß man mal ausprobieren.

Ich hatte allerdings die Liste mißverstanden, die beginnen die Zählung 
der Register bei 1, nicht bei 0, bei Deinem Polynom gibts also nur 28 
Stellen und nicht 29, wie ich angenommen hatte. Als Länge der MLS wird 
im neueren Xilinx Dokument für n=28 auch 268435455 angegeben, das sind 
2^28-1.

Ich werde das Programm nochmal modden müssen.

Wenn Xilinx sagt, dass das Polynom ne MLS produziert, wird das stimmen. 
Also lautet die Antwort auf die Originalfrage: ja, 0x2b0638b kommt vor, 
genauso wie jede andere Zahl aus dem Feld mit Ausnahme der 0.

Gerne würde ich wissen wie man bestimmt, ob ein Polynom eine MLS 
erzeugt. Lieber noch würde ich für eine gegebene MLS Länge das Polynom 
erzeugen können, ich glaube aber, das geht nur durch Probieren.

Gute Nacht
Detlef

[Lattice User (Gast)]

Detlef  _a schrieb:
> ich glaube aber, das geht nur durch Probieren.

Da irrst du dich.

Eines der grössten bekannten Polynome das eine MLS erzeugt ist:

x^6972593 + x^3037958 + 1 (*)

und das hat man garantiert nicht mit probieren gefunden :-)

Eine Xilinx App Note verlinkt eine Tabelle die bis zum Grad 168 geht, 
auch das ist viel zu gross zum Durchprobieren.

(*) The Great Trinomial Hunt (Richard P. Brent, Paul Zimmermann)

[Detlef _a (Gast)]

Yo, Du hast Recht, aber wie gehts denn sonst, das Finden und 
Verifizieren, hast Du einen Hinweis wo was zu finden ist? Die Xilinx 
Appnote hatte ich selber zitiert.

Cheers
Detlef

[Lattice User (Gast)]

Detlef _a schrieb:
> Yo, Du hast Recht, aber wie gehts denn sonst, das Finden und
> Verifizieren, hast Du einen Hinweis wo was zu finden ist?


Stichwort ist "primitive polynomal"

http://mathworld.wolfram.com/PrimitivePolynomial.html
http://en.wikipedia.org/wiki/Primitive_polynomial_%28field_theory%29
http://en.wikipedia.org/wiki/Euler%27s_totient_function

[Hagen R. (hagen)]

bzw.

"irreducible and primitive polynom"


falls du was mit PASCAL Code anfangen kannst hier mein Source:

Gruß Hagen

{ follow procedures create and check suitable Polynoms for above
  Linear Feedback Shift Registers.
  Such polynoms must be primitive, irreducible to produce maximal
  length LFSR's. }


type
  TFactors = array[0..6] of Cardinal;

function FactorOrder(var Factors: TFactors; Degree: Integer): Integer;
// find factors of 2^Degree-1 = possible Order of Polynom
// can be surrely more optimized, but the runtime here is not important yet
// as example:
//   For all orders from 2^0 -1 upto 2^32-1 exists only 33 possible primefactors.
//   Instead to looping trough all odd numbers as factors we could reduce the
//   loopcount if we use a lookuptable of all the 33 possible primefactors.
var
  Order,Rest,Prime,Bound,Factor,LastFactor: Cardinal;
begin
  Result := 0;
  LastFactor := 0;
  Prime := 3;
  Order := $FFFFFFFF shr (32 - Degree);
  Rest := Order;
  Bound := Round(Sqrt(Rest));
  while (Rest <> 1) and (Prime < Bound) do
    if Rest mod Prime = 0 then
    begin
      Rest := Rest div Prime;
      Factor := Order div Prime;
      if Factor <> LastFactor then
      begin
        LastFactor := Factor;
        Factors[Result] := Factor;
        Inc(Result);
      end;
      Bound := Round(Sqrt(Rest));
    end else Inc(Prime, 2);
  if Result > 0 then
  begin // only if 2^Degree-1 it self isn't prime
    Factors[Result] := Order div Rest;
    Inc(Result);
  end;
end;

function PolyIsPrimitive(Poly: Cardinal; Degree: Integer; const Factors: TFactors; FactorCount: Integer): Boolean;
// small, clean and efficient for small Degrees upto 32
// for larger Degrees we should go with real GF(2) arithmetic
type
  TPolyMatrix = array[0..31] of Cardinal;

  procedure PolyCopy(var D: TPolyMatrix; const S: TPolyMatrix);
  {$IFDEF ASM}
  asm
         XCHG  EAX,EDI
         XCHG  EDX,ESI
         MOV   ECX,32
         REP   MOVSD
         MOV   EDI,EAX
         MOV   ESI,EDX
  end;
  {$ELSE}
  begin
    Move(S, D, SizeOf(S));
  end;
  {$ENDIF}

  procedure PolyInit(var M: TPolyMatrix; Poly: Cardinal; Degree: Integer);
  var
    L: Cardinal;
    I: Integer;
  begin
    L := $80000000;
    M[Degree -1] := L;
    for I := 0 to Degree -2 do
    begin
      L    := L shr 1;
      M[I] := L;
    end;
    for I := 0 to Degree -2 do
    begin
      if Odd(Poly) then M[I] := M[I] or $80000000;
      Poly := Poly shr 1;
    end;
  end;

  procedure PolyMul(var R: TPolyMatrix; const M: TPolyMatrix; Degree: Integer);
  {$IFDEF ASM}
  // speedup >40% over all, and of course follow asm is nothing important or special tricky
  asm
         PUSH  EDI
         PUSH  ESI
         PUSH  EBX                       
         PUSH  EBP
         LEA   EDI,[EAX + ECX * 4]  // on top of R, eg @R[Degree]
         LEA   ESI,[EDX + ECX * 4]  // on top of M
         NEG   ECX                  // -Degree, we loop from -Degree upto 0
         MOV   EBP,ECX
  @@1:   MOV   EDX,[ESI + EBP * 4]  // outerloop
         XOR   EAX,EAX
         PUSH  ECX                  // save -Degree, eg. loopcounter
  @@2:   ADD   EDX,EDX              // inner loop, branchfree xor'ing is important for speed
         SBB   EBX,EBX
         AND   EBX,[EDI + ECX * 4]
         XOR   EAX,EBX
         INC   ECX
         JNZ   @@2
         POP   ECX                  // restore loopcounter
         INC   EBP
         PUSH  EAX                  // push T[] on stack
         JNZ   @@1
         SUB   EDI,4
  @@3:   POP   DWord Ptr [EDI]      // R[] = T[]
         SUB   EDI,4
         INC   ECX
         JNZ   @@3
         POP   EBP
         POP   EBX
         POP   ESI
         POP   EDI
  end;
  {$ELSE}
  var
    T: TPolyMatrix;
    I,J: Integer;
    N,D: Cardinal;
  begin
    for I := 0 to Degree -1 do
    begin
      N := M[I];
      D := 0;
      for J := 0 to Degree -1 do
      begin
        if N and $80000000 <> 0 then D := D xor R[J];
        N := N shl 1;
      end;
      T[I] := D;
    end;
    PolyCopy(R, T);
  end;
  {$ENDIF}

  procedure PolyPowMod(var R: TPolyMatrix; const M: TPolyMatrix; N: Cardinal; Degree: Integer);
  var
    L: Cardinal;
  begin
    PolyCopy(R, M);
    L := $80000000;
    while N and L = 0 do L := L shr 1;
    while L > 1 do
    begin
      L := L shr 1;
      PolyMul(R, R, Degree);
      if L and N <> 0 then PolyMul(R, M, Degree);
    end;
  end;

var
  P,M: TPolyMatrix;
  I,J: Integer;
  State: Cardinal;
begin
  Result := False;
  PolyInit(M, Poly, Degree);
  PolyCopy(P, M);
  State := P[0];
  for I := 1 to Degree do
  begin
    PolyMul(P, P, Degree);
    if P[0] = State then
      if I = Degree then
      begin
        for J := 0 to FactorCount -1 do
        begin
          PolyPowMod(P, M, Factors[J], Degree);
          if P[0] = $80000000 then Exit;
        end;
        Result := True;
        Exit;
      end else Exit;  
  end;    
end;

function FindPrimitivePolynom(Poly: Cardinal; Degree: Integer): Cardinal;
// on PIV 1.5 GHz
// 4.95 ms (asm) 6.97 ms (pascal) on degree 32 searches
// 0.41 ms (asm) 0.60 ms (pascal) on degree 16 searches
// on random input about 1/16 are primitive polynoms
// Poly / 2, means Result *2 +1 = real polynom

  function EvenParity(Poly: Cardinal): Boolean;
  // returns TRUE if count of bits set to 1 in Poly is even
  {$IFDEF ASM}
  asm
       MOVZX  EDX,AX
       SHR    EAX,16
       XOR    EAX,EDX
       XOR     AH,AL
       SETP    AL
  end;
  {$ELSE}
  var
    I: Cardinal;
  begin
    I := 0;
    while Poly <> 0 do
    begin
      Inc(I, Poly and 1);
      Poly := Poly shr 1;
    end;
    Result := not Odd(I);
  end;
  {$ENDIF}

var
  Factors: TFactors;
  Mask: Cardinal;
  FactorCount: Integer;
begin
  if Degree > 0 then
  begin
    Mask := $FFFFFFFF shr (32 - Degree);   // eg. 2^Degree -1
    Poly := Poly and Mask or 1 shl (Degree -1);
    FactorCount := FactorOrder(Factors, Degree);
    while Poly <= Mask do
      if PolyIsPrimitive(Poly, Degree, Factors, FactorCount) then
      begin
        Result := Poly;
        Exit;
      end else
      repeat
        Inc(Poly);
      until (Poly > Mask) or EvenParity(Poly);
  end;
  Result := 0;
end;

function IsPolynomPrimitive(Poly: Cardinal): Boolean;
// on PIV 1.5 GHz
// ~0.446 ms on random polys with degree 32
// ~0.052 ms on random polys with degree 16
var
  Factors: TFactors;
  FactorCount,Degree: Integer;
  P: Cardinal;
begin
  Degree := 0;
  P := Poly;
  while P <> 0 do
  begin
    P := P shr 1;
    Inc(Degree);
  end;
  if Degree > 0 then
  begin
    FactorCount := FactorOrder(Factors, Degree);
    Result := PolyIsPrimitive(Poly, Degree, Factors, FactorCount);
  end else Result := False;
end;

[Hagen R. (hagen)]

um nun zu prüfen ob eine "zahl" durch ein Polynom in GF(2) erzeugbar ist 
muß man das Polynom und diese Zahl in nicht mehr reduzierebare und 
primitive Polynome zerlegen, quasi das gleiche machen wie eine 
natürliche Zahl in deren Primzahlpotenzen zu zerlegen. Zwei natürliche 
Zahlen sind dann teilerfremd wenn sie eine Primzahlpotenz enthalten die 
nicht in beiden Primzahlpotenzzerlegungen der beiden Zahlen vorkommt. 
Gleiches gilt für GF(2).

Ist das gewählte Polynom des LFSRs also primitiv und nicht reduzierbar 
(quasi wie eine Primzahl in N) dann gilt: wenn die "Zahl" kleiner der 
Order -1 des Polynoms und nicht Null ist dann ist sie Bestandteil der 
Menge der erzeugbaren "Zahlen" des LFSRs => MLS.

Gruß hagen

[Lattice User (Gast)]

@Hagen Re

Da ich mich bisher nur so am Rande damit beschäftigt habe, wwei Fragen:

1.) Hast du das Programm auch ohne ASM Einlagen?

2.) Ich habe den Eindruck du verwendest primitiv und nicht reduzierbar 
synonym. Das wäre aber falsch. Ein primitives Polynom ist immer nicht 
reduzierbar, aber der Umkehrschluss gilt nicht:
Beispiel: 1+x+x^2+x^3+x^4

[Hmm (Gast)]

>Ich habe den Eindruck du verwendest primitiv und nicht reduzierbar
>synonym.

Könntest Du bitte mal zitieren, woher Du diesen Eindruck hast?

Ich lese da: "primitiv und nicht reduzierbar"

[Hagen R. (hagen)]

Lattice User schrieb:
> 1.) Hast du das Programm auch ohne ASM Einlagen?

Ist PASCAL und Assembler, dieser steht in DEFINES gekapselt da, also 
immer mit dem dazugehörigen PASCAL Source. Leider mit der Forensoftware 
hier nicht so gut ersichtlich.

Lattice User schrieb:
> Ein primitives Polynom ist immer nicht
> reduzierbar, aber der Umkehrschluss gilt nicht:

Das ist "korrekt" weswegen ich

Hmm schrieb:
> Ich lese da: "primitiv und nicht reduzierbar"

geschrieben habe ;)
Es gibt aber auch primitive Polynome die reduzierbar sind, aber soweit 
ich weiß nicht in GF(p^m). Man müsste also auch das gewählte Field mit 
angeben damit die Aussage "primitiv heist immer auch nicht reduzierbar" 
stimmt, es gibt ja nicht nur Polynome in GF(x).

siehe http://de.wikipedia.org/wiki/Primitives_Polynom
und dann http://de.wikipedia.org/wiki/Inhalt_%28Polynom%29

Gruß hagen

[Lattice User (Gast)]

Hagen Re schrieb:
> Ist PASCAL und Assembler, dieser steht in DEFINES gekapselt da, also
> immer mit dem dazugehörigen PASCAL Source. Leider mit der Forensoftware
> hier nicht so gut ersichtlich.

Ich meinte pures Pascal, dann wäre es leichter es in eine gängigere 
Sprache zz übersetzen. So ist das mir zuviel Arbeit.

Hagen Re schrieb:
> Es gibt aber auch primitive Polynome die reduzierbar sind,

Hmm, Wolfram ist anderer Meinung, gkeich der erste Satz.
http://mathworld.wolfram.com/PrimitivePolynomial.html

Und in der englischen Wikipedia steht bei Gauss Lemma:

"The notion of primitive polynomial used here (which differs from the 
notion with the same name in the context of finite fields)"

http://en.wikipedia.org/wiki/Gauss%27s_lemma_%28polynomial%29

Steht übrigens auch in deinem ersten Link:
"In der Ringtheorie wird der Begriff primitives Polynom anders 
verwendet."

[Hagen R. (hagen)]

Lattice User schrieb:
> Hagen Re schrieb:
>> Ist PASCAL und Assembler, dieser steht in DEFINES gekapselt da, also
>> immer mit dem dazugehörigen PASCAL Source. Leider mit der Forensoftware
>> hier nicht so gut ersichtlich.
>
> Ich meinte pures Pascal, dann wäre es leichter es in eine gängigere
> Sprache zz übersetzen. So ist das mir zuviel Arbeit.

Nochmal anders formuliert: es ist pures PASCAL, ignoriere doch einfach 
alls zwischen {$IFDEF ASM} und {$ELSE} dann bleibt das gewünschte pure 
PASCAL übrig. Oder noch anders formuliert: der Source ist je nach 
Compiler Defines reines PASCAL oder gemischt mit Assembler. Oder soll 
ich dir das jetzt noch raus löschen aus dem Source ?

Lattice User schrieb:
> Hmm, Wolfram ist anderer Meinung, gkeich der erste Satz.

Nö sind sie nicht. Ich sagte doch das die Angabe worauf sich die 
Polynomarithmetik bezieht wichtig ist damit diese Aussage stimmt. Auch 
Wolfram bezieht sich auf Polynome in Galois Feldern. Es gibt aber auch 
andere Polynome in anderen Domains, und bei denen muß diese Aussage 
nicht zwangsläufig stimmen. Ich gebe aber zu das es auch ein Tick von 
mir ist aussagenlogisch darauf zu bestehen das das Polynom "nicht 
reduzierbar und primitiv" sein muß. In GF(p^m) heist dies das ein 
primitives Polynom zangsläufig auch nicht reduzierbar sein wird, das muß 
aber für andere Polynomarithmetiken nicht stimmen. Ich habe es eben so 
gelernt es so zu formulieren, mein Lehrer war da auch sehr eigensinnig 
und penibel mit seinen Formulierungen. Letzendlich ist das egal, meine 
Ausage ist ansich richtig und wir fangen über Trivialitäten einen 
Glaubenskrieg an, es sind nur Worte und wir wissen was gemeint war.

Gruß Hagen

[Hagen R. (hagen)]

Lattice User schrieb:
> Ich meinte pures Pascal, dann wäre es leichter es in eine gängigere
> Sprache zz übersetzen.

PASCAL ist eine sehr gängige Sprache, was sonst ;)

[Hagen R. (hagen)]

Lattice User schrieb:
> Steht übrigens auch in deinem ersten Link:
> "In der Ringtheorie wird der Begriff primitives Polynom anders
> verwendet."

Ich weiß, das war ja auch der Grund warum ich es explizit verlinkt habe 
;)

[Lattice User (Gast)]

Hagen Re schrieb:
> PASCAL ist eine sehr gängige Sprache, was sonst ;)

Vor 30 Jahren :-)

[Hagen R. (hagen)]

Lattice User schrieb:
> Hagen Re schrieb:
>> PASCAL ist eine sehr gängige Sprache, was sonst ;)
>
> Vor 30 Jahren :-)

naja, ich arbeite für einige deutsche SW-Buden mit markanten 
Marktanteilen die mit Delphi arbeiten und das ist nichts anderes als 
PASCAL, übrigens ist der Source von mir da oben ebenfalls in 
Wirklichkeit ein Delphi Source.

Gruß hagen

[Detlef _. (detlef_a)]

Wen's interessiert: Angehängt das korrigierte Programm, auch mit XNOR 
Rückkopplung. Es probiert aus, ob ein gegebenes Polynom die MLS erzeugt. 
Das Polynom, das der TO genannt hatte, produziert eine MLS, also kommt 
auch der gesuchte Wert vor.

Danke an die Beteiligten, wieder was dabeigelernt.

Cheers
Detlef

/*******************************************************************/
int main(int  argc , char ** argv)
/*******************************************************************/
{

   unsigned char *f,c;
   unsigned long k,p;

#define NN (28)

f=(char *)malloc(1<<(NN-3));
if(f==NULL){printf("geht nich \n"); return;}

for(k=0;k<(1<<(NN-3));k++) {
  if((k&((1<<16)-1))==0) printf("%d \n",k);
  f[k]=0;
}

//p=0xffffffff;
p=0x0;

for(k=0;k<(1<<NN);k++) {
  if((k&((1<<21)-1))==0) printf("%d \n",(1<<NN)-k);
  p=p&((1<<NN)-1);
  if(p==0x2b0638b) { printf("yo %d %x %x \n",k,p,f[p>>3]); }
  c=f[p>>3]&(unsigned char)(1<<(p&7));
  if(c) { printf("gibbs schon %d %x %x \n",k,p,f[p>>3]); return;}
  f[p>>3] |= (unsigned char)(1<<(p&7));
  //p = (p<<1)|(((p>>27)&1)^((p>>2)&1));
  p = (p<<1)|((~(((p>>27)&1)^((p>>2)&1)))&1);
}

return 0;





}

[Detlef _. (detlef_a)]

>>(*) The Great Trinomial Hunt (Richard P. Brent, Paul Zimmermann)

Das liest sich spannend, der Zusammenhang zwischen Trinomials und 
Mersenne Primes ist ja auch erstaunlich (für mich zumindest).

x^43112609+x^4463337+1 ist auch primitiv, das gibt schon ordentliche 
Periodenlängen.

math rulez!
Cheers
Detlef