ฉันกำลังดูพื้นฐานของ ecc และพบตัวอย่างจากอินเทอร์เน็ตไม่ว่าจะใช้เส้นโค้งโดเมนต่อเนื่องหรือใช้จำนวนเฉพาะที่น้อยมาก หน้า เช่น 17 ในโดเมนแยกเพื่อแสดงคะแนน
ฉันอยากรู้จริงๆว่าถ้าฉันสามารถหาจุดที่มีขนาดใหญ่จริงๆ หน้า ในทางปฏิบัติ ตัวอย่างเช่น secp256k1 กำลังใช้ขนาดใหญ่มาก หน้า=2^256â2^32â977 ในโดเมน (p,a,b,G,n,h)
ด้านล่างนี้เป็นรหัสหลามที่ฉันใช้เพื่อหักจำนวนเต็มที่เป็นไปได้ของ y จากการแก้สมการด้วยช่วงของจำนวนเต็ม x. ฉันประหลาดใจที่ไม่มีการค้นหาแม้แต่ในช่วง 1 ล้าน!
ดังนั้นคำถามของฉันคือรหัสด้านล่างถูกต้องหรือไม่ และประการที่สอง หากถูกต้องหรือแก้ไขโดยผู้เชี่ยวชาญจริง ควรลองใช้ช่วงค่าใด
ป.ล.
ฉันสงสัยว่าจุดกำเนิดเป็นอย่างไร ช ถูกเลือกด้วย แต่นั่นอาจต้องการความเข้าใจที่ลึกซึ้งยิ่งขึ้นในหัวข้อ
นำเข้าคณิตศาสตร์
#secp256k1
# y**2 = x**3 + 7 (mod p)
P = 2**256 - 2**32 - 977
เอ = 0
ข = 7
#nistP256
P = 115792089210356248762697446949407573530086143415290314195533631308867097853951
เอ = -3
B = 41058363725152142129326129780047268409114441015993725554835256314039467401291
def in_curve(x):
เส้นโค้ง = x**3 + A*x + B
y_float = math.sqrt (เส้นโค้ง)
ถ้า abs(math.modf(y_float)[0]) < 0.0001 หรือ \
(1 - abs(math.modf(y_float)[0]) < 0.0001):
# พิมพ์ (y_float)
# ข้อบกพร่อง: y_int = int(math.modf(y_float)[1])
y_int = int (รอบ (y_float))
ถ้า y_int * y_int == (เส้นโค้ง):
พิมพ์ (y_int)
ส่งคืน y_int
กลับไม่มี
สำหรับ x ในช่วง (1, 1000000):
y = in_curve(x)
ถ้า y ไม่ใช่ไม่มี:
พิมพ์(x, y)
รหัสก่อนหน้านี้ผิด เนื่องจากทศนิยม sqrt() จะทำให้เกิดข้อผิดพลาดที่ยอมรับไม่ได้เมื่อแปลงกลับเป็นจำนวนเต็ม
แต่หลังจากเปลี่ยน คณิตศาสตร์ sqrt() ถึง คณิตศาสตร์.isqrt()มันยังไม่ทำให้สิ่งต่าง ๆ สมเหตุสมผล
ขอบคุณคำแนะนำจากทุกท่านที่ตอบในกระทู้ การใช้จุดกำเนิดเพื่อตรวจสอบอัลกอริทึมของฉัน ตอนนี้ฉันรู้อย่างชัดเจนว่าทำไมฉันถึงล้มเหลว
ประเด็นคือนอกจากใช้ % สำหรับการคูณและการบวกทั้งหมด I ควร ยังใช้รากที่สองแบบแยกส่วนเพื่อหาคำตอบ แทน จำนวนเต็ม สแควร์รูท พร้อมด้วย %. นั่นเป็นการใช้ในทางที่ผิดโดยสิ้นเชิง % แน่นอน
รหัสที่แก้ไขผ่านการทดสอบด้วยเวกเตอร์ทดสอบบางตัว
นำเข้าโมดูลาร์_sqrt
# เช่น. ฉันใช้รหัสจาก https://eli.thegreenplace.net/2009/03/07/computing-modular-square-roots-in-python
# โปรดขออนุญาตหากการใช้งานอยู่นอกเหนือขอบเขตของงานอดิเรกเพื่อการศึกษา และระบุเครดิตว่าเป็นมนุษย์ที่ดีเสมอ ;-)
# nist P256 นำมาจาก https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-186-draft.pdf
P = 115792089210356248762697446949407573530086143415290314195533631308867097853951
เอ = -3
B = 41058363725152142129326129780047268409114441015993725554835256314039467401291
Gx = 48439561293906451759052585252797914202762949526041747995844080717082404635286
G = 36134250956749795798585127919587881956611106672985015071877198253568414405109
def get_y_in_curve(x):
y2 = x**3 + A*x + B
y_int = modular_sqrt(y2, พี)
ถ้า y_int และ ((y_int * y_int) % P) == (y2 % P):
ส่งคืน y_int
กลับไม่มี
ยืนยัน get_y_in_curve(Gx) == Gy
ฉันไม่ค่อยแน่ใจว่าคุณหมายถึงอะไร $p$ และฉันไม่แน่ใจว่าคุณหมายถึงอะไรเพื่อให้โค้ดพิมพ์ออกมา
อย่างไรก็ตาม ดูเหมือนว่าคุณกำลังพยายามหาจุดที่มีค่าเป็นจำนวนเต็มบนเส้นโค้งวงรี $y^2=x^3+7$ โดยหมดแรง $x$ ค่าและฉันไม่พบจุดบกพร่องนอกเหนือจากคำสั่งพิมพ์ แต่ซีเกลแสดงให้เห็นว่าโดยทั่วไปเส้นโค้งวงรีเหนือจำนวนตรรกยะจะมีจำนวนเต็มจำนวนจำกัดเท่านั้น และเราคาดว่าสิ่งเหล่านี้จะหายากมาก ในความเป็นจริงสำหรับ เส้นโค้งที่คุณเลือก ไม่มีจุดจำนวนเต็ม แต่อย่างใด
คุณอาจกำลังพยายามหาจำนวนเต็ม $x$ และ $y$ ดังนั้น $y^2\equiv x^3+7\pmod p$ สำหรับนายกใหญ่บางคน $p$. ในกรณีนี้คุณควรใช้ mod รากที่สอง $p$ มากกว่าจำนวนจริง สิ่งนี้ใช้ การคำนวณที่แตกต่างกัน. การเลือกนายกขนาดใหญ่ $p$ แล้วทำการใด ๆ $x$ มูลค่ามีโอกาสประมาณ 50% ในการค้นหาที่เหมาะสม $y$ โดยการหารากที่สองแบบโมดูลาร์ของ $x^3+17$.
คนส่วนใหญ่ไม่เข้าใจว่าการถามคำถามมากมายจะปลดล็อกการเรียนรู้และปรับปรุงความสัมพันธ์ระหว่างบุคคล ตัวอย่างเช่น ในการศึกษาของ Alison แม้ว่าผู้คนจะจำได้อย่างแม่นยำว่ามีคำถามกี่ข้อที่ถูกถามในการสนทนา แต่พวกเขาไม่เข้าใจความเชื่อมโยงระหว่างคำถามและความชอบ จากการศึกษาทั้ง 4 เรื่องที่ผู้เข้าร่วมมีส่วนร่วมในการสนทนาด้วยตนเองหรืออ่านบันทึกการสนทนาของผู้อื่น ผู้คนมักไม่ตระหนักว่าการถามคำถามจะมีอิทธิพลหรือมีอิทธิพลต่อระดับมิตรภาพระหว่างผู้สนทนา
