Berlekamp Massey อาจผิด SAGEMATH

สิ่งนี้อยู่ในบริบทที่มีฟังก์ชัน berlekamp_massey ในตัวใน SAGEMATH

ขณะคำนวณพหุนามขั้นต่ำของลำดับโดยใช้ฟังก์ชัน Berlekamp Massey ฉันรู้สึกว่าฟังก์ชัน Berlekamp Massey ใน Sagemath ได้รับการออกแบบมาเพื่อให้ลำดับธาตุซ้ำสองครั้งเพื่อให้ได้ผลลัพธ์ที่ถูกต้อง พิจารณาปัญหาการคำนวณความซับซ้อนเชิงเส้นของสตริงคาบ $$s = 110010100001110$$

ฟังก์ชัน Berlekamp Massey พร้อมอินพุตที่ต่อกัน $$อินพุต = s+s$$ ให้ผลลัพธ์ที่ถูกต้อง

รหัส: berlekamp_massey([GF(2)(1), 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0 , 1, 0, 0, 0, 0, 1, 1, 1, 0])

เหตุใดจึงต้องเพิ่มลำดับเป็นสองเท่าสำหรับการคำนวณพหุนามขั้นต่ำที่ถูกต้องใน SAGEMATH อัลกอริทึมดั้งเดิมไม่ได้พูดอะไรแบบนี้ สิ่งนี้เกี่ยวข้องกับสาเหตุที่ฟังก์ชันนี้ยอมรับอินพุตที่มีความยาวเท่ากัน นี่เป็นวิธีที่กำหนดโมดูลใน sagemath หรือไม่

หมายเหตุ: บางครั้งสำหรับลำดับ s = $(s_0, s_1,......, s_{N-1})$พหุนามขั้นต่ำสำหรับกรณีที่พิจารณาลำดับ $s$ และลำดับ $s+s$ แตกต่างกันและในบางกรณีก็เหมือนกัน ดังนั้น ในกรณีที่มันแตกต่างกัน เราควรใช้พหุนามขั้นต่ำสำหรับลำดับซ้ำสองเท่า เพราะมันเห็นด้วยกับการพิจารณาเมทริกซ์ของ Hankel หรือไม่

หมายเหตุ: ฉันได้ทำตัวอย่างมากมายในช่วงสองสามวันที่ผ่านมา และจากนั้นฉันก็นำเสนอข้อโต้แย้งนี้ ขอบคุณสำหรับความช่วยเหลือ

BMA เป็นอัลกอริทึมแบบเรียกซ้ำ เอาต์พุตถูกต้องสำหรับอินพุตที่คุณนำเสนอ

ผลลัพธ์ของมันคือพหุนามลักษณะเฉพาะที่สามารถสร้างได้ $$(s_1,\ldots,s_N)\quad(1)$$ แต่อย่างที่ฉันอธิบายไว้ในคำตอบสำหรับคำถามที่เกี่ยวข้องของคุณ ที่นี่ ด้วยสูตร Hankel โดยทั่วไป การเกิดซ้ำอาจเปลี่ยนแปลงเมื่อคุณพิจารณาส่วนที่ยาวขึ้น

$$(s_1,\ldots,s_{N+i})$$

ของลำดับและไม่อาจปักหลักเป็นพหุนามลักษณะสุดท้ายได้จนกว่าคุณจะ พิจารณา $$(s_1,\ldots,s_{2N}).$$

ตัวเลือกของคุณในการทำซ้ำส่วนเริ่มต้นเป็นเพียงเท่านั้น หนึ่งที่เป็นไปได้ ส่วนขยายดังกล่าว และตามคำจำกัดความ ผลลัพธ์ของ BMA หลังจากส่วนขยายนี้ใช้ได้กับส่วนขยายแรกด้วย $N$ บิตของลำดับใน (1)