โซ่การบวก-ลบที่มีการเพิ่มขึ้นเป็นสองเท่าในราคาถูกหรือฟรี

ปัญหาที่เกี่ยวข้อง

มาตรฐาน โซ่บวก-ลบ (ASC) สำหรับจำนวนเต็ม $k$ กำหนดลำดับของการดำเนินการบวก / ลบ (สองเท่า) เพื่อให้ $k$ ถึงที่สุดแล้วโดยเริ่มจาก $1$. สิ่งนี้มีประโยชน์อย่างยิ่งในการคำนวณ ECC $k\cdot P$ ผ่านการเพิ่ม/ลบจุด EC และการเสแสร้ง เป้าหมายคือการค้นหา ASC ให้สั้นที่สุดเพื่อให้ใช้การบวก/ลบ/การเสแสร้งจำนวนน้อยที่สุด เช่น., $(1,2,4,8,16,32,31)$ เป็น ASC สำหรับ $31$ (ด้วยการบวก/เสแสร้งและการลบขั้นสุดท้าย) อย่างไรก็ตาม การค้นหา ASC ที่สั้นที่สุดดูเหมือนจะเป็นปัญหาที่ยาก

ปัญหาของฉัน

ในมาตรฐาน ASC's, the ความซับซ้อนของการทวีคูณ ถือว่าเป็น เท่ากับการบวก/ลบดังนั้นความยาวของ ASC จึงสามารถวัดความซับซ้อนได้ อย่างไรก็ตามในสถานการณ์ของฉัน สองเท่าคือ "ฟรี". สิ่งนี้นำไปสู่การทำให้เป็นภาพรวม (เรียกว่า ASC²) โดยที่เชนไม่มีจำนวนเต็ม แต่แทนที่จะเป็น ชั้นเรียนที่เท่าเทียมกัน ของ $\{k, 2k, 2^2k, 2^3k \ldots\} =: [k]$ สำหรับ $k$ จำนวนเต็มคี่ นั่นคือตัวอย่างก่อนหน้านี้สามารถเขียนได้ไม่นานเช่น $([1],[31])$ เนื่องจาก $31 = -1 + 2^5\cdot 1$. เป้าหมายที่ชัดเจนคือ ค้นหา ASC² ที่สั้นที่สุด.

คำถาม)

1. มี / คุณจะแนะนำใด ๆ (ฮิวริสติก) วิธีการหา ASC² ที่ "ดี"?
2. ได้อย่างไร ASC² สั้น ๆ ถูกสร้างขึ้นเพื่อให้พวกเขา ความเหมาะสม รับประกัน?
3. มี btw อยู่หรือไม่ วรรณคดีใด ๆ เกี่ยวกับเรื่องนี้?

แรงจูงใจ

การใช้เลขคณิตกับจำนวนเต็มเข้ารหัส (บิตต่อบิต) ASC² จะมีประโยชน์สำหรับการคูณแบบสเกลาร์ (เช่น การคูณจำนวนเต็มเข้ารหัสด้วยจำนวนเต็มข้อความธรรมดา) ในการนำเสนอดังกล่าว การเพิ่มไซเฟอร์เท็กซ์เป็นสองเท่านั้นมีราคาถูกจริง ๆ เป็นเพียงการเพิ่มการเข้ารหัสเล็กน้อยที่ศูนย์ไปยังตำแหน่งที่มีนัยสำคัญน้อยที่สุด ในทางกลับกัน การเติมมีราคาแพงมาก (เนื่องจากใช้ FHE) ดังนั้นจึงคุ้มค่าที่จะหา ASC² ที่ดีที่สุดเท่าที่จะเป็นไปได้

1. ผมคิดว่า วิธีหน้าต่างบานเลื่อน (และมัน ญาตินาฟ) ใช้ในการสร้างตัวแทน ASC ที่ดีก็ยังค่อนข้างดี หากเราแยกการกระทำสองเท่าออกจากการบวกและการลบที่ต่างกัน หน้าต่างบานเลื่อนจะไม่ลดจำนวนการทวีคูณ และประโยชน์ของมันคือการลดจำนวนการบวกและการลบที่ต่างกันจาก $O(\log k)$ ถึง $O(\log k/\log\log k)$. ในทางกลับกัน ฉันคิดว่ามีขอบเขตที่ต่ำกว่าความยาวของ ASC² ของ $\log\log k$ เนื่องจากจำนวนครั้งที่เกิด 01 หรือ 10 ในการขยายแบบไบนารีอาจพูดได้มากที่สุดสองเท่าโดยประมาณในแต่ละขั้นตอน

2. การเพิ่มประสิทธิภาพมักจะแสดงได้ยาก เป็นที่ทราบกันดีอยู่แล้วว่าการคำนวณ ASC ที่ดีที่สุดสำหรับชุดของเลขยกกำลังคือ NP-hard (ดู "ลำดับการคำนวณด้วยโซ่เพิ่มเติม", Peter Downey, Benton Leong และ Ravi Sethi)

3. วรรณกรรมที่กว้างขึ้นเกี่ยวกับเครือข่าย ASC จะครอบคลุมบางส่วนนี้ ฉันขอแนะนำให้เริ่มต้นด้วย "Art of Computer Programming" ฉบับที่เชื่อถือได้ของ Donald Knuth 2 ส่วน 4.6.3