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

Վիքիպեդիայից՝ ազատ հանրագիտարանից

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