Jump to content

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

Վիքիպեդիայից՝ ազատ հանրագիտարանից
Բլում Բլում Շուբ
Տեսակpower generator?
Անվանված էLenore Blum?, Manuel Blum? և Michael Shub?

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