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;
}