ขั้นตอนวิธีเชินฮาเกอ–ชตรัสเซิน

ขั้นตอนวิธีเชินฮาเกอ–ชตรัสเซิน (Schönhage–Strassen algorithm) เป็นขั้นตอนวิธีในการคูณเลขจำนวนเต็มขนาดใหญ่ ขั้นตอนวิธีนี้ได้รับการพัฒนามาจาก อาร์น็อลท์ เชินฮาเกอ และ ฟ็อลเคอร์ ชตรัสเซิน ในปี ค.ศ. 1971 โดยนำความสัมพันธ์เวียนเกิด มาใช้กับการแปลงฟูรีเยแบบเร็ว ในริงที่มีจำนวนสมาชิกเป็น 22"n" + 1 ตัว ซึ่งเป็นสมาชิกพิเศษประเภทหนึ่งของ ทฤษฎีการเปลี่ยนรูปของตัวเลข 
ขั้นตอนวิธีเชินฮาเกอ–ชตรัสเซินเป็นขั้นตอนวิธีการคูณที่เร็วที่สุดเท่าที่เคยค้นพบมาตั้งแต่ปี ค.ศ. 1971 จนถึง ปี ค.ศ. 2007 ก่อนที่จะมีวิธีใหม่เข้ามาแทนที่ซึ่งก็คือ ขั้นตอนวิธีของฟือเรอร์  ที่ได้รับการประกาศไว้ว่าเป็นวิธีที่มีความซับซ้อนเชิงเส้นกำกับ (asymptotic complexity) น้อยกว่า แต่อย่างไรก็ตามในปัจจุบัน ขั้นตอนวิธีของ Fürer ก็สามารถใช้งานได้เฉพาะกับ ค่าที่มีจำนวนมหาศาลเท่านั้น และไม่นิยมใช้กับการใช้งานในชีวิตปกติ
รายละเอียด.
การอธิบายในส่วนนี้ จะกล่าวถึงรายละเอียดของ ขั้นตอนวิธีเชินฮาเกอ–ชตรัสเซินว่ามีวิธีการอย่างไร โดยมีพื้นฐานการทำงานขั้นต้นจาก หนังสือของ แครนเดล และ โพเมอร์แรนซ์ เรื่อง “จำนวนเฉพาะ : ทัศนคติเกี่ยวกับการคำนวณทางคอมพิวเตอร์” รวมไปถึงข้อมูลจากหนังสือ “ศิลปะในการเขียนโปรแกรมคอมพิวเตอร์” โดย โดนัลด์ คนูธ (Donald Knuth)
สังวัตนาการ (Convolutions).
สมมติว่าเราต้องการจะคูณเลขจำนวน 2 ตัว เช่น 123 และ 456 โดยใช้การคูณแบบยาว ที่จำนวนที่นำมาคูณกันนั้นมีฐานเป็น “B” โดยการคูณนี้จะไม่มีการทดเลข ซึ่งผลลัพธ์ที่ได้มีลักษณะดังนี้
ลำดับที่ได้จากการคูณนี้ (4,13,28,27,18) เรียกว่า หรือ ซึ่งเกิดมาจาก ลำดับพื้นฐาน 2 ตัวคือ (1,2,3)และ(4,5,6) เมื่อเรามีลำดับของ acyclic convolution ครบทั้ง 2 ตัวแล้ว การคำนวณก็จะทำได้อย่างง่ายดาย โดยการจัดการกับเลขที่มีตัวทด จากตัวอย่าง หลักขวามือสุด เป็นเลข 18 ให้เก็บหลักขวามือ ซึ่งก็คือเลข 8 เอาไว้ จากนั้น นำเลขหลักซ้ายมือซึ่งก็คือเลข 1 ไปบวกกับ เลขในหลักขวามือของเลขที่อยู่ด้านซ้ายมือถัดไป ในที่นี้คือเลข 7 จาก เลข 27 ที่อยู่ในลำดับ acyclic ทำเช่นนี้ไปเรื่อย ๆ จะได้ผลลัพธ์สุดท้ายออกมาเป็น 5608
นอกจากนี้ยังมี ชนิดอื่น ๆ อีก 2 ชนิดที่อาจจะมีประโยชน์ในการคำนวณ
ชนิดแรก สมมติว่าลำดับของข้อมูลขาเข้ามีจำนวน “n” ตัว (ในที่นี้ลำดับมีจำนวน 3 ตัว) ดังนั้น acyclic convolution จะมีสมาชิกเป็นจำนวน "n"+"n"−1 ตัว ถ้าหากว่าเรานำเลขที่อยู่ขวามือสุด "n" ตัว มาบวกเข้ากับเลขซ้ายมือสุดจำนวน "n"−1 ตัว ผลที่ได้ออกมาจะเป็น :
ถ้าหากเรานำค่าจาก cyclic convolution มาทำการคำนวณแบบการจัดการกับเลขที่มีตัวทด จะได้ผลลัพธ์ที่เกิดจาก การนำเอาคำตอบของการคูณเลข 2 จำนวนในตอนแรกมาทำการมอดดูโลด้วย B"n" − 1 จากตัวอย่างจะได้ 103 − 1 = 999 ดังนั้นจากลำดับ (28,31,31) จะได้ค่าออกมาเป็น 3141 ซึ่ง 3141 ≡ 56088 (mod 999)
ในทางกลับกัน สำหรับชนิดที่สอง เราจะนำเลขที่อยู่ขวามือสุด "n" ตัว มาลบ แทนที่จะบวก กับเลขซ้ายมือสุดจำนวน "n"−1 ตัว ผลที่ได้ออกมาเราจะเรียกว่า :
ถ้าหากเรานำค่าจาก negacyclic convolution มาทำการคำนวณแบบการจัดการกับเลขที่มีตัวทด จะได้ผลลัพธ์ที่เกิดจาก การนำเอาคำตอบของการคูณเลข 2 จำนวนในตอนแรกมาทำการมอดดูโลด้วย B"n" + 1 จากตัวอย่างจะได้ 103 + 1 = 1001 ดังนั้นจากลำดับ (28,23,5) จะได้ค่าออกมาเป็น 3035 ซึ่ง 3035 ≡ 56088 (mod 1001)
ลำดับของ negacyclic convolution สามารถเป็นเลขจำนวนลบได้ เพราะจำนวนลบนี้สามารถกำจัดทิ้งได้ เมื่อทำการบวกหลักตัวทด
ทฤษฎีบทสังวัตนาการ (Convolution theorem).
ทฤษฎีบทสังวัตนาการ  มีลักษณะเหมือนกับวิธีการการคูณทั่ว ๆ ไปที่มีการอ้างอิงถึงทฤษฏีการแปลงฟูรีเยอย่างเร็ว(multiplication methods based on the Fast Fourier transform) ซึ่งขั้นตอนวิธีเชินฮาเกอ–ชตรัสเซิน จะมีหลักการเบื้องต้นที่อ้างอิงถึงทฤษฎีบทสังวัตนาการนี้
ทฤษฎีบทสังวัตนาการ  มีส่วนช่วยอย่างมากในการคำนวณลำดับ cyclic convolution 2 ลำดับใด ๆ โดยมีการกล่าวไว้ว่า :
สำหรับ cyclic convolution ของเวกเตอร์ใด ๆ 2 ตัว เกิดได้จาก การแปลงฟูรีเยไม่ต่อเนื่อง(DFT)โดยผลคูณของสมาชิกในเวกเตอร์เกิดจากการคูณกันตัวต่อตัว จากนั้นจึงทำการ inverse discrete Fourier transform (IDFT) ต่อ
หรือเขียนออกมาในรูปของสัญลักษณ์ได้ดังนี้ :
 CyclicConvolution(X, Y) = IDFT(DFT(X) · DFT(Y))
