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] Cộng hai điểm

    Cộng hai điểm trên đường cong Elliptic

    Với hai điểm P=(x1,y1)P=(x_1,y_1)P=(x1​,y1​), Q=(x2,y2)Q=(x_2,y_2)Q=(x2​,y2​) trên E:y2=x3+ax+bE: y^2=x^3+ax+bE:y2=x3+ax+b trong Fp\mathbb{F}_pFp​, phép cộng R=P+Q=(x3,y3)R=P+Q=(x_3,y_3)R=P+Q=(x3​,y3​):

    • Nếu P=OP=\mathcal{O}P=O thì R=QR=QR=Q; nếu Q=OQ=\mathcal{O}Q=O thì R=PR=PR=P.
    • Nếu x1=x2x_1=x_2x1​=x2​ và y1=−y2y_1=-y_2y1​=−y2​ thì R=OR=\mathcal{O}R=O.
    • Ngược lại hệ số góc: nếu P≠QP\ne QP=Q: λ=y2−y1x2−x1\lambda=\dfrac{y_2-y_1}{x_2-x_1}λ=x2​−x1​y2​−y1​​; nếu P=QP=QP=Q: λ=3x12+a2y1\lambda=\dfrac{3x_1^2+a}{2y_1}λ=2y1​3x12​+a​ (mọi phép chia là nghịch đảo modulo ppp).

    Khi đó x3=λ2−x1−x2x_3=\lambda^2-x_1-x_2x3​=λ2−x1​−x2​, y3=λ(x1−x3)−y1(modp)y_3=\lambda(x_1-x_3)-y_1 \pmod py3​=λ(x1​−x3​)−y1​(modp).

    Ví dụ

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

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

      Dòng 1: p a b. Dòng 2: điểm PPP (O hoặc x y). Dòng 3: điểm QQQ (O hoặc x y).

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

      5≤p≤1095 \le p \le 10^95≤p≤109, p nguyên tố; các điểm thuộc đường cong.

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

      In R=P+QR=P+QR=P+Q (O hoặc x y).

    Ví dụ:

    Đầu vào:

    17 2 2
5 1
6 3

    Đầu ra:

    10 6

    Giải thích:

    (5,1)+(6,3) cho điểm (10,6).

    Đang tải editor...