Lanțuri de adunare-scădere cu dublare ieftină sau gratuită

Problemă conexă

Standard Lanțul de adunare-scădere (ASC) pentru un număr întreg $k$ defineşte ordinea operaţiilor de adunare/scădere (dublare) astfel încât $k$ se ajunge in sfarsit, incepand cu $1$. Acest lucru este util în special în calcularea ECC $k\cdot P$ prin adunări/scăderi și dubleri de puncte EC. Scopul este de a găsi ASC cât mai scurt posibil, astfel încât să fie utilizat un număr minim de operații de adunare/scădere/dublare. De exemplu., $(1,2,4,8,16,32,31)$ este un ASC pentru $31$ (cu multe adunări/dubleri și o scădere finală). Cu toate acestea, pare a fi o problemă dificilă să găsiți cel mai scurt ASC.

Problema mea

În ASC-urile standard, complexitatea dublării este considerat a fi echivalent cu adunarea/scăderea, prin urmare lungimea ASC poate fi măsura complexității. În scenariul meu, însă, dublarea este „gratis”. Acest lucru duce la o generalizare (să-i spunem ASC²), în care lanțul nu conține numere întregi, ci mai degrabă clase de echivalenţă de $\{k, 2k, 2^2k, 2^3k \ldots\} =: [k]$ pentru $k$ număr întreg impar. Adică, exemplul anterior poate fi scris foarte scurt ca $([1],[31])$ de cand $31 = -1 + 2^5\cdot 1$. Scopul este clar să găsiți cel mai scurt ASC².

Întrebări)

1. Există/sugerați vreo (euristică) metodă pentru găsirea unui ASC² "bun".?
2. Cum ar putea scurte ASC² fie generate, astfel încât lor optimitatea este garantat?
3. Btw există orice literatură despre asta?

Motivația

Implementând aritmetica peste numere întregi criptate (bit-cu-bit), ASC² ar fi utilă pentru multiplicarea scalară (adică, multiplicarea unui întreg criptat cu un întreg text simplu). Într-o astfel de reprezentare, dublarea unui text cifrat este într-adevăr ieftină: este doar adăugarea unei criptări triviale de zero la poziția cea mai puțin semnificativă. Pe de altă parte, adăugarea este foarte costisitoare (din moment ce folosește FHE), prin urmare, merită să găsiți cel mai bun ASC² posibil.

1. Cred că metoda ferestrei glisante (si este ruda NAF) folosit pentru a construi reprezentări bune ASC este încă destul de bun. Dacă separăm acțiunile de dublare de adunări și scăderi eterogene, ferestrele glisante nu reduce numărul de duble și beneficiul său este în reducerea numărului de adunări și scăderi eterogene din $O(\log k)$ la $O(\log k/\log\log k)$. În schimb, cred că există o limită inferioară a lungimii unui ASC² de $\log\log k$ întrucât numărul de apariții de 01 sau 10 în expansiunea binară poate, aproximativ, cel mult să se dubleze la fiecare pas.

2. Optimitatea este probabil să fie greu de arătat. Se știe, de exemplu, că calcularea ASC-urilor optime pentru un set de exponenți este NP-hard (vezi "Calculul secvențelor cu lanțuri de adunare", Peter Downey, Benton Leong și Ravi Sethi).

3. Literatura mai largă despre lanțurile ASC va acoperi unele dintre acestea. Aș recomanda să începeți cu autoritatea lui Donald Knuth „Arta programării computerelor” Vol. 2 secțiunea 4.6.3