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] Đếm số điểm trên đường cong

    Đếm số điểm trên đường cong

    Bậc (order) của đường cong #E\#E#E là tổng số điểm hữu hạn cộng thêm điểm vô cực O\mathcal{O}O:

    #E=1+∑x=0p−1(soˆˊ nghiệm y của y2≡x3+ax+b)\#E = 1 + \sum_{x=0}^{p-1} \big(\text{số nghiệm } y \text{ của } y^2 \equiv x^3+ax+b\big)#E=1+∑x=0p−1​(soˆˊ nghiệm y của y2≡x3+ax+b)

    Theo định lý Hasse, #E\#E#E nằm trong khoảng p+1±2pp+1 \pm 2\sqrt{p}p+1±2p​.

    Ví dụ

    Trên p=17,a=2,b=2p=17,a=2,b=2p=17,a=2,b=2 có #E=19\#E = 19#E=19.

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

      Một dòng: p a b.

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

      5≤p≤50005 \le p \le 50005≤p≤5000, p nguyên tố; đường cong không suy biến.

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

      In một số nguyên là #E\#E#E (đã tính cả điểm vô cực).

    Ví dụ:

    Đầu vào:

    17 2 2

    Đầu ra:

    19

    Giải thích:

    Đường cong này có 19 điểm kể cả O.

    Đang tải editor...