“Greitas” lygties 2x mod N = Z arba (2m)x mod N = Z, x radimo algoritmas, kur N, Z ir m yra žinomi.

 

Žinoma, kad norint rasti x , reikia kelti laipsniu- kas kompiuterio mašininiame kode tolygu daugybos operacijoms. Poto reikia atlikti modulio operaciją- kas kompiuterio mašininiame kode tolygu dalybos operacijoms. Ir taip reikia išbandyti visus skaičius, kol bus rąstas tinkamas. Daugybos operacijos palyginus su dalybos atliekamos daug daug greičiau, bet jei naudojami skaičiai didesni nei kompiuterio registro ilgis, tai daugybos operacijos žymiai sulėtėja. Jei skaičiaus registras pailgėja dvigubai, tai daugybos operacijų padaugeja 4 kartus (jei naudojamas Intel algoritmas).  Apie dalybos operacijas iš vis nešneku, nes operacijų skaičius dideja katastrofiškai daug kartų, ilgėjant registo ilgiui.

            Čia bus aprašytas x radimo algoritmas, kuris skaičiavimams naudoja tik stūmimo, atimties ir lyginimo operacijos, visai nenaudojamos daugybos ir dalybos operacijos. Šitas algoritmas suranda x šimtus kartų greičiau nei standartinis.

 

Teorija

 

Yra žinoma ,kad   norint skaičių padauginti iš 2, arba padalinti iš 2 tai galima atlikti stūmimo operacijas, kurios bus atliktos žymiai greičiau:

            r*2 = r<<1;   (1)  (registro stūmimas į kairę vieną kartą)daugybai

            r/2 = r>>1 ;   (2)  (registro stūmimas į dešinę vieną kartą)dalybai.

Patyrę programistai dažnai tai vartoja. Bet pradedantiems tai gali būti naujiena, kaip ir kai kurių firmų kompiliatoriams.

  Toliau panaudojami kai kurie elementarūs (1) formulės išvedžiojimai ir kitos formulės:

 

2 (x+1) = (2x)* 2 = (2x)<<1;  (3)

 

Modulio radimui naudojama tokia dalybos savybė, kad vietoj dalybos moduliu galima naudoti atimtį.

 

            11 mod 3 = 2 = 11 - 3 - 3 - 3  = 2 ;

Taip pat atimti reikes netiek daug kartų, nes skaičių padauginus iš dviejų, jis nepadidėja taip, kad atimties operacijos , norint rasti modulį, nebebūtų greitesnės.

           

Result mod N,  modulio radimo algoritmas būtų toks():

 

1.      Jei rezultatas mažesnis už modulį N, tai šokam į pabaigą 4 punktą.

2.      Atimam iš rezultato modulio reikšmę N  Result = Result – N;

3.      Šokam į 1 punktą.

4.      Pabaiga. Modulis rastas.

 

Naudojama dar viena modulio savybė.

 

2 (x+1) mod N = (  ( (2x) mod N)  *2 ) mod N = (  ( (2x) mod N )  << 1  ) mod N;  (4)

 

Šita formulė leidžia naudoti rezultatą sekančiai x reikšmei apskaičiuoti ir patikrinti.


