Điểm:1

Làm cách nào để tìm điểm nguyên của đường cong ec trong một phạm vi nhất định?

lá cờ it

Tôi đã xem xét nội dung cơ bản của ecc và tìm thấy các ví dụ từ Internet sử dụng đường cong miền liên tục hoặc sử dụng số nguyên tố rất nhỏ P như 17 trong một miền riêng biệt để hiển thị các điểm.

Tôi thực sự tò mò rằng nếu tôi có thể tìm thấy một điểm thực sự lớn P trong thực tế. Ví dụ, secp256k1 đang sử dụng một P=2^256â2^32â977 trong miền (p,a,b,G,n,h).

Dưới đây là mã python tôi sử dụng để trừ số nguyên có thể có của y khỏi việc giải phương trình với phạm vi số nguyên x. Tôi ngạc nhiên rằng không có tìm thấy ngay cả trong phạm vi 1 triệu!

Vì vậy, câu hỏi của tôi là, mã bên dưới phải không? Và thứ hai, nếu nó đúng hoặc được sửa bởi một số chuyên gia thực sự, tôi nên thử phạm vi giá trị nào?

Tái bút Tôi tự hỏi làm thế nào điểm máy phát điện g cũng được chọn. Nhưng điều đó có thể cần hiểu sâu hơn về chủ đề này.

nhập toán

# secp256k1
# y**2 = x**3 + 7 (mod p)
P = 2**256 - 2**32 - 977
một = 0
B = 7

#nist P256
P = 115792089210356248762697446949407573530086143415290314195533631308867097853951
A = -3
B = 41058363725152142129326129780047268409114441015993725554835256314039467401291

xác định in_curve(x):
    đường cong = x**3 + A*x + B
    y_float = math.sqrt(đường cong)
    nếu abs(math.modf(y_float)[0]) < 0,0001 hoặc \
          (1 - abs(math.modf(y_float)[0]) < 0,0001):
        # in(y_float)
        # lỗi: y_int = int(math.modf(y_float)[1])
        y_int = int(vòng(y_float))
        nếu y_int * y_int == (đường cong):
            in(y_int)
            trả lại y_int
    trở lại Không có
 
cho x trong phạm vi (1, 1000000):
    y = in_curve(x)
    nếu y không phải là Không có:
        in(x, y)

cập nhật 1

Mã trước đó là sai, vì dấu phẩy động sqrt() sẽ gây ra lỗi không thể chấp nhận được khi chuyển đổi nó trở lại số nguyên.

Nhưng, sau khi thay thế toán.sqrt() đến toán.isqrt(), nó vẫn không làm cho mọi thứ trở nên hợp lý.

cập nhật 2

Nhờ những lời khuyên từ tất cả trả lời trong chủ đề. Sử dụng điểm tạo để xác minh thuật toán của tôi, giờ đây tôi biết rõ ràng tại sao mình thất bại.

Vấn đề là ngoài việc sử dụng % cho tất cả phép nhân và phép cộng, tôi Nên cũng sử dụng căn bậc hai mô-đun để tìm giải pháp, thay vì căn bậc hai số nguyên cùng với %. Đó hoàn toàn là một sự lạm dụng % chắc chắn.

Mã sửa đổi vượt qua bài kiểm tra với một số vectơ kiểm tra.

nhập mô-đun_sqrt
#  ví dụ. Tôi đã sử dụng mã từ https://eli.thegreenplace.net/2009/03/07/computing-modular-square-roots-in-python
# vui lòng xin phép nếu việc sử dụng vượt quá phạm vi sở thích giáo dục và luôn liệt kê tín dụng là một con người tử tế ;-)

# nist P256, lấy từ https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-186-draft.pdf
P = 115792089210356248762697446949407573530086143415290314195533631308867097853951
A = -3
B = 41058363725152142129326129780047268409114441015993725554835256314039467401291
Gx = 48439561293906451759052585252797914202762949526041747995844080717082404635286
Gy = 36134250956749795798585127919587881956611106672985015071877198253568414405109

chắc chắn get_y_in_curve(x):
    y2 = x**3 + A*x + B
    y_int = modul_sqrt(y2, P)
    nếu y_int và ((y_int * y_int) % P) == (y2 % P):
        trả lại y_int
    trở lại Không có

