Score:1

$F_{p^k}$ และเส้นโค้งวงรีเหนือ $E(F_{p^k})$ คืออะไร

ธง cn

ในการเข้ารหัสตามการจับคู่ จะมีฟิลด์จำกัด $F_{p^k}$ ที่ไหน $p$ เป็นจำนวนเฉพาะและ $k$ เป็นจำนวนเต็ม เส้นโค้งวงรีถูกสร้างขึ้นบนสนามที่มีขอบเขตเป็น $E(F_{p^k})$.

ตัวอย่างเช่นให้ $E$ เป็นเส้นโค้งวงรี $Y^2 = X^3 + aX + b $ เกิน $F_{q^k}$. ความหมายของอะไร $F_{q^k}$ ที่นี่? ฉันเข้าใจเฉพาะฟิลด์สำคัญ ($F_q$ โดยที่ q เป็นจำนวนเฉพาะ)

kelalaka avatar
in flag
มีการแนะนำในวิกิพีเดียเกี่ยวกับ [เขตข้อมูลจำกัด](https://en.wikipedia.org/wiki/Finite_field) และนี่เป็นเรื่องที่กว้าง ( มีคำถาม 4K อยู่แล้วใน [math.se](https:// math.stackexchange.com/questions/tagged/finite-fields) เกี่ยวกับเรื่องนี้ หากคุณต้องการเรียนรู้เกี่ยวกับ Finite Field เพิ่มเติม คุณควรเรียนหลักสูตรหรืออ่านหนังสือเกี่ยวกับเรื่องนี้
Score:3
ธง cn

คุณสามารถพิจารณาได้ $F_q[X]/(P(X))$ กับ $พี$ หนึ่ง พหุนามลดไม่ได้ ของปริญญา $k$ ใน $F_q[X]$.

หมายความว่าองค์ประกอบของฟิลด์ที่สามารถมองเห็นได้คือพหุนาม และเมื่อคุณทำการบวกหรือคูณ คุณกำลังคำนวณมันเป็นโมดูโล $พี$.

ตัวอย่างของเล่น: สมมติว่า $q=2=k$. เราสามารถใช้เวลา $P=X^2 + X + 1$ ซึ่งลดไม่ได้ใน $\mathbb{Z}_2$.

องค์ประกอบทั้งหมดอยู่ในรูปแบบ: $\alpha_0 + \alpha_1 X$.

อนุญาต $\alpha_0 + \alpha_1 X, \beta_0 + \beta_1 X$ สององค์ประกอบของสนาม $\alpha_0 + \alpha_1 X + \beta_0 + \beta_1 X= (\alpha_0 + \beta_0) + (\alpha_1 + \beta_1) X$

$(\alpha_0 + \alpha_1 X) \cdot (\beta_0 + \beta_1 X)= (\alpha_0\beta_0) + (\alpha_1\beta_0 + \alpha_0\beta_1) X + \alpha_1\beta_1X^2$. และเพราะว่า $X^2 = X +1 $, ก็เท่ากับ $(\alpha_0 + \alpha_1 X) \cdot (\beta_0 + \beta_1 X)= (\alpha_0\beta_0+ \alpha_1\beta_1) + (\alpha_1\beta_0 + \alpha_0\beta_1 + \alpha_1\beta_1) X$.

เพื่อคำนวณการกลับด้านของ $(\alpha_0 + \alpha_1 X)$เราต้องแก้ระบบ: $(\alpha_0x_0+ \alpha_1x_1)=1$ และ $ (\alpha_1x_0 + (\alpha_0+ \alpha_1)x_1)=0$.

xiaojiuwo avatar
cn flag
ขอบคุณ คุณช่วยยกตัวอย่างที่อธิบาย $F_{q}[X]$ ง่ายๆ ได้ไหม
Ievgeni avatar
cn flag
@xiaojiuwo ชัดเจนกว่านี้ไหม?
Score:1
ธง ng

เขตข้อมูล จำกัด $(\mathbb F,+,\cdot)$ เป็นเซตจำกัด $\mathbb F$ ด้วยกฎหมายภายในสองฉบับ $+$ และ $\cdot$, ดังนั้น $(\mathbb F,+)$ เป็นการแลกเปลี่ยน กลุ่ม โดยระบุเป็นกลาง $0$, และ $(\mathbb F-\{0\},\cdot)$ เป็นกลุ่มสับเปลี่ยนที่มีค่าเป็นกลาง $1$และการคูณคือการแจกแจง w.r.t. นอกจากนี้นั่นคือ $\forall A,B,C\in\mathbb F$ มันถือ $A\cdot(B+C)=(A\cdot B)+(A\cdot C)$.

แสดงให้เห็นว่ามีขอบเขตจำกัดทั้งหมดที่มีจำนวนองค์ประกอบเท่ากัน ไอโซมอร์ฟิคนั่นคือเราสามารถแมปจากที่หนึ่งไปยังอีกที่หนึ่งโดย คัดค้าน $\คณิตศาสตร์ F$ ดังนั้น $\mathcal F(A+B)=\mathcal F(A)+\mathcal F(B)$ และ $\mathcal F(A\cdot B)=\mathcal F(A)\cdot \mathcal F(B)$. เราจึงสามารถพูดถึง เดอะ เขตข้อมูล จำกัด $\mathbb F$ กับ $คิว$ องค์ประกอบ ก็มักจะสังเกตเห็น $\mathbb F_q$.

แสดงว่าเขตข้อมูลจำกัดใด ๆ มีจำนวน $คิว$ องค์ประกอบของแบบฟอร์ม $q=p^k$ สำหรับนายกรัฐมนตรีบางคน $p$ และบางส่วน $k\in\mathbb N^*$.

เมื่อไร $k=1$, สนาม $(\mathbb F_p,+,\cdot)$ เป็นเพียงวงแหวนของโมดูโลจำนวนเต็ม $p$, นั่นคือ $(\mathbb Z_p,+,\cdot)$.

สำหรับพล $k\in\mathbb N^*$เราสามารถคิดถึงสนาม $(\mathbb F_{p^k},+,\cdot)$ เป็นเซตของพหุนามดีกรีขึ้นไป $k-1$ และค่าสัมประสิทธิ์ใน $\mathbb Z_p$. นั่นคือพหุนามสำหรับตัวแปรนามธรรม $x$ ด้วยหนึ่งสัมประสิทธิ์ใน $\mathbb Z_p$ สำหรับแต่ละ $k$ ข้อกำหนด $x^i$ กับ $i\in\{0,1\ldots,k-1\}$. นอกจากนี้ใน $\mathbb F_{p^k}$ เป็นการบวกพหุนาม คูณใน $\mathbb F_{p^k}$ คือการคูณพหุนามตามด้วยโมดูโลการลดลง พหุนามการลดลงโดยเฉพาะ $R(x)$ ของปริญญาเป๊ะๆ $k$, และ ลดไม่ได้.

เท่าที่เราคิดได้ $\mathbb F_{p^k}$ เป็นชุดของ $p^k$ สิ่งอันดับของ $k$ องค์ประกอบของ $\mathbb Z_p$, ข้อสังเกต $(a_0,a_1\ldots,a_{k-1})$. นอกจากนี้ถูกกำหนดโดย$$(a_0,a_1\ldots,a_{k-1})+(b_0,b_1\ldots,b_{k-1})=(a_0+b_0,a_1+b_1\ldots,a_{k-1}+ ข_{k-1})$$โดยเพิ่มเติมเข้ามาในภายหลัง $\mathbb Z_p$นั่นคือด้วยโมดูโลการลดลง $p$. ถ้าทูเพิล $เอ$ มี $a_i=1$ และเงื่อนไขอื่นๆ ทั้งหมด $0$และทูเพิล $B$ มี $b_j=1$ และเงื่อนไขอื่นๆ ทั้งหมด $0$, แล้วเมื่อไหร่ $i+j<k$ ทูเพิล $C$ สำหรับ $A\cdot B$ มี $c_{i+j}=1$ และเงื่อนไขอื่นๆ ทั้งหมด $0$. เมื่อไร $i+j=k$ทูเพิล $C$ สำหรับ $A\cdot B$ เป็นทูเพิลคงที่ $(r_0,r_1,\ldots,r_{k-1})$ เป็นอิสระจาก $i$ และ $j=k-i$. ทูเพิลนั้นเป็นพหุนาม $R(x)=x^k-r_{k-1}\,x^{k-1}\ldots-r_1\,x-r_0$ ด้วยค่าสัมประสิทธิ์ใน $\mathbb Z_p$ เป็น ลดไม่ได้หมายถึง $r_0\ne0$. ทูเพิลคงที่นี้ $(r_0,r_1\ldots,r_{k-1})$หรือเทียบเท่ากับพหุนาม $R(x)$รวมกับกฎและคุณสมบัติของที่ระบุไว้ก่อนหน้านี้ $+$ และ $\cdot$นิยามการคูณอย่างสมบูรณ์ และเป็นกลาง $(1,0\ldots,0)$.

เราสามารถคำนวณทูเพิล $(c_0,c_1\ldots,c_{k-1})$ สำหรับ $(a_0,a_1\ldots,a_{k-1})\cdot(b_0,b_1\ldots,b_{k-1})$ ดังนี้

  • $(c_0,c_1\ldots,c_{k-1}):=(0,0\ldots,0)$

  • สำหรับ $i$ จาก $k-1$ ลงไป $0$

    • $m:=c_{k-1}$
    • สำหรับ $เจ$ จาก $k-1$ ลงไป $1$
      • $c_j:=m\cdot r_j+a_i\cdot b_j+c_{j-1}$
    • $c_0:=m\cdot r_0+a_i\cdot b_0$

    ด้วยการคำนวณในสองบรรทัดสุดท้าย $\mathbb Z_p$นั่นคือโมดูโล $p$.

ve flag
ฉันแค่ต้องการเพิ่มจุดเล็ก ๆ : ในบริบทของการเข้ารหัสตามการจับคู่ $k$ มักจะเป็นระดับการฝัง เช่น. มันคือ $k$ ที่เล็กที่สุด ดังนั้น $n | q^k-1$ โดยที่ $n$ คือจำนวนจุดในกลุ่มเส้นโค้งวงรี สิ่งสำคัญคือต้องเลือกเส้นโค้งที่มีค่า $k$ น้อยๆ มิฉะนั้นการจับคู่จะแพงเกินไปในการคำนวณ

โพสต์คำตอบ

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