Eksponentiering ved kvadrering - Exponentiation by squaring

I matematik og computerprogrammering er eksponentiering ved kvadrering en generel metode til hurtig beregning af store positive heltalskræfter i et tal , eller mere generelt af et element i en semigruppe , som et polynom eller en firkantmatrix . Nogle varianter omtales almindeligvis som kvadrat-og-multiplikationsalgoritmer eller binær eksponentiering . Disse kan være af ganske generel anvendelse, for eksempel i modulær regning eller fremstilling af matricer. For halvgrupper, for hvilke der normalt bruges additiv notation , f.eks. Elliptiske kurver, der bruges i kryptografi , betegnes denne metode også som dobbelt-og-tilføj .

Grundlæggende metode

Metoden er baseret på den observation, at vi for et positivt heltal n har

${\ displaystyle x^{n} = {\ begin {cases} x \, (x^{2})^{\ frac {n-1} {2}} og {\ mbox {if}} n {\ mbox {er ulige}} \\ (x^{2})^{\ frac {n} {2}} og {\ mbox {if}} n {\ mbox {er lige}}. \ end {cases} }}$

Eksempel: . 13 er ulige, så ved ovenstående, = . ${\ displaystyle x^{13}}$${\ displaystyle x^{13}}$${\ displaystyle x ((x^{2})^{6})}$

Man kan skrive som et produkt af eksponenter i form 2 ^k , for hvilken 2 ^k <13. = nogle produkt af , , , . Da den binære repræsentation af 13 er 1101, ${\ displaystyle x^{13}}$${\ displaystyle x^{13}}$${\ displaystyle x^{8}}$${\ displaystyle x^{4}}$${\ displaystyle x^{2}}$${\ displaystyle x^{1}}$

${\ displaystyle x^{13}}$ = ${\ displaystyle (x^{8})^{1} \ cdot (x^{4})^{1} \ cdot (x^{2})^{0} \ cdot (x^{1})^ {1}}$

Således kan vi bruge bitene i eksponenten til at bestemme, hvilke kræfter der beregnes.

Dette eksempel viser, hvordan man beregner ved hjælp af denne metode. Eksponenten, 13, er 1101 i binær. Bitene bruges i venstre til højre rækkefølge. Eksponenten har 4 bits, så der er 4 iterationer. ${\ displaystyle x^{13}}$

Først initialisere resultatet til 1: . ${\ displaystyle r \ leftarrow 1 \, (= x^{0})}$

Trin 1) ; bit 1 = 1, så beregne ;${\ displaystyle r \ leftarrow r^{2} \, (= x^{0})}$${\ displaystyle r \ leftarrow r \ cdot x \, (= x^{1})}$

Trin 2) ; bit 2 = 1, så beregne ;${\ displaystyle r \ leftarrow r^{2} \, (= x^{2})}$${\ displaystyle r \ leftarrow r \ cdot x \, (= x^{3})}$

Trin 3) ; bit 3 = 0, så vi er færdige med dette trin (tilsvarende svarer dette til );${\ displaystyle r \ leftarrow r^{2} \, (= x^{6})}$${\ displaystyle r \ leftarrow r \ cdot x^{0} \, (= x^{6})}$

Trin 4) ; bit 4 = 1, så bereg .${\ displaystyle r \ leftarrow r^{2} \, (= x^{12})}$${\ displaystyle r \ leftarrow r \ cdot x \, (= x^{13})}$

Hvis vi skriver i binær som , så svarer dette til at definere en sekvens ved at lade og derefter definere for , hvor vil ligne . ${\ displaystyle n}$${\ displaystyle b_ {k} \ cdots b_ {0}}$${\ displaystyle r_ {k+1}, \ ldots, r_ {0}}$${\ displaystyle r_ {k+1} = 1}$${\ displaystyle r_ {i} = r_ {i+1}^{2} x^{b_ {i}}}$${\ displaystyle i = k, \ ldots, 0}$${\ displaystyle r_ {0}}$${\ displaystyle x^{n}}$

Dette kan implementeres som følgende rekursive algoritme :

  Function exp_by_squaring(x, n)
    if n < 0  then return exp_by_squaring(1 / x, -n);
    else if n = 0  then return  1;
    else if n = 1  then return  x ;
    else if n is even  then return exp_by_squaring(x * x,  n / 2);
    else if n is odd  then return x * exp_by_squaring(x * x, (n - 1) / 2);

