ปัญหาเกี่ยวกับการลดระดับความลับของ Shamir ในประตูคูณ

มีการอธิบายกระบวนการลดระดับการแบ่งปันความลับของ Shamir ในประตูคูณ ลิงค์ต่อไปนี้

จากข้อมูลการแบ่งปันความลับที่ทำโดยพหุนามดีกรีหนึ่ง เราต้องสามารถสร้างความลับขึ้นมาใหม่ได้ นั่นคือ $10$,กับแต่ละ $2$ หุ้นออกจาก $3$ หุ้น $(3, 7, 0)$. อย่างไรก็ตามความลับที่สร้างขึ้นใหม่โดยใช้ $(3, 7)$ ถูกต้อง $10$แต่สร้างความลับขึ้นใหม่โดยใช้ $(3,0)$ คือ 9 และใช้ $(7, 0)$ เป็น $1$. ทำไมถึงเป็นเช่นนี้? ผิดพลาดตรงไหน?

ฉันคิดว่าคุณเข้าใจผิดเกี่ยวกับการสร้างส่วนแบ่งใหม่ ส่วนแบ่ง $(ก,ข,ค)$ ในบริบทนี้เป็นสามค่าที่สอดคล้องกับการประเมินพหุนามกล่าวคือ $(\sigma(1), \sigma(2),\sigma(3))$. ปัญหาของการสร้างส่วนแบ่งใหม่คือการใช้

1. สองค่าใด ๆ ข้างต้นของ $\sigma(i)$, และ
2. ความรู้นั้น $\sigma(x) = \sigma(0)+ax$ เป็นพหุนามดีกรีเชิงเส้น

การกู้คืน $\sigma(0)$. สามารถทำได้ง่ายๆ บอกว่าเรามี $\sigma(i) = \sigma(0) + ai$ และ $\sigma(j) = \sigma(0) + aj$. เราสามารถลบสิ่งเหล่านี้และ "แก้" สำหรับ $a$ เพื่อให้ได้สิ่งนั้น $a = (i-j)^{-1}(\sigma(i)-\sigma(j))$, ที่ไหน $a^{-1}$ คือโมดูโลผกผัน 11 จากนั้นใช้ค่านี้ของ $a$มันง่ายที่จะกู้คืน $\sigma(0)$.

โปรดทราบว่าค่าที่คำนวณได้ของ $a$ เหมือนกันทั้ง 3 กรณี เมื่อไร $(i,j) = (1,2)$เรามีสิ่งนั้น

$$a = (1-2)^{-1}(3-7) = 4$$

เมื่อไร $(i,j) = (1,3)$ เรามีสิ่งนั้น

$$a = (1-3)^{-1}(3-0) = (-2)^{-1}3 = (-6)3\equiv -18\bmod 11 \equiv 4\bmod 11 $$

ในทำนองเดียวกัน เมื่อ $(i,j) = (2,3)$เรามีสิ่งนั้น

$$a = (2-3)^{-1}(7-0) = -7\equiv 4\bmod 11.$$

ถัดไป สำหรับดัชนีใดๆ $i$เรามีสิ่งนั้น $\sigma(0) = \sigma(i) - ai\bmod 11 \equiv \sigma(i) - 4i\bmod 11$. ง่ายต่อการตรวจสอบสำหรับคู่ใด ๆ $(i, \sigma(i))$กล่าวคือสำหรับ $(1, 3)$, $(2,7)$, หรือ $(3,0)$หนึ่งได้รับ $10\bสมัย 11$ (หรือ $-1\bสมัย 11$ ---มีค่าเท่ากัน)

จากทั้งหมดที่กล่าวมา ฉันไม่พบคำอธิบายของการลดระดับในคำตอบที่เชื่อมโยงนั้นชัดเจนเป็นการส่วนตัว ฉันได้อธิบายไปก่อนหน้านี้แล้ว ที่นี่. อย่างคร่าว ๆ หนึ่งบรรลุการลดระดับโดยการรวมกัน

1. การดูการแก้ไข / การประเมินส่วนแบ่งเป็น "การเปลี่ยนแปลงพื้นฐาน" และ
2. ลดจากปริญญา $2t$ พหุนามในระดับหนึ่ง $t$ พหุนามผ่านการฉายลงบนตัวแรก $t$ พิกัด (ในเกณฑ์ที่เหมาะสม)

หากคุณคุ้นเคยกับพีชคณิตเชิงเส้นมากขึ้น สิ่งนี้จะให้ภาพ "เรขาคณิต" ที่ชัดเจนของสิ่งที่เกิดขึ้น แน่นอนว่าขึ้นอยู่กับภูมิหลังของคุณ