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

Բլում Բլում Շուբ
Տեսակ	power generator?
Անվանված է	Lenore Blum?, Manuel Blum? և Michael Shub?

Ալգորիթմ Բլում Բլում Շուբը, 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 –ն այդքան էլ հուսալի չէ։