ปัญหาที่เกี่ยวข้อง
มาตรฐาน โซ่บวก-ลบ (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² ที่สั้นที่สุด.
คำถาม)
- มี / คุณจะแนะนำใด ๆ (ฮิวริสติก) วิธีการหา ASC² ที่ "ดี"?
- ได้อย่างไร ASC² สั้น ๆ ถูกสร้างขึ้นเพื่อให้พวกเขา ความเหมาะสม รับประกัน?
- มี btw อยู่หรือไม่ วรรณคดีใด ๆ เกี่ยวกับเรื่องนี้?
แรงจูงใจ
การใช้เลขคณิตกับจำนวนเต็มเข้ารหัส (บิตต่อบิต) ASC² จะมีประโยชน์สำหรับการคูณแบบสเกลาร์ (เช่น การคูณจำนวนเต็มเข้ารหัสด้วยจำนวนเต็มข้อความธรรมดา)
ในการนำเสนอดังกล่าว การเพิ่มไซเฟอร์เท็กซ์เป็นสองเท่านั้นมีราคาถูกจริง ๆ เป็นเพียงการเพิ่มการเข้ารหัสเล็กน้อยที่ศูนย์ไปยังตำแหน่งที่มีนัยสำคัญน้อยที่สุด
ในทางกลับกัน การเติมมีราคาแพงมาก (เนื่องจากใช้ FHE) ดังนั้นจึงคุ้มค่าที่จะหา ASC² ที่ดีที่สุดเท่าที่จะเป็นไปได้