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] Tìm y từ x

    Tìm tung độ y từ hoành độ x

    Cho đường cong E:y2=x3+ax+bE: y^2 = x^3 + a x + bE:y2=x3+ax+b trên Fp\mathbb{F}_pFp​ và một hoành độ xxx. Cần tìm mọi y∈{0,1,…,p−1}y \in \{0,1,\dots,p-1\}y∈{0,1,…,p−1} sao cho (x,y)(x,y)(x,y) thuộc đường cong, tức là:

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

    Nếu vế phải là thặng dư bậc hai thì có 2 nghiệm (hoặc 1 nghiệm khi y=0y=0y=0); nếu là không thặng dư thì không có yyy nào.

    Ví dụ

    Với p=17,a=2,b=2,x=5p=17, a=2, b=2, x=5p=17,a=2,b=2,x=5: vế phải =1=1=1, các yyy thỏa mãn là 111 và 161616.

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

      Dòng 1: p a b. Dòng 2: một số nguyên x.

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

      5≤p≤50005 \le p \le 50005≤p≤5000, p nguyên tố; 0≤x<p0 \le x < p0≤x<p.

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

      In các giá trị yyy hợp lệ theo thứ tự tăng dần, cách nhau bởi dấu cách. Nếu không có, in KHONG CO.

    Ví dụ:

    Đầu vào:

    17 2 2
5

    Đầu ra:

    1 16

    Giải thích:

    Vế phải=1, các y là 1 và 16.

    Đang tải editor...