รหัสเรขาคณิตเชิงพีชคณิต ซึ่งมักย่อว่า รหัส AG เป็น รหัสเชิงเส้นประเภทหนึ่งที่ขยายความรหัส Reed–Solomonนักคณิตศาสตร์ชาวรัสเซียVD Goppaสร้างรหัสเหล่านี้เป็นครั้งแรกในปี 1982 ^{[ 1 ]}

ชื่อของรหัสเหล่านี้มีการเปลี่ยนแปลงนับตั้งแต่มีการตีพิมพ์บทความของ Goppa ที่อธิบายถึงรหัสเหล่านี้ ในทางประวัติศาสตร์ รหัสเหล่านี้ยังถูกเรียกว่ารหัสเรขาคณิตของ Goppa ด้วย^{[ 2 ]}อย่างไรก็ตาม นี่ไม่ใช่คำศัพท์มาตรฐานที่ใช้ใน วรรณกรรม ทฤษฎีการเข้ารหัส อีกต่อไป เนื่องจากรหัส Goppaเป็นรหัสประเภทหนึ่งที่แตกต่างออกไป ซึ่ง Goppa สร้างขึ้นในช่วงต้นทศวรรษ 1970 ^{[ 3 ] [ 4 ] [ 5 ]}

รหัสเหล่านี้ดึงดูดความสนใจในชุมชนทฤษฎีการเข้ารหัสเนื่องจากมีความสามารถในการเอาชนะขอบเขตของ Gilbert–Varshamovได้ ในขณะที่ค้นพบสิ่งนี้ ขอบเขตของ Gilbert–Varshamov ยังไม่ถูกทำลายในช่วง 30 ปีนับตั้งแต่การค้นพบ^{[ 6 ]}สิ่งนี้ได้รับการพิสูจน์โดย Tfasman, Vladut และ Zink ในปีเดียวกันกับที่ตีพิมพ์การสร้างรหัส ในบทความของพวกเขาเรื่อง " เส้นโค้งโมดูลาร์เส้นโค้งชิมูระ และรหัสกอปปา ดีกว่าขอบเขตของ Varshamov-Gilbert" ^{[ 7 ]}ชื่อของบทความนี้อาจเป็นแหล่งที่มาของความสับสนที่ส่งผลต่อการอ้างอิงถึงรหัสเรขาคณิตเชิงพีชคณิตในวรรณกรรมทฤษฎีการเข้ารหัสในช่วงทศวรรษ 1980 และ 1990

ในส่วนนี้จะอธิบายถึงการสร้างรหัสเรขาคณิตเชิงพีชคณิต โดยเริ่มต้นด้วยแนวคิดเบื้องหลังรหัสรีด-โซโลมอน ซึ่งใช้เป็นแรงบันดาลใจในการสร้างรหัสเรขาคณิตเชิงพีชคณิต

รหัสเรขาคณิตเชิงพีชคณิตเป็นการวางนัยทั่วไปของรหัส Reed–Solomon รหัส Reed–Solomon ซึ่งสร้างขึ้นโดยIrving ReedและGustave Solomonในปี 1960 ใช้ พหุนามเอก ตัวแปรเพื่อสร้างคำรหัส โดยการประเมินพหุนามที่มีดีกรีเล็กพอสมควร ณ จุดต่างๆ ในฟิลด์จำกัด^{[ 8 ]}${\displaystyle \mathbb {F} _{q}}$

ตามหลักการแล้ว รหัสรีด-โซโลมอนถูกนิยามในลักษณะต่อไปนี้ ให้กำหนดให้ เป็นจำนวนเต็มบวก ให้รหัสรีด-โซโลมอนคือรหัสประเมินผล${\displaystyle \mathbb {F} _{q}=\{\alpha _{1},\dots ,\alpha _{q}\}}$${\displaystyle k\leq n\leq q}$$${\displaystyle \mathbb {F} _{q}[x]_{<k}:=\left\{f\in \mathbb {F} _{q}[x]:\deg f<k\right\}}$$${\displaystyle RS(q,n,k)}$$${\displaystyle RS(q,n,k)=\left\{\left(f(\alpha _{1}),f(\alpha _{2}),\dots ,f(\alpha _{n})\right):f\in \mathbb {F} _{q}[x]_{<k}\right\}\subseteq \mathbb {F} _{q}^{n}.}$$