Selvom den ikke er hale-rekursiv , kan denne algoritme omskrives til en hale-rekursiv algoritme ved at indføre en hjælpefunktion:

  Function exp_by_squaring(x, n)
    return exp_by_squaring2(1, x, n)
  Function exp_by_squaring2(y, x, n)
    if n < 0  then return exp_by_squaring2(y, 1 / x, - n);
    else if n = 0  then return  y;
    else if n = 1  then return  x * y;
    else if n is even  then return exp_by_squaring2(y, x * x,  n / 2);
    else if n is odd  then return exp_by_squaring2(x * y, x * x, (n - 1) / 2).

En hale-rekursiv variant kan også konstrueres ved hjælp af et par akkumulatorer i stedet for en hjælpefunktion som vist i F# -eksemplet nedenfor. Akkumulatorerne a1 og a2 kan betragtes som lagring af værdierne, og hvor i og j initialiseres til henholdsvis 1 og 0. I det jævne tilfælde er jeg fordoblet, og i det ulige tilfælde øges j med i. Det endelige resultat er hvor . ${\ displaystyle x^{i}}$${\ displaystyle x^{j}}$${\ displaystyle x^{i+j}}$${\ displaystyle i+j = n}$

let exp_by_squaring x n =
    let rec _exp x n' a1 a2 =
        if   n' = 0   then 1
        elif n' = 1   then a1*a2
        elif n'%2 = 0 then _exp x (n'/2) (a1*a1) a2
        else               _exp x (n'-1) a1 (a1*a2)
    _exp x n x 1

Den iterative version af algoritmen bruger også et afgrænset hjælpeareal og er givet af

  Function exp_by_squaring_iterative(x, n)
    if n < 0 then
      x := 1 / x;
      n := -n;
    if n = 0 then return 1
    y := 1;
    while n > 1 do
      if n is even then 
        x := x * x;
        n := n / 2;
      else
        y := x * y;
        x := x * x;
        n := (n - 1) / 2;
    return x * y

Beregningskompleksitet

En kort analyse viser, at en sådan algoritme bruger firkanter og højst multiplikationer, hvor betegner gulvfunktionen . Mere præcist er antallet af multiplikationer en mindre end antallet af dem, der er til stede i den binære udvidelse af n . For n større end ca. 4 er dette beregningsmæssigt mere effektivt end naivt at multiplicere basen med sig selv gentagne gange. ${\ displaystyle \ lfloor \ log _ {2} n \ rfloor}$${\ displaystyle \ lfloor \ log _ {2} n \ rfloor}$${\ displaystyle \ lfloor \; \ rfloor}$

Hver kvadrering resulterer i omtrent det dobbelte af antallet af cifre i den foregående, og hvis multiplikation af to d -cifrede tal er implementeret i O ( d ^k ) -operationer for nogle faste k , er kompleksiteten af ​​computing x ⁿ givet ved

${\ displaystyle \ sum \ limit _ {i = 0}^{O (\ log n)} {\ big (} 2^{i} O (\ log x) {\ big)}^{k} = O { \ big (} (n \ log x)^{k} {\ big)}.}$

2 ^k -ary metode

Denne algoritme beregner værdien af x ⁿ efter udvidelse af eksponenten i base 2 ^k . Det blev først foreslået af Brauer i 1939. I algoritmen herunder gør vi brug af følgende funktion f (0) = ( k , 0) og f ( m ) = ( s ,  u ), hvor m = u · 2 ^s med du ulige.

Algoritme:

Input

Et element x i G , en parameter k > 0, et ikke-negativt heltal n = ( n _{l −1} , n _{l −2} , ..., n ₀ ) _{2 ^k} og de forudberegnede værdier .${\ displaystyle x^{3}, x^{5}, ..., x^{2^{k} -1}}$

Produktion

Elementet x ⁿ i G

y := 1; i := l - 1
while i ≥ 0 do
    (s, u) := f(ni)
    for j := 1 to k - s do
        y := y2 
    y := y * xu
    for j := 1 to s do
        y := y2
    i := i - 1
return y

For optimal effektivitet bør k være det mindste heltal, der tilfredsstiller

${\ displaystyle \ log n <{\ frac {k (k+1) \ cdot 2^{2k}} {2^{k+1} -k-2}}+1.}$

Glidende vindue metode

Denne metode er en effektiv variant af 2 ^k -ary -metoden. For eksempel at beregne eksponenten 398, der har binær ekspansion (110 001 110) ₂ , tager vi et vindue med længde 3 ved hjælp af algoritmen 2 ^k -ary metode og beregner 1, x ³ , x ⁶ , x ¹² , x ²⁴ , x ⁴⁸ , x ⁴⁹ , x ⁹⁸ , x ⁹⁹ , x ¹⁹⁸ , x ¹⁹⁹ , x ³⁹⁸ . Men vi kan også beregne 1, x ³ , x ⁶ , x ¹² , x ²⁴ , x ⁴⁸ , x ⁹⁶ , x ¹⁹² , x ¹⁹⁹ , x ³⁹⁸ , hvilket sparer en multiplikation og svarer til at evaluere (110 001 110) ₂

Her er den generelle algoritme:

Algoritme:

Input

Et element x i G , et ikke-negativt heltal n = ( n _{l −1} , n _{l −2} , ..., n ₀ ) ₂ , en parameter k > 0 og de forudberegnede værdier .${\ displaystyle x^{3}, x^{5}, ..., x^{2^{k} -1}}$

Produktion

Elementet x ⁿ ∈ G .

Algoritme:

y := 1; i := l - 1
while i > -1 do
    if ni = 0 then
        yy:= y2' i := i - 1
    else
        ss:= max{i - k + 1, 0}
        while ns = 0 do
            ss:= s + 1
        for h := 1 to i - s + 1 do
            yy:= y2
        uu:= (ni, ni-1, ..., ns)2
        yy:= y * xu
        ii:= s - 1
return y

Montgomery's stige teknik

Mange algoritmer til eksponentiering giver ikke forsvar mod sidekanalangreb . En angriber, der observerer sekvensen af ​​firkanter og multiplikationer, kan nemlig (delvist) gendanne den eksponent, der er involveret i beregningen. Dette er et problem, hvis eksponenten skulle forblive hemmelig, som med mange public-key kryptosystemer . En teknik kaldet " Montgomery's ladder" adresserer denne bekymring.

I betragtning af den binære ekspansion af et positivt heltal n = ( n _{k −1} ... n ₀ ) ₂ med n _{k − 1} = 1, kan vi beregne x ⁿ som følger:

x1 = x; x2 = x2
for i = k - 2 to 0 do
    If ni = 0 then
        x2 = x1 * x2; x1 = x12
    else
        x1 = x1 * x2; x2 = x22
return x1

Algoritmen udfører en fast sekvens af operationer ( op til log  n ): en multiplikation og kvadrering finder sted for hver bit i eksponenten, uanset bitens specifikke værdi. En lignende algoritme til multiplikation ved fordobling findes.

Denne specifikke implementering af Montgomerys stigen er endnu ikke beskyttet mod cachen timing angreb : memory access ventetid kan stadig være observerbar til en angriber, som forskellige variabler er adgang afhængigt af værdien af stumper af den hemmelige eksponent. Moderne kryptografiske implementeringer bruger en "scatter" -teknik til at sikre, at processoren altid savner den hurtigere cache.

Eksponent med fast base

Der er flere metoder, der kan bruges til at beregne x ^n, når basen er fast og eksponenten varierer. Som man kan se, spiller forberegninger en nøglerolle i disse algoritmer.

Yaos metode

Yaos metode er ortogonal i forhold til 2 ^k -ary -metoden, hvor eksponenten udvides i radix b = 2 ^k, og beregningen er som udført i algoritmen ovenfor. Lad n , n _i , b og b _i være heltal.

Lad eksponenten n skrives som

${\ displaystyle n = \ sum _ {i = 0}^{w-1} n_ {i} b_ {i},}$

hvor for alle . ${\ displaystyle 0 \ leqslant n_ {i} <h}$${\ displaystyle i \ i [0, w-1]}$

Lad x _i = x ^{b _i} .

Derefter bruger algoritmen ligheden

${\ displaystyle x^{n} = \ prod _ {i = 0}^{w-1} x_ {i}^{n_ {i}} = \ prod _ {j = 1}^{h-1} { \ bigg [} \ prod _ {n_ {i} = j} x_ {i} {\ bigg]}^{j}.}$

I betragtning af elementet x i G og eksponenten n skrevet i ovenstående form, sammen med de forudberegnede værdier x ^{b ₀} ... x ^{b _{w −1}} , beregnes elementet x ⁿ ved hjælp af nedenstående algoritme:

y = 1, u = 1, j = h - 1
while j > 0 do
    for i = 0 to w - 1 do
        if ni = j then
            u = u × xbi
    y = y × u
    j = j - 1
return y

Hvis vi sætter h = 2 ^k og b _i = h ⁱ , så er n _i -værdierne simpelthen cifrene for n i basis h . Yaos metode samler i u først de x _i, der ser ud til den højeste magt ; i næste runde samles de med magt også i u osv. Variablen y multipliceres gange med den indledende u , gange med de næsthøjeste kræfter osv. Algoritmen bruger multiplikationer, og elementer skal gemmes for at beregne x ⁿ . ${\ displaystyle h-1}$${\ displaystyle h-2}$${\ displaystyle h-1}$${\ displaystyle h-2}$${\ displaystyle w+h-2}$${\ displaystyle w+1}$

Euklidisk metode

Den euklidiske metode blev først introduceret i Effektiv eksponentiering ved hjælp af forberegning og vektortilsætningskæder af PD Rooij.

Denne metode til beregning i gruppe G , hvor n er et naturligt heltal, hvis algoritme er angivet nedenfor, bruger følgende ligestilling rekursivt: ${\ displaystyle x^{n}}$

${\ displaystyle x_ {0}^{n_ {0}} \ cdot x_ {1}^{n_ {1}} = \ venstre (x_ {0} \ cdot x_ {1}^{q} \ højre)^{ n_ {0}} \ cdot x_ {1}^{n_ {1} \ mod n_ {0}},}$

hvor . Med andre ord bruges en euklidisk division af eksponenten n ₁ med n ₀ til at returnere en kvotient q og en rest n ₁ mod n ₀ . ${\ displaystyle q = \ left \ lfloor {\ frac {n_ {1}} {n_ {0}}} \ right \ rfloor}$

I betragtning af basiselementet x i gruppe G og eksponenten skrevet som i Yaos metode, beregnes elementet ved hjælp af forudberegnede værdier og derefter algoritmen nedenfor. ${\ displaystyle n}$${\ displaystyle x^{n}}$${\ displaystyle l}$${\ displaystyle x^{b_ {0}}, ..., x^{b_ {l_ {i}}}}}$

