Кіріспе

Блум Блум Шуб (Б. Б. Ш.) – 1986 жылы Ленор Блум, Мануэль Блум және Майкл Шуб ұсынған псевдорандомдық сандар генераторы, ол Майкл О. Рабиннің бір бағытты функциясынан туындайды. TOC Блум Блум Шуб мына түрде келеді:

,

мұнда M = pq – екі үлкен жай санның p және q көбейтіндісі. Алгоритмнің әр қадамында xn+1-ден белгілі бір нәтиже алынады; нәтиже әдетте xn+1-дің биттерінің жұптығы немесе xn+1-дің ең кіші маңызды биттерінің бірі немесе бірнешеуі болады. Тұқым x0 – M-ге өзіндік жай сан (яғни p және q сандары x0-дің бөлгіштері емес) және 1 немесе 0 емес, бүтін сан болуы керек. Екі жай сан, p және q, екеуі де 3 (mod 4) конгруэнтті болуы керек (бұл әр квадраттық қалдықтың да квадраттық қалдық болатын бір квадрат түбірі бар екенін қамтамасыз етеді) және кішкентай gcd((p-3)/2, (q-3)/2) болатын қауіпсіз жай сандар болуы керек (бұл цикл ұзындығын ұзартады). Блум Блум Шуб генераторының ерекше қасиеті – кез келген xi мәнін тікелей есептеу мүмкіндігі (Ойлер теоремасы бойынша):

,

мұндағы – Кармихаел функциясы. (Бұл жерде бізде ).

Қауіпсіздік

Оның қауіпсіздігін факторлаудың есептеу қиындығына келтіретін дәлел бар. Егер жай сандар тиісті түрде таңдалса және әрбір xn-нің O(log log M) төменгі реттік биттері шығарылса, онда M үлкендегенде, шығыс биттерін кездейсоқтан ажырату, M модулі бойынша квадраттық қалдықтар мәселесін шешуден кем болмауы керек. BBS кездейсоқ сандар генераторының тиімділігі модульдің M мөлшеріне және итерация басына жұмсалатын биттер санына j байланысты. M-ді кішірету немесе j-ді үлкейту алгоритмді жылдамдатады, бірақ сонымен бірге қауіпсіздікті де азайтады. 2005 жылғы мақалада берілген M және j үшін BBS қауіпсіздігінің нақты, асимптотикалық емес дәлелі келтірілген. Бұл нәтиже күтілетін қауіпсіздікті есептеу шығындарымен салыстыру арқылы екі санның таңдалуын бағыттау үшін де қолданылуы мүмкін.