khẳng định get_y_in_curve(Gx) == Gy
fgrieu avatar
lá cờ ng
Mã không chính xác. Vấn đề chính là tiền điện tử Đường cong Elliptic không hoạt động với $x$ và $y$ trong một tập hợp vô hạn. Nó sử dụng một [trường hữu hạn](https://en.wikipedia.org/wiki/Finite_field). secp256k1 sử dụng trường $\mathbb F_p$, cũng như [vòng số nguyên modulo](https://en.wikipedia.org/w/index.php?title=Ring_of_integers_modulo_n) $p$. Vì vậy, mã sẽ tính toán `đường cong` modulo giảm `P` của nó, và tính toán (khi nó tồn tại) một căn bậc hai mô-đun của nó; xem [điều này](https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm) để biết một phương pháp. Vui lòng cải thiện hoặc đóng câu hỏi.
Match Man avatar
lá cờ it
@fgrieu Vâng, tôi đã nhận ra sai lầm của mình ngay sau khi Daniel chỉ ra. Bây giờ câu hỏi được cập nhật với thuật toán đã sửa. Bạn có muốn tôi đóng câu hỏi vì nó * đã * sai không? Hoặc giữ nó như một ví dụ về cách mọi thứ nên được thực hiện trong Không gian hữu hạn của ECC. Hay thậm chí mọi thứ có thể sai như thế nào khi nhảy từ "đường cong" không gian vô hạn sang không gian hữu hạn? :)
fgrieu avatar
lá cờ ng
Câu hỏi được cập nhật là OK. Vì câu trả lời đã giúp, tôi nghĩ tốt nhất là chấp nhận nó, và tất cả sẽ ổn thôi. Lưu ý về mã mới: sẽ tốt hơn nếu đổi tên `curve` thành `y2` ; tính toán nó theo modulo `P` trước đó (ví dụ: `y2 = (x**3 + A*x + B) % P` hoặc `y2 = (pow(x, 3, P) + A*x + B) % P )` ; và để sử dụng lại nó trong `y_int = modul_sqrt(y2)` và `if ((y_int * y_int) % P) == y2:`. Không rõ ngay lập tức `module_sqrt` sẽ làm gì khi nó bị lỗi. Một cách độc lập, việc sử dụng `module_sqrt` của người khác có ổn trong ngữ cảnh không? Đó là phần liên quan!
Match Man avatar
lá cờ it
Mã được tái cấu trúc. modul_sqrt sẽ trả về 0 nếu lỗi và mã mới cũng đã thêm kiểm tra đó. Tôi không sử dụng trực tiếp mã của Eli nhưng lấy mã của anh ấy làm ví dụ.
Điểm:3
lá cờ ru

Tôi không chắc ý của bạn là gì $p$ và tôi không chắc ý của bạn là gì khi mã của bạn được in ra.

Tuy nhiên, có vẻ như bạn đang cố tìm các điểm có giá trị nguyên trên đường cong elip $y^2=x^3+7$ bằng cách kiệt sức $x$ các giá trị và tôi không thể phát hiện ra lỗi nào ngoài câu lệnh in. NHƯNG Siegel đã chỉ ra rằng nói chung các đường cong elliptic trên các số hữu tỷ chỉ có một số hữu hạn các điểm có giá trị nguyên và chúng tôi cho rằng những điểm này thực sự rất hiếm. Trên thực tế đối với đường cong mà bạn đã chọn không có điểm số nguyên nào.

Bạn có thể đang cố gắng tìm số nguyên $x$$y$ để có thể $y^2\equiv x^3+7\pmod p$ cho một số nguyên tố lớn $p$. Trong trường hợp này bạn nên lấy căn bậc hai mod $p$ hơn là trên các con số thực. Điều này sử dụng một phép tính khác. Chọn một số nguyên tố lớn $p$ và sau đó lấy bất kỳ $x$ giá trị có khoảng 50% cơ hội tìm thấy một giá trị phù hợp $y$ bằng cách lấy một căn bậc hai mô-đun của $x^3+17$.

Match Man avatar
lá cờ it
Tôi đã thêm ý nghĩa của `p` trong câu hỏi. Nó lớn đến mức tôi không phải điều chế với bất kỳ số nhỏ nào như 1 tỷ... > Trên thực tế, đối với đường cong mà bạn đã chọn, không có điểm nguyên nào.
Daniel S avatar
lá cờ ru
Ồ tôi hiểu rồi. Trong trường hợp đó, nếu bạn cố gắng tạo ra các điểm mà không sử dụng bất kỳ số học mô-đun nào, thì nó sẽ không hoạt động vì khi đó chúng sẽ là các điểm tích phân và không có điểm nào trên đường cong này. Lưu ý rằng các số "nhỏ" không phải là số chính phương vẫn có thể có căn bậc hai mod $p$ nếu một người sẵn sàng sử dụng số học mô-đun.
Match Man avatar
lá cờ it
Ý bạn là tôi nên thay đổi if y_int * y_int == (x^3 + 7) thành if y_int * y_int == (x^3 + 7) % P, trong đó P = 2^256â2^32â 977? Tôi hiểu rằng secp256k1 được xác định trên â¤p, vì vậy phép tính dấu phẩy động trước đó chỉ để tìm xem y có đủ gần để trở thành một số nguyên hay không. Thực sự có rất nhiều ứng cử viên khả thi trong 1 triệu nhưng không ai trong số họ thực sự là một...
Daniel S avatar
lá cờ ru
Không. Ý tôi là (dựa trên thực tế là $p\equiv 3\pmod 4$), bạn nên thay thế y_float=math.sqrt(x^3+7) bằng y_int=pow(x^3+7,(p+ 1)/4,p) rồi kiểm tra xem y_int*y_int==(x^3+7)%p. Điều này sẽ không cung cấp cho bạn giá trị nhỏ của $y$, nhưng không có giải pháp nào có giá trị nhỏ của cả $x$ và $y$. Kiểm tra liên kết về cách tính căn bậc hai mod $p$.
Match Man avatar
lá cờ it
Hiểu rồi. Câu hỏi được cập nhật với hoạt động chính xác ngay bây giờ. Cảm ơn.

Đăng câu trả lời

Hầu hết mọi người không hiểu rằng việc đặt nhiều câu hỏi sẽ mở ra cơ hội học hỏi và cải thiện mối quan hệ giữa các cá nhân. Ví dụ, trong các nghiên cứu của Alison, mặc dù mọi người có thể nhớ chính xác có bao nhiêu câu hỏi đã được đặt ra trong các cuộc trò chuyện của họ, nhưng họ không trực giác nhận ra mối liên hệ giữa câu hỏi và sự yêu thích. Qua bốn nghiên cứu, trong đó những người tham gia tự tham gia vào các cuộc trò chuyện hoặc đọc bản ghi lại các cuộc trò chuyện của người khác, mọi người có xu hướng không nhận ra rằng việc đặt câu hỏi sẽ ảnh hưởng—hoặc đã ảnh hưởng—mức độ thân thiện giữa những người đối thoại.