Begin loop   
    Find ${\displaystyle M\in [0,l-1]}$, such that ${\displaystyle \forall i\in [0,l-1],n_{M}\geq n_{i}}$.
    Find ${\displaystyle N\in {\big (}[0,l-1]-M{\big )}}$, such that ${\displaystyle \forall i\in {\big (}[0,l-1]-M{\big )},n_{N}\geq n_{i}}$.
    Break loop if ${\displaystyle n_{N}=0}$.
    Let ${\displaystyle q=\lfloor n_{M}/n_{N}\rfloor }$, and then let ${\displaystyle n_{N}=(n_{M}{\bmod {n}}_{N})}$.
    Compute recursively ${\displaystyle x_{M}^{q}}$, and then let ${\displaystyle x_{N}=x_{N}\cdot x_{M}^{q}}$.
End loop;
Return ${\displaystyle x^{n}=x_{M}^{n_{M}}}$.

Algoritmen finder først den største værdi blandt n _i og derefter supremum inden for mængden af { n _i \ i ≠ M } . Så det rejser x _M til potensen q , multiplicerer denne værdi med x _N , og tildeler derefter x _N resultatet af denne beregning og n _M værdien n _M modulo n _N .

Yderligere applikationer

Den samme idé tillader hurtig beregning af store eksponenter modulo et tal. Især inden for kryptografi er det nyttigt at beregne kræfter i en ring med heltal modulo q . Det kan også bruges til at beregne heltalskræfter i en gruppe ved hjælp af reglen