Čia pavyzdys funkcijos parašytos su C++, kuri apskaičiuoja x ir gražina rezultatą. Skaičių tipas vienodas uint yra beženklis sveikas skaičius. Intel 386 procesoriuje ir geresniuose, tai 32 bitų ilgio skaičius. Taigi didžiausias skaičius būtų virš 4 milijardų. Didžiausias modulis galėtų būti dvigubai mažesnis. Tai būtų virš 2 milijardų. Tai žinoma nedideli skaičiai. Norint dirbti su didesniais sveikais skaičiais reikia naudoti specialias tokiems skaičiams parašytas klases. Tokia klasė gali tūrėti tik tris aritmetines operacijas (+,-) , vieną loginę (<<1), lyginimo operaciją (= =), priskyrimo operaciją (= ). Jei tokia klasė būtų “BigInteger”, tai tereikia užkomentuoti  “typedef unsigned int  uint;” eilutę ir atkomentuoti  “// typedef BigInteger  uint; “ eilutę.

            Kode matosi  /* || Result= = 0*/  užkomentuotas kodas.  Gali susidaryti situacija, kai rezultatas taps lygus nuliui, tada algoritmas “užsiciklins”, kad to nebūtų reikia nuimti, komentaro simbolius. Tokiu atveju algoritmas sulėtės. Kad taip neatsitiktų reikėtų, padaryti papildomus patikrinimus, prieš naudojant šią funkciją. Tai būtų atskyra tema.  Bet gal užtektų patikrinti, bent jau ar modulis nėra lyginis. Bet  RSA algoritme dažniausiai naudojami, dviejų didelių pirminių skaičių sandaugos moduliai. Todėl tikimybė, kad rezultatas bus 0 ir programa užsiciklins yra maža ir galima nekreipti dėmesio.

            Šitą algoritmą nesunkiai galima pritaikyti tinkliniam skaičiavimui. Tam reikalingas “Serveris” ir “Klientas” .  “Serveris” skirsto skaičiavimo užduotis “Klientams”, kontroliuoja užduoties atlikimo laiką ir taip toliau. Sakysim už “X-Box” kodo dešifravimą, buvo skirta nemaža premija(200 000 dol.). Jame naudojamas RSA algoritmas ir moduliai kurių ilgis siekia 2048 bitus.  Tai labai didelis skaičius ir skaičiavimai trūktų labai ilgai. Bet naudojant tinklo resursus, skaičiavimus galima būtų atitinkamai pagreitinti. Bet ir tai nepadėtų, nebent labai pasisektų…

Laiko apskaičiavimui galima naudoti labai paprastą būdą. Inkrementavimo laiko apskaičiavimas. Sakysim reikia apskaičiuoti, kiek reikia laiko kompiuteriui suskaičiuoti nuo 1 iki  didžiausio 2048 bitų ilgio skaičiaus. Tarkime dabar yra kompiuteriai kurie gali atlikti 4Giga inkrementavimo operacijų per sekundę. Tai laiko jam reikės labai daug. Gaunasi apie 607 skaitmenų skaičius sekundžių. Taigi vien inkrementavimo operacijoms laikas neįsivaizduojamai didelis.

            Na aš nesiūlau jums skaičiuoti, bet šitas algoritmas, tai tik būdas norint  tai pamėginti. Ir tai alternatyvus būdas, norint “nulaužti”  RSA algoritmą. Pirmas būdas rasti duoto “public” rakto daugiklius  (factoring). Žinoma tobulėjant technikai, seni raktai jau dešifruojami. Bet RSA algoritmo privalumas yra, kad galima raktus imti vis didesnius. Tik jei kas nors išras būdą greitam sudėtinių  skaičių radimui, arba mano straipsnyje X radimo algoritmą, tik tada RSA algorimas žlugs. Bet deja geriausi pasaulio matematikai to niekaip nesugalvoja.

           

 

typedef unsigned int  uint;

// typedef BigInteger  uint;

uint SearchX(uint Z, uint N);

uint SearchX(uint Z, uint N)

{         

            register uint Result=2;  

            for(uint x=1; x<N; x++)

{

            Result = Result <<1;

            while(Result >= N)

                        Result = Result – N;

                        if(Result = = Z /* || Result= = 0*/)

                                    return x;        

            }

            return 0;

}

 

Greičiau suskaičiuos, jei x bus dekrementuojamas, o gražinant rezultatą x reikšmė padaroma, kad rodytų tikrą laipsnį.

 

uint SearchX(uint Z, uint N)

{         

            register uint Result=2;  

            for(uint x = N-1;x>0;x--)

{

            Result = Result <<1;

            while(Result>=N)

                        Result= Result – N;

                        if(Result = = Z /* || Result= = 0*/)

                                    return N-x;    

            }

            return 0;

}

 

 

//(2m)x mod N = Z, x paieškos algoritmas

typedef unsigned int  uint;

uint SearchX_Full(const  uint Z, const  uint N, const  uint m);

uint SearchX_Full (const uint Z, const  uint N, const  uint m)

{         

            register uint Result=2;  

            for(uint x=1;x<N;x++)

{

            for(uint i=m;m>0;i--){

                        Result =2<<1;

                        while(Result>=N)

                                    Result= Result – N;

            }

                        if(Result = = Z /* || Result= = 0*/)

                                    return x;        

            }

            return 0;

}

 Main page