หากทำการคำนวณเลข DFT และ IDFT โดยการใช้การแปลงฟูรีเยแบบเร็ว ทำให้เกิดขั้นตอนวิธีการคูณที่ใช้ความสัมพันธ์เวียนเกิดในการคูณสมาชิกเวกเตอร์ที่ถูกแปลงแล้ว DFT(X) and DFT(Y) โดยผลลัพธ์ที่ได้ออกมานั้นจะมีประสิทธิภาพในการคำนวณ cyclic convolution เป็นอย่างมาก
สำหรับขั้นตอนวิธีการนี้ มีประโยชน์ในการคำนวณ negacyclic convolution ด้วยเช่นกัน โดยการเปลี่ยนแปลงทฤษฎีบทสังวัตนาการเพียงเล็กน้อย สมมติว่ามีเวกเตอร์ X และ Y มีความยาว "n" และค่า "a" คือค่าฐานที่เป็นเอกภาพของลำดับ 2"n" (ซึ่งก็คือ "a"2"n" = 1 และจำนวน "a" ทุกๆตัวที่มีค่าของเลขชี้กำลังน้อยว่า มีค่าไม่เท่ากับ 1) ดังนั้นเราจะได้เวกเตอร์ตัวที่ใหม่ที่มีชื่อ A เป็นเวกเตอร์ตัวที่ 3 ที่เรียกกันว่า ""
 "A" = ("a""j"), 0 ≤ "j" < "n"
 "A"−1 = ("a"−j"), 0 ≤ "j" < "n"
ซึ่งก็คือ:
NegacyclicConvolution("X", "Y") = "A"−1 · IDFT(DFT("A" · "X") · DFT("A" · "Y"))
 จะเห็นได้ว่าในการคำนวณ negacyclic convolution นี้มีวิธีการเหมือนกันวิธีก่อนหน้านี้ที่ได้กล่าวมา แต่มีความต่างกันตรงที่วิธีก่อนหน้านั้นคูณด้วย "A" แต่วิธีนี้คูณด้วย "A"−1 นั่นเอง
ประสิทธิภาพการทำงาน.
ประสิทธิภาพในการทำงานของขั้นตอนวิธีเชินฮาเกอ–ชตรัสเซิน หากเราพิจารณาจากความซับซ้อนในการกำหนดจำนวนบิต  จะสามารถเขียนในรูปของ สัญกรณ์โอใหญ่ ได้คือ O(N log N log log N) ในขณะที่พิจารณาจากความซับซ้อนทางด้านการคำนวณทางคณิตศาสตร์ หรือที่เรียกว่า  จะได้เป็น O(N log N) 
ตัวอย่างการใช้งาน.
ขั้นตอนวิธีเชินฮาเกอ–ชตรัสเซิน ใช้ในการลดรูปการคูณจำนวนเต็มใด ๆ ที่มีจำนวน S บิต ไปเป็นจำนวนการคูณ L ครั้งโดยประมาณใกล้เคียงได้เป็น 4S/L บิตของจำนวนเต็ม เท่านั้นไม่พอขั้นตอนวิธีนี้ได้นำไปประยุกต์ใช้กับทฤษฎีบทดิจิทัล อิเลคทรอนิกส์ โดยเฉพาะเรื่องเสียงดิจิทัล โดย ทฤษฎี นั้นถือเป็นหัวใจหลักของขั้นตอนวิธีนี้เลยก็ว่าได้ นอกจากนี้ ขั้นตอนวิธีเชินฮาเกอ–ชตรัสเซินยังสามารถนำไปใช้จริงใน GNU Multi-Precision Library หรือที่รู้จักกันในชื่อย่อว่า GMP ซึ่งเป็นซอร์ฟแวร์ทางคณิตศาสตร์ ที่ได้รับการพัฒนาจาก The GNU Project นั่นเอง