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 Elliptic

    Đường cong elliptic dạng Weierstrass trên trường hữu hạn Zp\mathbb{Z}_pZp​ (ppp nguyên tố lẻ) được cho bởi phương trình: E:  y2≡x3+ax+b(modp)E:\; y^2 \equiv x^3 + ax + b \pmod{p}E:y2≡x3+ax+b(modp)

    Ngoài các điểm (x,y)(x,y)(x,y) với 0≤x,y<p0\le x,y<p0≤x,y<p thỏa mãn phương trình trên, đường cong còn có một điểm đặc biệt gọi là điểm ở vô cực, ký hiệu OOO, luôn được xem là thuộc đường cong.

    Cho tham số p,a,bp,a,bp,a,b và TTT điểm cần kiểm tra, hãy xác định mỗi điểm có thuộc EEE hay không.

    Ví dụ: với p=97,a=2,b=3p=97,a=2,b=3p=97,a=2,b=3: điểm (3,6)(3,6)(3,6) thuộc EEE vì 62=36≡33+2⋅3+3=36(mod97)6^2=36 \equiv 3^3+2\cdot3+3=36 \pmod{97}62=36≡33+2⋅3+3=36(mod97); điểm (3,7)(3,7)(3,7) không thuộc EEE vì 72=49≢367^2=49\not\equiv 3672=49≡36.

    • Định dạng đầu vào:
      • Dòng 1: ba số nguyên p a bp\ a\ bp a b.
      • Dòng 2: số nguyên TTT (1≤T≤10001\le T\le 10001≤T≤1000).
      • TTT dòng tiếp theo, mỗi dòng là "x yx\ yx y" (0≤x,y<p0\le x,y<p0≤x,y<p) hoặc chữ "O" (điểm vô cực).
    • Định dạng đầu ra:

      TTT dòng, mỗi dòng in "YES" nếu điểm thuộc EEE, ngược lại in "NO".

    Ví dụ:

    Đầu vào:

    97 2 3
4
3 6
3 7
0 10
1 1

    Đầu ra:

    YES
NO
YES
NO

    Đầu vào:

    97 2 3
1
O

    Đầu ra:

    YES

    Đang tải editor...