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 điểm bằng thuật toán Double-and-Add

    Cho điểm cơ sở G=(x,y)G=(x,y)G=(x,y) trên đường cong elliptic E:y2≡x3+ax+b(modp)E: y^2\equiv x^3+ax+b\pmod pE:y2≡x3+ax+b(modp) (G≠OG\neq OG=O). Với số nguyên không âm kkk (có thể rất lớn, tới 101810^{18}1018), điểm kGkGkG (cộng GGG với chính nó kkk lần) không được tính bằng cách lặp cộng kkk lần (quá chậm), mà phải dùng thuật toán Double-and-Add: duyệt các bit của kkk từ thấp lên cao, ở mỗi bước nhân đôi một điểm tích lũy và cộng dồn GGG hiện tại (đã nhân đôi) vào kết quả nếu bit tương ứng bằng 1. Quy ước 0⋅G=O0\cdot G=O0⋅G=O.

    Cho TTT truy vấn giá trị kkk, hãy tính kGkGkG cho mỗi truy vấn.

    Ví dụ: p=97,a=2,b=3p=97,a=2,b=3p=97,a=2,b=3, G=(0,10)G=(0,10)G=(0,10): 2G=(65,32)2G=(65,32)2G=(65,32).

    • Định dạng đầu vào:
      • Dòng 1: ba số nguyên p a bp\ a\ bp a b.
      • Dòng 2: "x y" là tọa độ điểm GGG.
      • Dòng 3: số nguyên TTT (1≤T≤2001\le T\le 2001≤T≤200).
      • TTT dòng tiếp theo, mỗi dòng một số nguyên kkk (0≤k≤10180\le k\le 10^{18}0≤k≤1018).
    • Định dạng đầu ra:

      TTT dòng, mỗi dòng in kết quả kGkGkG dạng "x y", hoặc "O" nếu kết quả là điểm vô cực.

    Ví dụ:

    Đầu vào:

    97 2 3
0 10
6
0
1
2
50
7
1000000000000000000

    Đầu ra:

    O
0 10
65 32
O
10 76
O

    Đầu vào:

    97 2 3
0 10
1
49

    Đầu ra:

    0 87

    Đang tải editor...