Có thuật toán nào để tính toán wNAF cho số mũ nhanh hơn bậc hai không?

Myria

22:36, 06/04/2023

Để thực hiện phép lũy thừa trong một nhóm mà việc đảo ngược dễ dàng, chẳng hạn như các nhóm đường cong elip, có một thuật toán để tính toán $w$NAF ("$w$mảng -ary dạng không liền kề") nhanh hơn $O(n^2)$? Các thuật toán tiêu chuẩn được liệt kê trên Wikipedia dưới dạng (được dịch sang Python):

def wnaf(d):
    kết quả = []
    cho tôi trong phạm vi (256):
        nếu d & 1:
            di = mod(d)
            d -= di
            kết quả += [di]
        khác:
            kết quả += [0]
        d >>= 1
    kết quả trả về[::-1]

Phần bậc hai ở đây là đi có thể âm, biến phép trừ thành phép cộng. Điều này có thể mang đến tận đầu số, vì vậy việc xử lý toàn bộ giá trị của đ có khả năng cần thiết cho mỗi lần lặp lại, làm cho thuật toán trở thành bậc hai về số lượng bit.

Có cách nào tốt hơn để làm điều này?

0 + 0

thực hiện

số học mô-đun

Điểm:2

Crypto

Daniel S

09:32, 07/04/2023

Câu hỏi vui! Câu trả lời là có. Bí quyết là sửa đổi vòng lặp theo dấu hiệu của cửa sổ cuối cùng. Nếu cửa sổ cuối cùng là số dương, chúng tôi bỏ qua các số 0 và dừng ở số 1 tiếp theo; nếu cửa sổ cuối cùng là âm, chúng tôi bỏ qua 1 giây và dừng ở 0 tiếp theo và lật nó. Tôi nghĩ rằng cũng có một bước cuối cùng cho cả điều này và thuật toán được trích dẫn trong câu hỏi nếu cửa sổ cuối cùng là âm, chúng ta cần thêm 1 vào trước. Đây là cách tốt nhất của tôi để thử một số con trăn cho các cửa sổ có chiều rộng $w$.

xác định wnaf2(d):
    kết quả = []
    dấu = 0
    trong khi d !=0:
        nếu (d & 1)^ký:
            di = mods(d^sign)
            sign = (d>>(w-1)&1) # Có trường hợp đưa cái này vào chức năng mod
            d = d>>w # Chỉ cần quét sạch cửa sổ cuối cùng mà không cần mang
            kết quả += [di]
            kết quả += (w-1)*[0]
        khác:
            kết quả += [0]
            d >>= 1
    nếu ký:
        kết quả += [1]
    kết quả trả về[::-1]

Đây là tuyến tính với điều kiện là chúng tôi đang đếm ca làm việc và che dấu là $O(1)$ hoạt động.

0 + 0

Myria

22:05, 08/04/2023

Các thay đổi và mặt nạ là $O(1)$ trong triển khai thực (tức là không phải Python) bởi vì thay vì thực sự chuyển toàn bộ `d`, chúng ta chỉ có thể lập chỉ mục các byte và bit. Điều này giải quyết vấn đề tôi đang gặp phải. Cảm ơn!

Hồi đáp

Phan Văn Trường

Câu hỏi này là trong các ngôn ngữ khác:

EN: Is there an algorithm to compute the wNAF for an exponent faster than quadratic?

TH: มีอัลกอริทึมในการคำนวณ wNAF สำหรับเลขชี้กำลังที่เร็วกว่ากำลังสองหรือไม่?

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

RU: Существует ли алгоритм для вычисления wNAF для показателя степени быстрее, чем квадратичный?

VI: Có thuật toán nào để tính toán wNAF cho số mũ nhanh hơn bậc hai không?

Đăng câu trả lời

Hầu hết mọi người không hiểu rằng việc đặt nhiều câu hỏi sẽ mở ra cơ hội học hỏi và cải thiện mối quan hệ giữa các cá nhân. Ví dụ, trong các nghiên cứu của Alison, mặc dù mọi người có thể nhớ chính xác có bao nhiêu câu hỏi đã được đặt ra trong các cuộc trò chuyện của họ, nhưng họ không trực giác nhận ra mối liên hệ giữa câu hỏi và sự yêu thích. Qua bốn nghiên cứu, trong đó những người tham gia tự tham gia vào các cuộc trò chuyện hoặc đọc bản ghi lại các cuộc trò chuyện của người khác, mọi người có xu hướng không nhận ra rằng việc đặt câu hỏi sẽ ảnh hưởng—hoặc đã ảnh hưởng—mức độ thân thiện giữa những người đối thoại.