înregistrare Logare
Puncte:2
Myria avatar Crypto

Există un algoritm pentru a calcula wNAF pentru un exponent mai rapid decât pătratic?

drapel in
Myria

Pentru a face exponențierea într-un grup pentru care inversarea este trivial de ușoară, cum ar fi grupurile de curbe eliptice, există un algoritm pentru calcularea $w$NAF ("$w$-ary form non-adiacent") matrice mai rapid decât $O(n^2)$? The algoritm standard este listat pe Wikipedia ca (tradus în Python):

def wnaf(d):
    rezultat = []
    pentru i în interval (256):
        dacă d & 1:
            di = mods(d)
            d -= di
            rezultat += [di]
        altceva:
            rezultat += [0]
        d >>= 1
    returnează rezultat[::-1]

Partea pătratică aici este aceea di poate fi negativ, transformând scăderea în adunare. Acest lucru poate duce până în partea de sus a numărului, procesând astfel întreaga valoare a d este potențial necesar pentru fiecare iterație, făcând algoritmul pătratic în numărul de biți.

Există o modalitate mai bună de a face asta?

50
0 + 0
Puncte:2
Daniel S avatar Crypto
drapel ru
Daniel S

Intrebare amuzanta! Raspunsul este da. Trucul este să modifici bucla în funcție de semnul ultimei ferestre. Dacă ultima fereastră a fost pozitivă, sărim peste 0 și ne oprim la următorul 1; dacă ultima fereastră a fost negativă, sărim peste 1 secunde și ne oprim la următorul 0 și o întoarcem. Cred că există, de asemenea, un pas final atât pentru acest lucru, cât și pentru algoritmul citat în întrebarea în care, dacă fereastra finală este negativă, trebuie să punem înainte un 1. Iată cel mai bun împunsător al meu python pentru ferestre de lățime $w$.

def wnaf2(d):
    rezultat = []
    semn = 0
    în timp ce d !=0:
        dacă (d & 1)^semn:
            di = mods(d^sign)
            semn = (d>>(w-1)&1) # Există un caz pentru introducerea acestui lucru în funcția mods
            d = d>>w # Doar ștergeți ultima fereastră fără transporturi
            rezultat += [di]
            rezultat += (w-1)*[0]
        altceva:
            rezultat += [0]
            d >>= 1
    dacă semnează:
        rezultat += [1]
    returnează rezultat[::-1]

Acest lucru este liniar, cu condiția să numărăm schimburile și mascam ca $O(1)$ operațiuni.

0 + 0
Myria avatar
drapel in
Myria
Schimbările și mascarea sunt $O(1)$ într-o implementare reală (adică nu Python), deoarece, în loc să schimbăm efectiv întregul `d`, putem doar indexa octeții și biții. Asta rezolvă problema pe care o aveam. Mulțumiri!
0
Răspunde
drapel romania
SEF 777
întrebarea această in alte limbi:

Postează un răspuns

Majoritatea oamenilor nu înțeleg că a pune multe întrebări deblochează învățarea și îmbunătățește legătura interpersonală. În studiile lui Alison, de exemplu, deși oamenii își puteau aminti cu exactitate câte întrebări au fost puse în conversațiile lor, ei nu au intuit legătura dintre întrebări și apreciere. În patru studii, în care participanții au fost implicați în conversații ei înșiși sau au citit transcrieri ale conversațiilor altora, oamenii au avut tendința să nu realizeze că întrebarea ar influența – sau ar fi influențat – nivelul de prietenie dintre conversatori.