การแบ่งพหุนามในการพิสูจน์ขอบเขตล่างบนบันทึกแบบไม่ต่อเนื่องในกลุ่มทั่วไป

ในการพิสูจน์ของ Shoup เกี่ยวกับความแข็งของบันทึกที่ไม่ต่อเนื่องในกลุ่มทั่วไปใน กระดาษแผ่นนี้เขากล่าวถึงว่า:

ในทุกขั้นตอนของเกม อัลกอริทึมได้คำนวณรายการ $F_1,\จุด,F_k$ ของพหุนามเชิงเส้นใน $Z/p^t[X]$ พร้อมด้วยรายการค่า $z_1,\จุด,z_k$ ใน $Z/วินาที$และรายการ $\sigma_1,\จุด,\sigma_k$ ของ แตกต่าง ค่าใน $S$.

อัลกอริทึมจะได้รับการเข้ารหัสในขั้นต้น $1,x$ และการเข้าถึงการดำเนินการกลุ่ม + ผกผัน ดังนั้นจึงชัดเจนว่าอะไรก็ตามที่อัลกอริทึมคำนวณสามารถแสดงเป็นพหุนามเชิงเส้นใน $Z/n[X]$, ที่ไหน $n=p^t ส$. อย่างไรก็ตาม ฉันไม่เห็นว่าสิ่งนี้แบ่งออกเป็นพหุนามเชิงเส้นได้อย่างไรใน $Z/p^t[X]$ และคงที่ใน $Z/วินาที$.