Score:1

การจับคู่สำหรับผู้เริ่มต้น: PohligâHellman ความซับซ้อนของเวลาโจมตี

ธง fr

ฉันอ่าน การจับคู่สำหรับผู้เริ่มต้น โดยเครก คอสเตลโล

ฉันกำลังพยายามทำความเข้าใจตัวอย่างของ (สิ่งที่ฉันคิด) คืออัลกอริทึมของ PohligâHellman (ในหน้า 31 ของหนังสือ)

พิจารณา $E/\mathbb{F}_{1021}\,:\,y^2=x^3+905x+100$ ด้วยการสั่งซื้อแบบกลุ่ม $\#E(\mathbb{F}_q)=966=2\cdot3\cdot7\cdot23$ และเครื่องกำเนิดไฟฟ้า $P = (1006,416)$. เราได้รับ $Q = (612,827)$ และเราพยายามค้นหา $k$ ดังนั้น $[k]P = Q$. มากกว่าที่จะแสวงหา $i$ ในกลุ่มเต็ม $(2 \leq ฉัน \leq 965)$เราสามารถแมปอินสแตนซ์ลงในแต่ละกลุ่มย่อยลำดับสำคัญได้โดยการคูณด้วยปัจจัยร่วมที่เหมาะสม แล้วแก้หา $k_j = k\, \text{mod}\,j, j \in \{2,3,7,23\}$. สำหรับ $เจ = 2$, เรามี $P_j = P_2 = [966/2]P = [483](1006,416) = (174, 0)$ และ $Q_j = Q_2 = [483](612,827) = (174, 0)$ ดังนั้น $Q_2 = [k_2]P_2$ ให้ $k_2 = 1$.

จากนั้นเขาก็ให้ค่าสำหรับ $k_2$, $k_3$ฯลฯ

สำหรับ $k_{23}$, เขาพูดว่า

สำหรับ $Q_{23} = [k_{23}]P_{23}$ เราหมดแรง $k_{23} \ใน \{1, ..., 22\}$ เพื่อดูว่า $k_{23} = 20$.

ฉันไม่แน่ใจว่านี่เป็นเพียงการพิมพ์ผิด หรือฉันเข้าใจอะไรพื้นฐานที่มากกว่านั้นผิด ถ้า $k_{23} = 20$ จากนั้นเขาก็ไม่เหนื่อย $\{1, ..., 22\}$เขาหมดแรง $\{1, ....,20\}$. เขาทำซ้ำสิ่งเดียวกันนี้ที่อื่น ดังนั้นฉันจึงคิดว่ามันไม่ใช่การพิมพ์ผิด และฉันรู้สึกสับสนเล็กน้อย

ใครมีคำอธิบาย?

Score:1
ธง gb

ฉันไม่แน่ใจว่านี่เป็นเพียงการพิมพ์ผิด หรือฉันเข้าใจอะไรพื้นฐานที่มากกว่านั้นผิด ถ้า $k_{23} = 20$ จากนั้นเขาก็ไม่เหนื่อย $\{1, ..., 22\}$เขาหมดแรง $\{1, ....,20\}$. เขาทำซ้ำสิ่งเดียวกันนี้ที่อื่น ดังนั้นฉันจึงคิดว่ามันไม่ใช่การพิมพ์ผิด และฉันรู้สึกสับสนเล็กน้อย

สิ่งที่เขาหมายถึงคือการพยายามทุกองค์ประกอบในชุด $\{1, ..., 22\}$ รับประกันอย่างละเอียดถี่ถ้วนเพื่อค้นหา $k_{23}$. มันเกิดขึ้นที่เขาพบมันหลังจากอายุ 20 และไม่ต้องทดสอบ 21 หรือ 22 (สมมติว่าเขาเริ่มทดสอบตั้งแต่ 1) ในจักรวาลอื่นเขาสามารถค้นพบได้ $k_{23} = 5$ และหยุดอยู่แค่นั้น แต่ไม่คำนึงถึงมูลค่าที่แท้จริง เข้าใกล้ ก็ยังหมดชุดอยู่ดี $\{1, ..., 22\}$.

โพสต์คำตอบ

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