Effekt ( x , - n ) = (Effekt ( x , n )) ⁻¹ .

Metoden fungerer i hver semigruppe og bruges ofte til at beregne matricers beføjelser .

Eksempelvis evalueringen af

13789 ⁷²²³⁴¹ (mod 2345) = 2029

ville tage meget lang tid og meget lagerplads, hvis den naive metode blev brugt: beregn 13789 ⁷²²³⁴¹ , tag derefter resten, når den blev divideret med 2345. Selv brug af en mere effektiv metode vil tage lang tid: kvadrat 13789, tag resten, når den er delt med 2345, gang resultatet med 13789 og så videre. Dette vil tage mindre end modulære multiplikationer. ${\ displaystyle 2 \ log _ {2} (722340) \ leq 40}$

Anvendelse over eksp-by-squaring- algoritmen med " *" fortolket som x  *  y = xy mod 2345 (det vil sige en multiplikation efterfulgt af en division med rest) fører til kun 27 multiplikationer og divisioner af heltal, som alle kan gemmes i et enkelt maskinord.

Signeret-cifret omkodning

I visse beregninger kan det være mere effektivt at tillade negative koefficienter og dermed bruge inversen af ​​basen, forudsat at inversion i G er "hurtig" eller er blevet forudberegnet. For eksempel, når man beregner x ^{2 k −1} , kræver den binære metode k −1 multiplikationer og k −1 kvadrater. Imidlertid kunne man udføre k kvadrater for at få x ^{2 k} og derefter gange med x ^{−1 for} at opnå x ^{2 k −1} .

