Score:2

มีเหตุผลใดที่ต้องค้นหาค่า Z ที่นอกเหนือจาก 1 เมื่อแปลง X,Y เป็น Jacobian แทนค่า EC Point

ธง om

เมื่อแลกเปลี่ยนรหัสสาธารณะ ฉันมักจะได้รับรูปแบบการบีบอัดของ เอ็กซ์, วาย พิกัด. หากต้องการเพิ่มความเร็ว ฉันต้องแสดงสิ่งนั้นใน Jacobean x,y,z รูปร่าง.

Z=1 ตอบสนองทุกอย่างและดูที่ความเร็ว (https://th.wikibooks.org/wiki/Cryptography/Prime_Curve/Jacobian_Coordinates, http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian.html) ฉันไม่เห็นเหตุผลที่ชัดเจนว่าทำไม Z=1 จะช้ากว่า (หรือเร็วกว่า) กว่าอย่างอื่น Zนี่เป็นคำถามที่ถูกต้องหรือไม่ ช่วยชี้ทางให้ฉันหน่อยได้ไหมว่า "มันดูสมเหตุสมผลไหมที่จะมองหา Z นอกเหนือจาก 1?”

kelalaka avatar
in flag
ไม่ชัดเจนเหรอ? $Z^4$ นั่นคือ 1 เมื่อ $Z=1$ และสำหรับกรณีอื่นๆ เราต้องการ 3 เท่า
T. Rossi avatar
om flag
ขอบคุณสำหรับคำตอบอย่างรวดเร็ว เมื่อฉันคูณจุดด้วยจำนวนที่มาก ฉันจะบวกเพิ่มเป็นสองเท่า เพิ่มสามเท่า ฯลฯ และฉันสงสัยว่าการเลือก z ที่แตกต่างกันจะมีผลกระทบหรือไม่ ฉันไม่แน่ใจว่าคำถามนี้สมเหตุสมผลหรือไม่ ขอบคุณอีกครั้งสำหรับความอดทน
kelalaka avatar
in flag
ในการคูณแบบสเกลาร์ จุดจะถูกบวกครั้งแล้วครั้งเล่า (การบวกสองครั้ง) ไม่มีจุดที่ตายตัว
Score:2
ธง in

จุดสองเท่า (ลิงก์ Wiki) ต้องการ Z^4 และเมื่อใช้กับอัลกอริทึม double-and-add (จำเป็นสำหรับการคำนวณจุดสาธารณะ, ECDH และลายเซ็นตาม EC) โดยใช้ $Z=1$ ทำให้การคำนวณง่ายขึ้น Z^4 มิฉะนั้นอาจต้องเพิ่มเป็น 3 เท่า วิธี double-and-add โดยที่ ความละเอียด ไม่ได้รับการแก้ไขเพื่อประหยัดเวลา วิกิพีเดียแบบดับเบิลและเพิ่ม รุ่น;

ให้ bits = bit_representation(s) # เวกเตอร์ของบิต (จาก MSB ถึง LSB) แทน s
ให้ res = O # ชี้ที่ระยะอนันต์
สำหรับบิตในบิต:
    res = res + res # สองเท่า
    ถ้าบิต == 1:            
        res = res + P # เพิ่ม
    ผม = ผม - 1
คืนความละเอียด

นี่คือจุดเริ่มต้นของเรื่องยาว เดอะ "m-fold สองเท่า" (ทำซ้ำสองเท่า) คำนวณ $[2^m]P$ และคำนวณเท่านั้น Z^4 ครั้งหนึ่ง. เมื่อคุณต้องการ $[k]P$คุณอาจต้องเป็นตัวแทน $k$ ในรูปแบบไบนารี จากนั้นใช้ m-fold สองเท่าเมื่อจำเป็น เพื่อให้ได้ประโยชน์จากสิ่งนี้ เราต้องคำนวณต้นทุนก่อนที่จะตัดสินใจใช้ m-fold double หรือไม่

คำตอบนั้นไม่ง่ายและสมบูรณ์เนื่องจาก อันนี้ ต้องใช้ Z1=Z2 กับ 5M+2S สำหรับรุ่น Wiki เพิ่มเติมมี 12M+4S ค่าใช้จ่าย. เดอะ 5M+2S ยังคงมี Z1 การคูณและถ้า Z1=1 ที่มีต้นทุนเป็นศูนย์

ในประโยคสั้น ๆ โดยทั่วไป Z1=1 ลดความซับซ้อนของสมการ

เนื่องจาก $(X_1:Y_1:Z_1)$ แสดงถึง $(Z/Z^2,Y/Z^3)$ และ $(X_1:Y_1:Z_1)$ เป็นความสัมพันธ์สมมูลนั่นคือ $$(X_1:Y_1:Z_1) \sim (\lambda X_1:\lambda Y_1:\lambda Z_1)$$ เราสามารถแปลงไฟล์ $Z_1 = 1$ กับ $$(X_1/Z_1:Y_1/Z_1:1)$$

โปรดจำไว้ว่า 1/Z1 ไม่ใช่การหาร แต่เป็นการผกผันของ Z1 บนฟิลด์ที่กำหนด

เดอะ Z1 ในทางกลับกันไม่ได้อยู่ที่นั่นด้วย Z1=1 ภายใต้การดำเนินงาน. เพื่อให้ได้ประโยชน์จากสิ่งนี้ เราต้องหาค่าผกผันและดำเนินการคูณสอง ในทางกลับกัน การหาค่าผกผันเป็นสิ่งที่เราไม่ต้องการเพราะมันมีราคาแพง

อย่างน้อยก็มีประโยชน์ที่จุดเริ่มต้นของการคูณสเกลาร์

T. Rossi avatar
om flag
ขอบคุณมาก!!
kelalaka avatar
in flag
ห่างไกลจากคำตอบที่สมบูรณ์แบบแม้ว่า ....

โพสต์คำตอบ

คนส่วนใหญ่ไม่เข้าใจว่าการถามคำถามมากมายจะปลดล็อกการเรียนรู้และปรับปรุงความสัมพันธ์ระหว่างบุคคล ตัวอย่างเช่น ในการศึกษาของ Alison แม้ว่าผู้คนจะจำได้อย่างแม่นยำว่ามีคำถามกี่ข้อที่ถูกถามในการสนทนา แต่พวกเขาไม่เข้าใจความเชื่อมโยงระหว่างคำถามและความชอบ จากการศึกษาทั้ง 4 เรื่องที่ผู้เข้าร่วมมีส่วนร่วมในการสนทนาด้วยตนเองหรืออ่านบันทึกการสนทนาของผู้อื่น ผู้คนมักไม่ตระหนักว่าการถามคำถามจะมีอิทธิพลหรือมีอิทธิพลต่อระดับมิตรภาพระหว่างผู้สนทนา