Բլում Բլում Շուբ

Ալգորիթմ Բլում Բլում Շաբը, BBS դա կեղծ պատահական համարների գենեչատոր է առաջարկված 1986 թվականին Լենոր Բլյումի, Մանուել Բլյումի և Մայքլ Շաբի կողմից: BBS-ի տեսքն է`

որտեղ` M=P*Q -ն երկու մեծ պարզ թվերի` p և q արդյունքն է: Ալգորիտմի յուրաքանչյուր քայլում ելքային տվյալները ստացվում են կամ $x_n$-ից վերցնելով հավասարության բիթեր, կամ մեկ կամ ավելի պակաս, քան ավելի նշանակալի բիթեր $x_n$. Երկու պարզ թվերի` p և q համար, երկուսն էլ պետք է լինեն մոդուլով համեմատելի 3 -ից մինչև մոդուլով 4 (ինչը ապահովոջմ է, որը ամեն մի քառակուսի մնացորդ ունի մեկ քառակուսի արմատ, որը հանդիսանում է նաև որպես մնացորդ և ամենամեց ընդհանուր բաժանարար: (p-1), φ(q-1)) պետք է լինի փոքր (ԱՅՆ ՄԵԾԱՑՆՈՒՄ Է ՑԻԿԼԻ ԵՐԿԱՐՈՒԹՅՈՒՆԸ ) Այս ալգորիթմի հետաքրքիր առանձնահատկությունն այն է, որ Xn ստացման համար պարտադիր չէ հաշվարկել բոլոր (n-1) նախորդ համարները, եթե հայտնի են գեներատորի նախնական վիճակի x0, p և q–ի համարները: n -ի նշանակությունը կարող է հաշվարկվել միանգամից օգտագործելով հետեվյալ բանաձևը`

$x_{n+1} = x_n^2 \bmod M$

Անվտանգություն

Այս գեներատոր հարմար է ծածկագիտության մեջ, բայց ոչ մոդելավորման համար, քանի որ այն այդքան էլ արագ չէ: Սակայն այն ունի անսովոր մեծ դիմադրողականություն, որը մատակարարում է գեներատորի հատկությունից ելնելով համակարգչային բարդության տեսության խնդրի ֆակտորինգային համարներից: Երբ պարզ թվերը ընտրված են ուշադիր և $O(\log\log M)$ բիտը յուրաքանչյուր $x_n$ - ի հանդիսանում են ելքային տվյալներ, ապա ինչպես $M$ սահմանը աճում է արագ տեմպերով և ելքային բիտերի հաշվարկը կլինի նույնքան դժվար , որքան $M$ - ի ֆակտորիզացիան: Եթե ամբողջ թվերի ֆակտորիզացիայի այնքան ել դժվար է (ինչպես և սպասվում էր), ապա BBS մեծ $M$ -ով կունենա ցանկացած ոչ պատահական նախշերից ազատ ելք, որոնք կարող են նույնացնել հաշվարկի բավարար ծավալների դեպքում: Սակայն, հնարավոր է ֆակտորիզացման համար ալգորիտմի հայտնվում և, հետևաբար BBS –ն այդքան էլ հուսալի չէ: