Baby-step jätte-step

Inom gruppteorin , en gren av matematiken, är baby-step jätte-steget en möte-i-mitten- algoritm för att beräkna den diskreta logaritmen eller ordningen för ett element i en finit abelsk grupp av Daniel Shanks . Problemet med diskret logg är av grundläggande betydelse för området för kryptografi med publika nyckel .

Många av de mest använda kryptografisystemen är baserade på antagandet att den diskreta loggen är extremt svår att beräkna; ju svårare det är, desto mer säkerhet ger det en dataöverföring. Ett sätt att öka svårigheten med det diskreta loggproblemet är att basera kryptosystemet på en större grupp.

Teori

Algoritmen är baserad på en avvägning mellan rum och tid . Det är en ganska enkel modifiering av provmultiplikation, den naiva metoden för att hitta diskreta logaritmer.

Givet en cyklisk grupp $G$ av ordningen $n$ , en generator $\alpha$ för gruppen och ett gruppelement $\beta$ , är problemet att hitta ett heltal $x$ så att

$\alpha ^{x}=\beta \,.$

Baby-step jätte-steg-algoritmen är baserad på att skriva om $x$ :

$x=im+j$

$m=\left\lceil {\sqrt {n}}\right\rceil$

$0\ leq i<m$

$0\leq j<m$

Därför har vi:

$\alpha ^{x}=\beta \,$

$\alpha ^{im+j}=\beta \,$

$\alpha ^{j}=\beta \left(\alpha ^{-m}\right)^{i}\,$

Algoritmen förberäknar $\alpha ^{j}$ för flera värden på $j$ . Sedan fixar den en $m$ och försöker värdena på $i$ på höger sida av kongruensen ovan, på samma sätt som provmultiplikation. Den testar för att se om kongruensen är uppfylld för något värde på $j$ , med hjälp av de förberäknade värdena för $\alpha ^{j}$ .

Algoritmen

Ingång : En cyklisk grupp G av ordningen n , med en generator α och ett element β .

Utdata : Ett värde x som uppfyller $\alpha ^{x}=\beta$ .

1. m ← Tak( √ n )
2. För alla j där 0 ≤ j < m :
   1. Beräkna α ^j och lagra paret ( j , α ^j ) i en tabell. (Se § I praktiken )
3. Beräkna α ^{− m} .
4. γ ← β . (set γ = β )
5. För alla i där 0 ≤ i < m :
   1. Kontrollera om γ är den andra komponenten ( α ^j ) i något par i tabellen.
   2. Om så är fallet, returnera im + j .
   3. Om inte, γ ← γ • α ^{− m} .

I praktiken

Det bästa sättet att snabba upp baby-step jätte-steg-algoritmen är att använda ett effektivt tabelluppslagsschema. Det bästa i det här fallet är en hashtabell . Hashen görs på den andra komponenten, och för att utföra kontrollen i steg 1 av huvudslingan hashas y och den resulterande minnesadressen kontrolleras. Eftersom hashtabeller kan hämta och lägga till element i ${\displaystyle O(1)}-$ tid (konstant tid), saktar detta inte ner den övergripande baby-step jätte-step-algoritmen.

Algoritmens rymdkomplexitet är $O({\sqrt {n}})$ , medan tidskomplexiteten för algoritmen är ${\displaystyle \sum _{k=1}^{\sqrt {n}}\log k=O\!\left({\sqrt {n}}\log n\right)} på grund av den första delen$ av babysteg av upprepad multiplikation av generatorn före lagring (observera att varje multiplikation bara tar linjär tid vad gäller bitarna, eftersom generatorn antingen är liten eller anses vara en konstant för probleminstansen). Denna gångtid är dock bättre än $O(n)$ körtid för den naiva brute force-beräkningen.

Baby-step giant-step-algoritmen används ofta för att lösa den delade nyckeln i Diffie Hellman-nyckelutbytet , när modulen är ett primtal. Om modulen inte är primtal, Pohlig-Hellman-algoritmen en mindre algoritmisk komplexitet och löser samma problem.

Anteckningar

• Baby-step jätte-steg algoritmen är en generisk algoritm. Det fungerar för varje ändlig cyklisk grupp.
• Det är inte nödvändigt att veta ordningen på grupp G i förväg. Algoritmen fungerar fortfarande om n bara är en övre gräns för gruppordningen.
• Vanligtvis används baby-step giant-step-algoritmen för grupper vars ordning är prime. Om gruppens ordning är sammansatt Pohlig-Hellman-algoritmen mer effektiv.
• Algoritmen kräver O ( m )-minne. Det är möjligt att använda mindre minne genom att välja ett mindre m i det första steget av algoritmen. Om du gör det ökar körtiden, som då är O ( n / m ). Alternativt kan man använda Pollards rho-algoritm för logaritmer , som har ungefär samma gångtid som baby-step jätte-step-algoritmen, men bara ett litet minneskrav.
• Medan denna algoritm tillskrivs Daniel Shanks, som publicerade 1971 års tidning där den först förekom, uppger ett 1994 papper av Nechaev att det var känt för Gelfond 1962.
• Det finns optimerade versioner av den ursprungliga algoritmen, som att använda de kollisionsfria trunkerade uppslagstabellerna för eller negationskartor och Montgomerys samtidiga modulära inversion som föreslagits i.

Vidare läsning

• H. Cohen , En kurs i beräkningsalgebraisk talteori, Springer, 1996.
• D. Shanks , Klassnummer, en teori om faktorisering och släkten. I Proc. Symp. Ren matte. 20, sid. 415—440. AMS, Providence, RI, 1971.
• A. Stein och E. Teske, Optimized baby step-giant step methods, Journal of the Ramanujan Mathematical Society 20 (2005), nr. 1, 1–32.
• AV Sutherland , Orderberäkningar i generiska grupper , doktorsavhandling, MIT, 2007.
• DC Terr, En modifiering av Shanks baby-step giant-step-algoritm, Mathematics of Computation 69 (2000), 767–773. doi : 10.1090/S0025-5718-99-01141-2

externa länkar

• Baby step-Giant steg – exempel C källkod