vấn đề liên quan
Tiêu chuẩn Chuỗi cộng-trừ (ASC) cho một số nguyên $k$ xác định thứ tự của các phép tính cộng/trừ (nhân đôi) sao cho $k$ cuối cùng đã đạt được, bắt đầu với $1$.
Điều này đặc biệt hữu ích trong ECC để tính toán $k\cdot P$ thông qua cộng/trừ và nhân đôi điểm EC.
Mục tiêu là tìm ASC càng ngắn càng tốt, để sử dụng số lượng phép toán cộng/trừ/nhân đôi tối thiểu.
Ví dụ., $(1,2,4,8,16,32,31)$ là một ASC cho $31$ (với nhiều phép cộng/nhân đôi và phép trừ cuối cùng).
Tuy nhiên, có vẻ như là một vấn đề khó khăn để tìm ra ASC ngắn nhất.
Vấn đề của tôi
Trong ASC tiêu chuẩn, sự phức tạp của việc nhân đôi được coi là tương đương với cộng/trừ, do đó độ dài của ASC có thể là thước đo độ phức tạp.
Trong kịch bản của tôi, tuy nhiên, nhân đôi là "miễn phí".
Điều này dẫn đến một khái quát hóa (hãy gọi nó là ASC²), trong đó chuỗi không chứa số nguyên, mà là các lớp tương đương của $\{k, 2k, 2^2k, 2^3k \ldots\} =: [k]$ vì $k$ số nguyên lẻ.
Tức là, ví dụ trước có thể được viết rất ngắn gọn dưới dạng $([1],[31])$ từ $31 = -1 + 2^5\cdot 1$.
Mục tiêu rõ ràng là để tìm ASC² ngắn nhất.
(các) câu hỏi
- Có/bạn sẽ đề xuất bất kỳ (heuristic) nào phương pháp tìm ASC² "tốt"?
- Làm thế nào có thể ASC² ngắn được tạo ra, để chúng sự tối ưu được đảm bảo?
- Có btw tồn tại bất kỳ văn học về điều này?
Động lực
Thực hiện phép tính số học trên các số nguyên được mã hóa (từng bit), ASC² sẽ hữu ích cho phép nhân vô hướng (nghĩa là nhân một số nguyên được mã hóa với một số nguyên văn bản gốc).
Trong một biểu diễn như vậy, việc nhân đôi một bản mã thực sự là rẻ: nó chỉ là thêm một mã hóa tầm thường của số 0 vào vị trí ít quan trọng nhất.
Mặt khác, việc bổ sung rất tốn kém (vì nó đang sử dụng FHE), do đó, đáng để tìm ASC² tốt nhất có thể.
