การแทนที่แบบโครเนกเกอร์เป็นเทคนิคที่ตั้งชื่อตามเลโอโปลด์ โครเนกเกอร์สำหรับการหาค่าสัมประสิทธิ์ของพหุนาม ที่ไม่ทราบค่า โดยการประเมินค่าที่ค่าเดียว ถ้าp ( x ) เป็นพหุนามที่มีสัมประสิทธิ์เป็นจำนวนเต็ม และเลือกx ให้เป็น กำลังของสองและมีขนาดใหญ่กว่าสัมประสิทธิ์ใดๆ ของp แล้ว ค่าสัมประสิทธิ์ของแต่ละพจน์ของ p ( x ) สามารถอ่านได้โดยตรงจากเลขฐานสองของp (x )

การประยุกต์ใช้วิธีนี้อย่างหนึ่งคือการลดปัญหาการคำนวณของการคูณพหุนามให้เหลือเพียงปัญหาการคูณจำนวนเต็ม (ซึ่งอาจง่ายกว่า) หากp ( x ) และq ( x ) เป็นพหุนามที่มีสัมประสิทธิ์ที่ทราบแล้ว เราสามารถใช้สัมประสิทธิ์เหล่านี้เพื่อกำหนดค่าของxที่เป็นกำลังสองที่มากพอที่จะทำให้สามารถอ่าน ค่าสัมประสิทธิ์ของผลคูณ pq ( x ) ได้จากการแสดงเลขฐานสองของจำนวน p ( x ) q ( x ) เนื่องจากp ( x ) และq ( x ) นั้นสามารถหาได้ง่ายจากสัมประสิทธิ์ของpและqผลลัพธ์นี้แสดงให้เห็นว่าการคูณพหุนามสามารถทำได้ในเวลาเท่ากับการคูณเลขฐานสองเพียงครั้งเดียว^{[ 1 ]}

ให้nเป็นค่าสูงสุดของดีกรีของpและqขอบเขตที่เพียงพอสามารถหาได้จากข้อเท็จจริงที่ว่าสัมประสิทธิ์ทุกตัวในผลคูณเป็นผลรวมของผลคูณของคู่สัมประสิทธิ์อย่างมากที่สุดnครั้ง โดยที่ตัวแรกในคู่มาจากpและตัวที่สองมาจากqให้aและbเป็นสัมประสิทธิ์ที่ใหญ่ที่สุด (ในแง่ขนาด) ของpและqตามลำดับ ดังนั้นสัมประสิทธิ์ทั้งหมดของpqจะต้องไม่มากกว่าnabดังนั้นโดยการบวกจำนวนบิตของn , aและbเราจะได้กำลังที่เหมาะสม

• ผลิตภัณฑ์โครเนกเกอร์