Til dette formål definerer vi den signerede cifrede repræsentation af et helt tal n i radix b som

${\ displaystyle n = \ sum _ {i = 0}^{l-1} n_ {i} b^{i} {\ tekst {med}} | n_ {i} | <b.}$

Signeret binær repræsentation svarer til det særlige valg b = 2 og . Det betegnes med . Der er flere metoder til beregning af denne repræsentation. Fremstillingen er ikke unik. Tag for eksempel n = 478 : to forskellige signerede-binære repræsentationer er givet af og , hvor bruges til at betegne -1 . Da den binære metode beregner en multiplikation for hver ikke-nul-post i basis-2-repræsentationen af n , er vi interesserede i at finde den signerede-binære repræsentation med det mindste antal ikke-nul-poster, det vil sige den med minimal Hamming vægt . En metode til at gøre dette er at beregne repræsentationen i ikke-tilstødende form , eller kort sagt NAF, som er en, der tilfredsstiller og betegnes med . F.eks. Er NAF -repræsentationen på 478 . Denne repræsentation har altid minimal Hamming -vægt. En simpel algoritme til at beregne NAF -repræsentationen for et givet heltal med er følgende: ${\ displaystyle n_ {i} \ in \ {-1,0,1 \}}$${\ displaystyle (n_ {l-1} \ prikker n_ {0}) _ {s}}$${\ displaystyle (10 {\ bar {1}} 1100 {\ bar {1}} 10) _ {s}}$${\ displaystyle (100 {\ bar {1}} 1000 {\ bar {1}} 0) _ {s}}$${\ displaystyle {\ bar {1}}}$ ${\ displaystyle n_ {i} n_ {i+1} = 0 {\ tekst {for alle}} i \ geqslant 0}$${\ displaystyle (n_ {l-1} \ dots n_ {0}) _ {\ text {NAF}}}$${\ displaystyle (1000 {\ bar {1}} 000 {\ bar {1}} 0) _ {\ text {NAF}}}$${\ displaystyle n = (n_ {l} n_ {l-1} \ prikker n_ {0}) _ {2}}$${\ displaystyle n_ {l} = n_ {l-1} = 0}$

${\displaystyle c_{0}=0}$
for i = 0 to l − 1 do
  ${\displaystyle c_{i+1}=\left\lfloor {\frac {1}{2}}(c_{i}+n_{i}+n_{i+1})\right\rfloor }$
  ${\displaystyle n_{i}'=c_{i}+n_{i}-2c_{i+1}}$
return ${\displaystyle (n_{l-1}'\dots n_{0}')_{\text{NAF}}}$

En anden algoritme af Koyama og Tsuruoka kræver ikke den betingelse, at ; det minimerer stadig Hamming -vægten. ${\ displaystyle n_ {i} = n_ {i+1} = 0}$

Alternativer og generaliseringer

Eksponentiering ved kvadrering kan ses som en suboptimal additionskæde-eksponentieringsalgoritme : den beregner eksponenten med en additionskæde, der består af gentagne eksponentdoblinger (kvadrationer) og/eller øgede eksponenter med én (multipliceret med x ). Mere generelt kan man nogle gange udføre eksponentieringen ved hjælp af færre multiplikationer (men typisk ved hjælp af mere hukommelse) , hvis man tillader, at alle tidligere beregnede eksponenter summeres (ved at multiplicere disse x ). Den mindste effekt, hvor dette sker, er for n = 15:

${\ displaystyle x^{15} = x \ times (x \ times [x \ times x^{2}]^{2})^{2}}$ (kvadrering, 6 gange),

${\ displaystyle x^{15} = x^{3} \ gange ([x^{3}]^{2})^{2}}$ (optimal tilsætningskæde, 5 gange hvis x ³ genbruges).

Generelt er det et svært problem at finde den optimale additionskæde for en given eksponent, for hvilken der ikke kendes effektive algoritmer, så optimale kæder bruges typisk kun til små eksponenter (f.eks. I kompilatorer, hvor kæderne til små kræfter er blevet forud-tabuleret ). Der er dog en række heuristiske algoritmer, der, selvom de ikke er optimale, har færre multiplikationer end eksponentiering ved at kvadrere på bekostning af yderligere bogholderiarbejde og hukommelsesbrug. Uanset det vokser antallet af multiplikationer aldrig langsommere end Θ (log n ), så disse algoritmer forbedres kun asymptotisk ved eksponentiering ved i bedste fald at kvadrere med en konstant faktor.

Se også

• Modulær eksponentiering
• Vectorial tilføjelseskæde
• Montgomery reduktion
• Ikke-tilstødende form
• Tilsætningskæde

Noter

Referencer