Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [An toàn thông tin] Nhân vô hướng kP

    Nhân vô hướng kP (thuật toán nhân đôi và cộng)

    Phép nhân vô hướng kP=P+P+⋯+P⏟kkP = \underbrace{P+P+\dots+P}_{k}kP=kP+P+⋯+P​​ được tính hiệu quả bằng double-and-add: duyệt các bit của kkk, mỗi bước nhân đôi điểm tích lũy và cộng PPP khi bit bằng 1. Độ phức tạp O(log⁡k)O(\log k)O(logk).

    Quy ước: 0⋅P=O0\cdot P = \mathcal{O}0⋅P=O.

    Ví dụ

    Trên p=17,a=2,b=2p=17,a=2,b=2p=17,a=2,b=2, G=(5,1)G=(5,1)G=(5,1): 3G=(10,6)3G=(10,6)3G=(10,6).

    • Định dạng đầu vào:

      Dòng 1: p a b. Dòng 2: số nguyên kkk và điểm PPP: k x y (hoặc k O).

    • Ràng buộc đầu vào:

      5≤p≤1095 \le p \le 10^95≤p≤109, p nguyên tố; 0≤k≤10180 \le k \le 10^{18}0≤k≤1018; PPP thuộc đường cong.

    • Định dạng đầu ra:

      In kPkPkP (O hoặc x y).

    Ví dụ:

    Đầu vào:

    17 2 2
3 5 1

    Đầu ra:

    10 6

    Giải thích:

    3·(5,1)=(10,6).

    Đang tải editor...