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

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

BBS-ի տեսքն է՝

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

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

Կատեգորիա:Ալգորիթմներ