Blum Blum Shub

Blum Blum Shub (B.B.S.) är en pseudoslumptalsgenerator (PSTG) och är även kryptologiskt säker. B.B.S. har formen: . där utsignalen ofta presenteras som pariteten för xi , på formen z1, z2, … zi. Alla de log (log (M)) första bitarna är dock säkra att använda. Startvärdet x0 räknas fram genom formeln x0 = s2 (mod M), där s ska vara ett tal mellan 1 och M-1, tillhöra de naturliga talen och p och q ska inte vara en faktor i s. M är produkten mellan två unika tillräckligt stora p och q (M = pq), där p och q uppfyller: . Denna egenskap gör att varje xi (som är en kvadratisk rest) enbart har en rot som är en kvadratisk rest, vilket gör det möjligt (om man känner till p och q) att ta fram xi-1 entydigt. För att få en så lång cykellängd som möjligt så ska SGD(φ(p-1), φ(q-1)) vara så liten som möjligt (där φ(n) är Eulers fi-funktion). För att räkna ut cykellängden, d.v.s. hur många iterationer som måste köras innan dess att talen upprepar sig (x0 = xlängd), använder man formeln λ(λ (M)) = längd, där lambda är . Detta gäller oftast men endast med säkerhet då ytterligare ett krav ställs på valet av p och q, samt att s måste väljas mer specifikt. En intressant egenskap hos B.B.S. är att det är möjligt att räkna fram xi för alla i via Eulers sats: . Om man känner till x0 samt M, vilket också gör det möjligt att räkna sekvensen framåt. Genom att känna till xi+1 och faktorerna i M d.v.s. p och q kan man även räkna sekvensen baklänges.