กอปปาตั้งข้อสังเกตว่าสามารถพิจารณาได้ว่าเป็นเส้นตรงเชิงเส้นตรง โดยมีเส้นตรงเชิงฉาย ที่สอดคล้องกัน จากนั้นพหุนามใน(กล่าวคือพหุนามที่มีดีกรีน้อยกว่าเหนือ) สามารถคิดได้ว่าเป็นพหุนามที่มี การ ^{อนุญาต} ให้มี ขั้วไม่เกินที่จุดอนันต์ใน^[ 6 ^]${\displaystyle \mathbb {F} _{q}}$${\displaystyle \mathbb {P} _{\mathbb {F} _{q}}^{1}}$${\displaystyle \mathbb {F} _{q}[x]_{<k}}$${\displaystyle k}$${\displaystyle \mathbb {F} _{q}}$${\displaystyle k}$${\displaystyle \mathbb {P} _{\mathbb {F} _{q}}^{1}}$

ด้วยแนวคิดนี้ Goppa จึงหันไปพิจารณาทฤษฎีบท Riemann–Rochองค์ประกอบของปริภูมิ Riemann–Roch คือฟังก์ชันที่มีลำดับขั้วจำกัดต่ำกว่าเกณฑ์ที่กำหนด^{[ 9 ]}โดยข้อจำกัดนั้นจะถูกเข้ารหัสไว้ในสัมประสิทธิ์ของตัวหาร ที่สอดคล้องกัน การประเมินฟังก์ชันเหล่านั้นที่จุดตรรกยะบนเส้นโค้งพีชคณิตเหนือ(นั่นคือ จุดในบนเส้นโค้ง) จะให้รหัสในความหมายเดียวกับการสร้าง Reed-Solomon ${\displaystyle X}$${\displaystyle \mathbb {F} _{q}}$${\displaystyle \mathbb {F} _{q}^{2}}$${\displaystyle X}$

อย่างไรก็ตาม เนื่องจากพารามิเตอร์ของรหัสเรขาคณิตเชิงพีชคณิตเชื่อมโยงกับฟิลด์ฟังก์ชันเชิงพีชคณิตคำจำกัดความของรหัสจึงมักกำหนดในภาษาของฟิลด์ฟังก์ชันเชิงพีชคณิตเหนือฟิลด์จำกัด^{[ 10 ]}ถึงกระนั้น สิ่งสำคัญคือต้องจำความเชื่อมโยงกับเส้นโค้งเชิงพีชคณิต เนื่องจากสิ่งนี้ให้วิธีการคิดเชิงเรขาคณิตที่เข้าใจง่ายกว่าเกี่ยวกับรหัส AG ในฐานะส่วนขยายของรหัส Reed-Solomon ^{[ 9 ]}

ตามหลักการแล้ว รหัสเรขาคณิตเชิงพีชคณิตถูกกำหนดในลักษณะต่อไปนี้^{[ 10 ]}ให้เป็นฟิลด์ฟังก์ชันเชิงพีชคณิตให้ เป็นผลรวมของตำแหน่งที่แตกต่างกันของที่มีดีกรีหนึ่ง และเป็นตัวหารที่มีส่วนรองรับ ที่ไม่ทับซ้อนกัน จากรหัสเรขาคณิตเชิงพีชคณิตที่เกี่ยวข้องกับตัวหารและถูกกำหนดเป็นข้อมูลเพิ่มเติมเกี่ยวกับรหัสเหล่านี้สามารถพบได้ทั้งในตำราเบื้องต้น^{[ 6 ]}และตำราขั้นสูงเกี่ยวกับทฤษฎีการเข้ารหัส^{[ 10 ] [ 11 ]}${\displaystyle F/\mathbb {F} _{q}}$${\displaystyle D=P_{1}+\dots +P_{n}}$${\displaystyle n}$${\displaystyle F/\mathbb {F} _{q}}$${\displaystyle G}$${\displaystyle D}$${\displaystyle C_{\mathcal {L}}(D,G)}$${\displaystyle D}$${\displaystyle G}$$${\displaystyle C_{\mathcal {L}}(D,G):=\lbrace (f(P_{1}),\dots ,f(P_{n})):f\in {\mathcal {L}}(G)\rbrace \subseteq \mathbb {F} _{q}^{n}.}$$

