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] Kiểm tra điểm thuộc đường cong

    Kiểm tra điểm thuộc đường cong Elliptic

    Cho đường cong Elliptic trên trường hữu hạn Fp\mathbb{F}_pFp​:

    E:y2≡x3+ax+b(modp)E: y^2 \equiv x^3 + a x + b \pmod{p}E:y2≡x3+ax+b(modp)

    với ppp nguyên tố. Điểm (x,y)(x, y)(x,y) thuộc đường cong nếu thỏa mãn phương trình trên.

    Cho p,a,bp, a, bp,a,b và điểm (x,y)(x, y)(x,y), hãy kiểm tra điểm có nằm trên đường cong hay không.

    Ví dụ

    Với p=17,a=2,b=2p=17, a=2, b=2p=17,a=2,b=2 và điểm (5,1)(5,1)(5,1): 12=11^2 = 112=1, còn 53+2⋅5+2=137≡1(mod17)5^3+2\cdot5+2 = 137 \equiv 1 \pmod{17}53+2⋅5+2=137≡1(mod17). Hai vế bằng nhau nên in YES.

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

      Dòng 1: ba số nguyên p a b. Dòng 2: hai số nguyên x y (0 ≤ x,y < p).

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

      5≤p≤1095 \le p \le 10^95≤p≤109, p nguyên tố; 0≤a,b<p0 \le a,b < p0≤a,b<p; 0≤x,y<p0 \le x,y < p0≤x,y<p.

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

      In YES nếu điểm thuộc đường cong, ngược lại in NO.

    Ví dụ:

    Đầu vào:

    17 2 2
5 1

    Đầu ra:

    YES

    Giải thích:

    1^2=1 và 5^3+2·5+2=137≡1 (mod 17), khớp nên YES.

    Đang tải editor...