รหัสเรขาคณิตเชิงพีชคณิตบางรหัสสามารถถอดรหัสได้โดยใช้อัลกอริทึมที่อิงตามอัลกอริทึม Berlekamp–Massey–Sakata Shojiro Sakata ได้แนะนำอัลกอริทึมนี้ในฐานะส่วนขยายของอัลกอริทึม Berlekamp–Masseyสำหรับอาร์เรย์หลายมิติ^{[ 12 ]}โดยเฉพาะอย่างยิ่ง รหัสเรขาคณิตเชิงพีชคณิตแบบจุดเดียวสามารถถอดรหัสได้อย่างมีประสิทธิภาพโดยใช้อัลกอริทึม Berlekamp–Massey–Sakata และต่อมาได้มีการพัฒนาตัวแปรต่างๆ สำหรับรหัสหลายจุดจากเส้นโค้งเชิงพีชคณิต^{[ 13 ]}

จะเห็นได้ว่า

${\displaystyle RS(q,n,k)={\mathcal {C}}_{\mathcal {L}}(D,(k-1)P_{\infty })}$

โดยที่คือจุดที่อนันต์บนเส้นโปรเจกทีฟและคือผลรวมของจุดตรรกยะ อื่นๆ${\displaystyle P_{\infty }}$${\displaystyle \mathbb {P} _{\mathbb {F} _{q}}^{1}}$${\displaystyle D=P_{1}+\dots +P_{q}}$${\displaystyle \mathbb {F} _{q}}$

เส้นโค้งเฮอร์มิเชียนกำหนดโดยสมการที่พิจารณาเหนือฟิลด์^{[ 2 ]}เส้นโค้งนี้มีความสำคัญเป็นพิเศษเพราะตรงตามขอบเขต Hasse–Weil ด้วยความเท่าเทียมกัน และด้วยเหตุ นี้จึงมีจำนวนจุดแอฟฟินสูงสุดเหนือ[ ^{14 ] ใน}ส่วนที่เกี่ยวกับรหัสเรขาคณิตเชิงพีชคณิต นี่หมายความว่ารหัสเฮอร์มิเชียนมีความยาวเมื่อเทียบกับตัวอักษรที่กำหนดไว้^{[ 15 ]}$${\displaystyle x^{q+1}=y^{q}+y}$$${\displaystyle \mathbb {F} _{q^{2}}}$${\displaystyle \mathbb {F} _{q^{2}}}$

ปริภูมิ Riemann–Roch ของฟิลด์ฟังก์ชัน Hermitian จะแสดงอยู่ในข้อความต่อไปนี้^{[ 2 ]}สำหรับฟิลด์ฟังก์ชัน Hermitianที่กำหนดโดยและสำหรับปริภูมิ Riemann–Roch คือโดยที่คือจุดที่อนันต์บน ${\displaystyle \mathbb {F} _{q^{2}}(x,y)}$${\displaystyle x^{q+1}=y^{q}+y}$${\displaystyle m\in \mathbb {Z} ^{+}}$${\displaystyle {\mathcal {L}}(mP_{\infty })}$$${\displaystyle {\mathcal {L}}(mP_{\infty })=\left\langle x^{a}y^{b}:0\leq b\leq q-1,aq+b(q+1)\leq m\right\rangle ,}$$${\displaystyle P_{\infty }}$${\displaystyle {\mathcal {H}}_{q}(\mathbb {F} _{q^{2}})}$

ด้วยเหตุนี้ รหัสเฮอร์มิเชียนแบบจุดเดียวจึงสามารถกำหนดได้ในลักษณะต่อไปนี้ ให้เป็นเส้นโค้งเฮอร์มิเชียนที่กำหนดบน ${\displaystyle {\mathcal {H}}_{q}}$${\displaystyle \mathbb {F} _{q^{2}}}$

ให้เป็นจุดอนันต์บนและเป็นตัวหารที่รองรับโดย จุดตรรกยะ ที่แตกต่างกันบนนอกเหนือจาก ${\displaystyle P_{\infty }}$${\displaystyle {\mathcal {H}}_{q}(\mathbb {F} _{q^{2}})}$$${\displaystyle D=P_{1}+\cdots +P_{n}}$$${\displaystyle n:=q^{3}}$${\displaystyle \mathbb {F} _{q^{2}}}$${\displaystyle {\mathcal {H}}_{q}}$${\displaystyle P_{\infty }}$

รหัสเฮอร์มิเชียนแบบจุดเดียวคือ ${\displaystyle C(D,mP_{\infty })}$

${\displaystyle C(D,mP_{\infty }):=\left\lbrace (f(P_{1}),\dots ,f(P_{n})):f\in {\mathcal {L}}(mP_{\infty })\right\rbrace \subseteq \mathbb {F} _{q^{2}}^{n}.}$