อัลกอริทึม Schönhage–Strassen เป็น อัลกอริทึมการคูณที่รวดเร็วในเชิง อะซิมโทติก สำหรับจำนวนเต็มขนาด ใหญ่ ซึ่งเผยแพร่โดยArnold SchönhageและVolker Strassenในปี 1971 ^{[ 1 ]} อัลกอริทึม นี้ทำงานโดยการใช้การแปลงฟูริเยร์แบบเร็ว (FFT) ซ้ำๆ กับจำนวนเต็มโมดูลัส n ความซับซ้อนของบิตรันไทม์ในการคูณ จำนวน nหลักสองจำนวนโดยใช้อัลกอริทึมนี้อยู่ในสัญกรณ์บิ๊ก โอ${\displaystyle 2^{n}+1}$${\displaystyle O(n\cdot \log n\cdot \log \log n)}$

อัลกอริทึม Schönhage–Strassen เป็นวิธีการคูณที่เร็วที่สุดในเชิงอะซิมโทติกที่รู้จักกันตั้งแต่ปี 1971 จนถึงปี 2007 มันเร็วกว่าวิธีการเก่าๆ เช่น การคูณแบบ KaratsubaและToom–Cook ในเชิง อะซิมโท ติก และเริ่มมีประสิทธิภาพเหนือกว่าในทางปฏิบัติสำหรับตัวเลขที่มีจำนวนหลักทศนิยมมากกว่าประมาณ 10,000 ถึง 100,000 หลัก^{[ 2 ]} ในปี 2007 Martin Fürer ได้เผยแพร่ อัลกอริทึมที่มีความซับซ้อนเชิงอะซิมโทติกที่เร็วกว่า^{[ 3 ]}ในปี 2019 David Harvey และJoris van der Hoevenได้แสดงให้เห็นว่าการคูณหลายหลักมีความซับซ้อนเชิงทฤษฎี อย่างไรก็ตาม อัลกอริทึมของพวกเขามีปัจจัยคงที่ซึ่งทำให้มันช้าจนเป็นไปไม่ได้สำหรับปัญหาในทางปฏิบัติใดๆ ที่คิดได้ (ดูอัลกอริทึมกาแล็กติก ) ^{[ 4 ]}${\displaystyle O(n\log n)}$

การประยุกต์ใช้อัลกอริทึม Schönhage–Strassen รวมถึงการคำนวณขนาดใหญ่ที่ทำเพื่อตัวมันเอง เช่นการค้นหาจำนวนเฉพาะเมอร์เซนน์บนอินเทอร์เน็ตครั้งใหญ่และการประมาณค่าπรวมถึงการประยุกต์ใช้ในทางปฏิบัติ เช่นการแยกตัวประกอบเส้นโค้งวงรี Lenstraผ่านการแทนที่ Kroneckerซึ่งลดการคูณพหุนามเป็นการคูณจำนวนเต็ม^{[ 5 ] [ 6 ]}

ส่วนนี้มีอัลกอริทึมเวอร์ชันที่เรียบง่ายกว่า ซึ่งแสดงวิธีการคำนวณผลคูณของจำนวนธรรมชาติสองจำนวนโดยใช้โมดูลัสของจำนวนในรูปแบบโดยที่เป็นจำนวนคงที่บางจำนวน จำนวนเต็มจะต้องถูกแบ่งออกเป็นบล็อกของบิต ดังนั้นในการใช้งานจริง จึงเป็นสิ่งสำคัญที่จะต้องสร้างสมดุลที่เหมาะสมระหว่างพารามิเตอร์ ไม่ว่าในกรณีใด อัลกอริทึมนี้จะช่วยให้สามารถคูณจำนวนเต็มบวกสองจำนวนได้ โดยมีเงื่อนไขว่าจะต้องถูกเลือกให้ เป็นไปตามเงื่อนไข ${\displaystyle ab}$${\displaystyle a,b}$${\displaystyle 2^{n}+1}$${\displaystyle n=2^{k}M}$${\displaystyle a,b}$${\displaystyle D=2^{k}}$${\displaystyle M}$${\displaystyle M,k}$${\displaystyle n}$${\displaystyle ab<2^{n}+1}$

ให้เป็นจำนวนบิตในสัญญาณและโดยที่เป็นกำลังของสอง แบ่งสัญญาณและออกเป็นบล็อก บล็อกละ บิต แล้วจัดเก็บบล็อกที่ได้เป็นอาร์เรย์(ซึ่งเพื่อความง่าย เราจะถือว่าค่าในอาร์เรย์เป็นจำนวนเต็มที่มีความแม่นยำสูง) ${\displaystyle n=DM}$${\displaystyle a}$${\displaystyle b}$${\displaystyle D=2^{k}}$${\displaystyle a}$${\displaystyle b}$${\displaystyle D}$${\displaystyle M}$${\displaystyle A,B}$

ต่อไปนี้เราจะเลือกค่าสัมบูรณ์สำหรับการแปลงฟูริเยร์ ให้ เป็นเช่นนั้นนอกจากนี้ ให้และพิจารณาองค์ประกอบของอาร์เรย์เป็นจำนวนเต็ม (ความแม่นยำตามอำเภอใจ) มอดูลัสสังเกตว่าเนื่องจากค่าสัมบูรณ์มีขนาดใหญ่พอที่จะรองรับตัวทดใดๆ ที่อาจเกิดขึ้นจากการคูณและดังนั้น ผลคูณ(มอดูลัส) สามารถคำนวณได้โดยการประเมินการสังเคราะห์ของ นอกจากนี้ ด้วยเราจะได้และดังนั้น จึง เป็น รากที่ n ของเอกภาพแบบดั้งเดิม มอดู ลั ส${\displaystyle M'}$${\displaystyle DM'\geq 2M+k}$${\displaystyle n'=DM'}$${\displaystyle A,B}$${\displaystyle 2^{n'}+1}$${\displaystyle 2^{n'}+1\geq 2^{2M+k}+1=D2^{2M}+1}$${\displaystyle a}$${\displaystyle b}$${\displaystyle ab}$${\displaystyle 2^{n}+1}$${\displaystyle A,B}$${\displaystyle g=2^{2M'}}$${\displaystyle g^{D/2}\equiv -1{\pmod {2^{n'}+1}}}$${\displaystyle g}$${\displaystyle D}$${\displaystyle 2^{n'}+1}$

ต่อไปเราจะทำการแปลงฟูริเยร์แบบไม่ต่อเนื่องของอาร์เรย์ในวงแหวนโดยใช้รากที่หนึ่งของเอกภาพเป็นฐานฟูริเยร์ ซึ่งจะได้อาร์เรย์ที่แปลงแล้วเนื่องจากเป็นกำลังของสอง การแปลงนี้จึงสามารถทำได้ในเวลาเชิงลอการิทึมโดยใช้ การแปลงฟูริเย ร์ แบบเร็ว${\displaystyle A,B}$${\displaystyle \mathbb {Z} /(2^{n'}+1)\mathbb {Z} }$${\displaystyle g}$${\displaystyle {\widehat {A}},{\widehat {B}}}$${\displaystyle D=2^{k}}$

ให้(ผลคูณแบบจุดต่อจุด) และคำนวณการแปลงผกผันของอาร์เรย์โดยใช้รากที่หนึ่งของเอกภาพอีกครั้งอาร์เรย์ในตอนนี้คือการสังเคราะห์ของอาร์เรย์สุดท้าย ผลคูณจะได้รับจากการประเมินค่า ${\displaystyle {\widehat {C}}_{i}={\widehat {A}}_{i}{\widehat {B}}_{i}}$${\displaystyle C}$${\displaystyle {\widehat {C}}}$${\displaystyle g}$${\displaystyle C}$${\displaystyle A,B}$${\displaystyle ab{\pmod {2^{n}+1}}}$$${\displaystyle ab\equiv \sum _{j}C_{j}2^{Mj}\mod {2^{n}+1}.}$$

อัลกอริทึมพื้นฐานนี้สามารถปรับปรุงได้หลายวิธี ประการแรก ไม่จำเป็นต้องจัดเก็บตัวเลขด้วยความแม่นยำสูง แต่สามารถจัดเก็บได้เพียงระดับบิต ซึ่งจะทำให้การแสดงผลอาร์เรย์ในเครื่องมีประสิทธิภาพมากขึ้นประการที่สอง เห็นได้ชัดว่าการคูณในการแปลงไปข้างหน้าเป็นการเลื่อนบิตอย่างง่าย ด้วยความระมัดระวัง ก็สามารถคำนวณการแปลงผกผันโดยใช้การเลื่อนบิตเพียงอย่างเดียวได้เช่นกัน ด้วยความระมัดระวัง จึงเป็นไปได้ที่จะกำจัดการคูณที่แท้จริงออกจากอัลกอริทึม ยกเว้นในส่วนที่ประเมินผลคูณแบบจุดต่อจุด ดังนั้นจึงเป็นประโยชน์ที่จะเลือกพารามิเตอร์เพื่อให้สามารถคำนวณผลคูณแบบจุดต่อจุดได้อย่างมีประสิทธิภาพ ไม่ว่าจะเป็นเพราะเป็นคำในเครื่องเพียงคำเดียว หรือใช้อัลกอริทึมที่ปรับให้เหมาะสมสำหรับการคูณจำนวนเต็มของจำนวนคำ (โดยอุดมคติคือจำนวนน้อย) การเลือกพารามิเตอร์จึงเป็นส่วนสำคัญสำหรับการปรับปรุงวิธีการให้ดียิ่งขึ้นต่อไป ${\displaystyle a,b}$${\displaystyle n'+1}$${\displaystyle A,B}$${\displaystyle {\widehat {C}}_{i}={\widehat {A}}_{i}{\widehat {B}}_{i}}$${\displaystyle D,M}$${\displaystyle D,M}$

ทุกจำนวนในระบบฐาน B สามารถเขียนได้ในรูปพหุนาม:

${\displaystyle X=\sum _{i=0}^{N}{x_{i}B^{i}}}$

นอกจากนี้ การคูณจำนวนสองจำนวนอาจมองได้ว่าเป็นผลคูณของพหุนามสองตัว:

${\displaystyle XY=\left(\sum _{i=0}^{N}{x_{i}B^{i}}\right)\left(\sum _{j=0}^{N}{y_{i}B^{j}}\right)}$

เพราะว่าสำหรับ: เราจะได้คอนโวลูชัน ${\displaystyle B^{k}}$${\displaystyle c_{k}=\sum _{(i,j):i+j=k}{a_{i}b_{j}}=\sum _{i=0}^{k}{a_{i}b_{ki}}}$

โดยใช้ FFT ( การแปลงฟูริเยร์แบบเร็ว ) ซึ่งใช้ในเวอร์ชันดั้งเดิมแทน NTT ( การแปลงเชิงทฤษฎีจำนวน ) ^{[ 7 ]}ด้วยกฎการสังเคราะห์ เราจะได้

${\displaystyle {\hat {f}}(a*b)={\hat {f}}\left(\sum _{i=0}^{k}a_{i}b_{ki}\right)={\hat {f}}(a)\bullet {\hat {f}}(b).}$

นั่นคือโดยที่ คือสัมประสิทธิ์ที่สอดคล้องกันในปริภูมิฟูริเยร์ ซึ่งสามารถเขียนได้อีกแบบว่า: ${\displaystyle C_{k}=a_{k}\bullet b_{k}}$${\displaystyle C_{k}}$${\displaystyle {\text{fft}}(a*b)={\text{fft}}(a)\bullet {\text{fft}}(b)}$

เราได้ค่าสัมประสิทธิ์เดียวกันเนื่องจากความเป็นเชิงเส้นภายใต้การแปลงฟูริเยร์ และเนื่องจากพหุนามเหล่านี้ประกอบด้วยพจน์ที่ไม่ซ้ำกันเพียงพจน์เดียวต่อค่าสัมประสิทธิ์:

${\displaystyle {\hat {f}}(x^{n})=\left({\frac {i}{2\pi }}\right)^{n}\delta ^{(n)}}$ และ

${\displaystyle {\hat {f}}(a\,X(\xi )+b\,Y(\xi ))=a\,{\hat {X}}(\xi )+b\,{\hat {Y}}(\xi )}$

กฎการสังเคราะห์:${\displaystyle {\hat {f}}(X*Y)=\ {\hat {f}}(X)\bullet {\hat {f}}(Y)}$

เราได้ลดปัญหาการหาค่าคอนโวลูชันให้เหลือเพียงปัญหาการหาค่าผลคูณ โดยใช้ FFT

โดยการหา FFT ของการประมาณค่าแบบพหุนามของแต่ละค่าเราสามารถกำหนดค่าสัมประสิทธิ์ที่ต้องการได้ ${\displaystyle C_{k}}$

อัลกอริทึมนี้ใช้วิธีแบ่งและพิชิต (divide-and-conquer)เพื่อแบ่งปัญหาออกเป็นปัญหาย่อยๆ

${\displaystyle c_{k}=\sum _{(i,j):i+j\equiv k{\pmod {N(n)}}}a_{i}b_{j}}$, ที่ไหน.${\displaystyle N(n)=2^{n}+1}$

โดยการปล่อยให้:

${\displaystyle a_{i}'=\theta ^{i}a_{i}}$และ${\displaystyle b_{j}'=\theta ^{j}b_{j},}$

เมื่อ ราก ^ที่ n อยู่เราจะเห็นว่า: ^{[ 8 ]}${\displaystyle \theta ^{N}=-1}$

${\displaystyle {\begin{aligned}C_{k}&=\sum _{(i,j):i+j\equiv k{\pmod {N(n)}}}a_{i}b_{j}=\theta ^{-k}\sum _{(i,j):i+j\equiv k{\pmod {N(n)}}}a_{i}'b_{j}'\\[6pt]&=\theta ^{-k}\left(\sum _{(i,j):i+j=k}a_{i}'b_{j}'+\sum _{(i,j):i+j=k+n}a_{i}'b_{j}'\right)\\[6pt]&=\theta ^{-k}\left(\sum _{(i,j):i+j=k}a_{i}b_{j}\theta ^{k}+\sum _{(i,j):i+j=k+n}a_{i}b_{j}\theta ^{n+k}\right)\\[6pt]&=\sum _{(i,j):i+j=k}a_{i}b_{j}+\theta ^{n}\sum _{(i,j):i+j=k+n}a_{i}b_{j}.\end{aligned}}}$

หมายความว่า เราสามารถใช้ค่าน้ำหนักแล้วคูณด้วยค่าที่ได้ในภายหลัง ${\displaystyle \theta ^{i}}$${\displaystyle \theta ^{-k}}$

แทนที่จะใช้ค่าน้ำหนักในขั้นตอนแรกของการเรียกซ้ำ (เมื่อ) เราสามารถคำนวณได้ดังนี้: ${\displaystyle \theta ^{N}=-1}$${\displaystyle n=N}$

${\displaystyle C_{k}=\sum _{(i,j):i+j\equiv k{\pmod {N(N)}}}=\sum _{(i,j):i+j=k}a_{i}b_{j}-\sum _{(i,j):i+j=k+n}a_{i}b_{j}}$

ในการแปลงฟูริเยร์แบบเร็ว (FFT) ปกติที่ทำงานกับจำนวนเชิงซ้อน จะใช้สูตรดังนี้:

$${\displaystyle \exp \left({\frac {2k\pi i}{n}}\right)=\cos {\frac {2k\pi }{n}}+i\sin {\frac {2k\pi }{n}},\qquad k=0,1,\dots ,n-1.}$$

${\displaystyle {\begin{aligned}C_{k}&=\theta ^{-k}\left(\sum _{(i,j):i+j=k}a_{i}b_{j}\theta ^{k}+\sum _{(i,j):i+j=k+n}a_{i}b_{j}\theta ^{n+k}\right)\\[6pt]&=e^{-i2\pi k/n}\left(\sum _{(i,j):i+j=k}a_{i}b_{j}e^{i2\pi k/n}+\sum _{(i,j):i+j=k+n}a_{i}b_{j}e^{i2\pi (n+k)/n}\right)\end{aligned}}}$

อย่างไรก็ตาม FFT ยังสามารถใช้เป็น NTT ( การแปลงเชิงทฤษฎีจำนวน ) ใน Schönhage–Strassen ได้อีกด้วย ซึ่งหมายความว่าเราต้องใช้θเพื่อสร้างจำนวนในฟิลด์จำกัด (ตัวอย่างเช่น) ${\displaystyle \mathrm {GF} (2^{n}+1)}$

รากแห่งเอกภาพภายใต้ฟิลด์จำกัดGF( r )คือสมาชิก a ที่ทำให้หรือตัวอย่างเช่นGF( p )โดยที่pเป็นจำนวนเฉพาะจะ ให้${\displaystyle \theta ^{r-1}\equiv 1}$${\displaystyle \theta ^{r}\equiv \theta }$${\displaystyle \{1,2,\ldots ,p-1\}}$

โปรดสังเกตว่าใน และในสำหรับผู้สมัครเหล่านี้ภายใต้ฟิลด์จำกัด และด้วยเหตุนี้จึงกระทำในแบบที่เราต้องการ ${\displaystyle 2^{n}\equiv -1}$${\displaystyle \operatorname {GF} (2^{n}+1)}$${\displaystyle {\sqrt {2}}\equiv -1}$${\displaystyle \operatorname {GF} (2^{n+2}+1)}$${\displaystyle \theta ^{N}\equiv -1}$

ยังคงสามารถใช้อัลกอริธึม FFT เดิมได้ ตราบใดที่θเป็นรากที่หนึ่งของเอกภาพของฟิลด์จำกัด

ในการหาค่าการแปลง FFT/NTT เราจะทำดังนี้:

${\displaystyle {\begin{aligned}C_{k}'&={\hat {f}}(k)={\hat {f}}\left(\theta ^{-k}\left(\sum _{(i,j):i+j=k}a_{i}b_{j}\theta ^{k}+\sum _{(i,j):i+j=k+n}a_{i}b_{j}\theta ^{n+k}\right)\right)\\[6pt]C_{k+k}'&={\hat {f}}(k+k)={\hat {f}}\left(\sum _{(i,j):i+j=2k}a_{i}b_{j}\theta ^{k}+\sum _{(i,j):i+j=n+2k}a_{i}b_{j}\theta ^{n+k}\right)\\[6pt]&={\hat {f}}\left(\sum _{(i,j):i+j=2k}a_{i}b_{j}\theta ^{k}+\sum _{(i,j):i+j=2k+n}a_{i}b_{j}\theta ^{n+k}\right)\\[6pt]&={\hat {f}}\left(A_{k\leftarrow k}\right)\bullet {\hat {f}}(B_{k\leftarrow k})+{\hat {f}}(A_{k\leftarrow k+n})\bullet {\hat {f}}(B_{k\leftarrow k+n})\end{aligned}}}$

ผลิตภัณฑ์แรกมีส่วนช่วยต่อสำหรับแต่ละkผลิตภัณฑ์ ที่สองมีส่วนช่วยต่อเนื่องจากmod${\displaystyle c_{k}}$${\displaystyle c_{k}}$${\displaystyle (i+j)}$${\displaystyle N(n)}$

เพื่อทำสิ่งที่ตรงกันข้าม:

${\displaystyle C_{k}=2^{-m}{\hat {f^{-1}}}(\theta ^{-k}C_{k+k}')}$หรือ${\displaystyle C_{k}={\hat {f^{-1}}}(\theta ^{-k}C_{k+k}')}$

ขึ้นอยู่กับว่าจำเป็นต้องปรับข้อมูลให้เป็นมาตรฐานหรือไม่

คูณด้วยค่าหนึ่งเพื่อปรับข้อมูล FFT ให้เป็นมาตรฐานในช่วงที่กำหนด โดยที่mหาได้จากการใช้ตัวผกผันการคูณแบบโมดูลาร์ ${\displaystyle 2^{-m}}$${\displaystyle {\frac {1}{n}}\equiv 2^{-m}{\bmod {N}}(n)}$

ในอัลกอริทึม Schönhage–Strassen ควรคิดว่าเป็นต้นไม้ไบนารีโดยมีค่าอยู่ในโดยให้สำหรับแต่ละKสามารถค้นหาทั้งหมดและจัดกลุ่มคู่ทั้งหมดเป็น M กลุ่มที่แตกต่างกัน การใช้เพื่อจัดกลุ่มคู่ผ่านการสังเคราะห์เป็นปัญหาคลาสสิกในอัลกอริทึม^{[ 9 ]}${\displaystyle N=2^{M}+1}$${\displaystyle 0\leq {\text{index}}\leq 2^{M}=2^{i+j}}$${\displaystyle K\in [0,M]}$${\displaystyle i+j=K}$${\displaystyle (i,j)}$${\displaystyle i+j=k}$${\displaystyle (i,j)}$

ด้วยเหตุนี้ โปรดช่วยเราจัดกลุ่มงานย่อยแต่ละกลุ่มตามระดับความลึกkในโครงสร้างแบบต้นไม้ด้วย${\displaystyle N=2^{M}+1}$${\displaystyle (i,j)}$${\displaystyle {\frac {M}{2^{k}}}}$${\displaystyle N=2^{\frac {M}{2^{k}}}+1}$

โปรดสังเกตว่าสำหรับค่า L บางค่า สิ่งนี้ทำให้ N เป็นจำนวนแฟร์มาต์เมื่อทำการมอดูเลตเราจะได้วงแหวนแฟร์มาต์ ${\displaystyle N=2^{M}+1=2^{2^{L}}+1}$${\displaystyle N=2^{M}+1=2^{2^{L}}+1}$

เนื่องจากจำนวนเฟอร์มาต์บางจำนวนเป็นจำนวนเฉพาะเฟอร์มาต์ ในบางกรณีจึงสามารถหลีกเลี่ยงการคำนวณได้

แน่นอนว่ายังมีจำนวนเฉพาะอื่นๆ อีกหลายจำนวน ที่สามารถนำมาใช้ได้ โดยให้ข้อดีของจำนวนเฉพาะเช่นเดียวกัน โดยการให้ จะ ทำให้ได้จำนวนสูงสุดในเลขฐานสองที่มีบิต เป็นจำนวนเมอร์เซนน์ ซึ่งในบางกรณีเป็นจำนวนเฉพาะเมอร์เซนน์ จึงเป็นตัวเลือกที่เหมาะสมที่จะใช้แทนจำนวนแฟร์มาต์${\displaystyle N=2^{k}-1}$${\displaystyle k+1}$${\displaystyle N=2^{k}-1}$${\displaystyle N=2^{2^{L}}+1}$

การคำนวณโมดูลัสหลายครั้งกับN ที่แตกต่างกัน อาจเป็นประโยชน์เมื่อต้องแก้ปัญหาผลคูณจำนวนเต็ม โดยใช้ทฤษฎีบทเศษเหลือของจีนหลังจากแบ่งM ออกเป็น Nประเภทต่างๆ ที่เล็กกว่าแล้วจะสามารถหาคำตอบของการคูณxy ได้ ^{[ 10 ]}

จำนวนเฟอร์มาต์และจำนวนเมอร์เซนน์เป็นเพียงสองประเภทของจำนวน ในสิ่งที่เรียกว่าจำนวนเฟอร์มาต์เมอร์เซนน์ทั่วไป (GSM) โดยมีสูตรดังนี้: ^{[ 11 ]}

${\displaystyle G_{q,p,n}=\sum _{i=1}^{p}q^{(p-i)n}={\frac {q^{pn}-1}{q^{n}-1}}}$

${\displaystyle M_{p,n}=G_{2,p,n}}$

ในสูตรนี้คือจำนวนแฟร์มาต์ และคือจำนวนเมอร์เซนน์ ${\displaystyle M_{2,2^{k}}}$${\displaystyle M_{p,1}}$

สูตรนี้สามารถใช้สร้างชุดสมการที่สามารถใช้ในทฤษฎีบทเศษเหลือของจีนได้: ^{[ 12 ]}

${\displaystyle g^{\frac {(M_{p,n}-1)}{2}}\equiv -1{\pmod {M_{p,n}}}}$โดยที่gเป็นจำนวนที่ทำให้มีx อยู่จริง โดย สมมติว่า${\displaystyle x^{2}\equiv g{\pmod {M_{p,n}}}}$${\displaystyle N=2^{n}}$

นอกจากนี้โดยที่aคือองค์ประกอบที่สร้างองค์ประกอบในในลักษณะเป็นวัฏจักร ${\displaystyle g^{2^{(p-1)n}-1}\equiv a^{2^{n}-1}{\pmod {M_{p,n}}}}$${\displaystyle \{1,2,4,...2^{n-1},2^{n}\}}$

ถ้าโดย ที่แล้ว${\displaystyle N=2^{t}}$${\displaystyle 1\leq t\leq n}$${\displaystyle g_{t}=a^{(2^{n}-1)2^{n-t}}}$

สูตรต่อไปนี้มีประโยชน์ในการหาค่าK ที่เหมาะสม (จำนวนกลุ่มที่จะแบ่ง บิต Nออก) โดยกำหนดขนาดบิตNโดยการคำนวณประสิทธิภาพ: ^{[ 13 ]}

${\displaystyle E={\frac {{\frac {2N}{K}}+k}{n}}}$Nคือขนาดบิต (ที่ใช้ใน) ในระดับนอกสุดKให้กลุ่มของบิต โดยที่ ${\displaystyle 2^{N}+1}$${\displaystyle {\frac {N}{K}}}$${\displaystyle K=2^{k}}$

หาค่าn ได้จาก N, Kและk โดยการหาค่า xที่เล็กที่สุดซึ่งทำให้ ${\displaystyle 2N/K+k\leq n=K2^{x}}$

ถ้าหากสมมติว่าประสิทธิภาพสูงกว่า 50% และค่า kน้อยมากเมื่อเทียบกับส่วนที่เหลือของสูตร จะได้ว่า ${\displaystyle {\frac {n}{2}}\leq {\frac {2N}{K}},K\leq n}$

${\displaystyle K\leq 2{\sqrt {N}}}$

นี่หมายความว่า: เมื่อบางสิ่งมีประสิทธิภาพสูงมากค่า Kจะถูกจำกัดค่าสูงสุดโดยหรือถูกจำกัดค่าสูงสุดในเชิงอนุกรมโดย${\displaystyle 2{\sqrt {N}}}$${\displaystyle {\sqrt {N}}}$

ตามอัลกอริทึมมาตรฐาน อัลกอริทึมการคูณโมดูลาร์ Schönhage-Strassen (พร้อมการปรับปรุงบางอย่าง) สามารถดูภาพรวมได้จาก^{[ 14 ]}

• T3MUL = การคูณแบบทูม-คุก
• SMUL = การคูณเชินฮาเกะ–สเตรสเซน
• ประเมินผล = FFT/IFFT

สำหรับรายละเอียดการใช้งาน สามารถอ่านหนังสือPrime Numbers: A Computational Perspectiveได้^{[ 15 ]}ตัวแปรนี้แตกต่างจากวิธีการดั้งเดิมของ Schönhage เล็กน้อยตรงที่ใช้การแปลงน้ำหนักแบบไม่ต่อเนื่องเพื่อทำการคอนโวลูชันแบบเนกาไซคลิกได้อย่างมีประสิทธิภาพมากขึ้น แหล่งข้อมูลโดยละเอียดอีกแหล่งหนึ่งคือThe Art of Computer Programming ของKnuth ^{[ 16 ]}

ส่วนนี้จะอธิบายถึงการปรับปรุงประสิทธิภาพที่สำคัญหลายประการในการใช้งานถนนเชินฮาเก-สตราสเซิน (Schönhage–Strassen)

เมื่อต่ำกว่าจุดตัดที่กำหนด การใช้อัลกอริธึมการคูณแบบอื่น เช่น การคูณแบบ Toom–Cook จะมีประสิทธิภาพมากกว่า^{[ 17 ]}

แนวคิดคือการใช้เป็นรากของเอกภาพที่ มีลำดับ ในฟิลด์จำกัด(ซึ่งเป็นคำตอบของสมการ) เมื่อถ่วงน้ำหนักค่าในแนวทาง NTT (การแปลงเชิงทฤษฎีจำนวน) พบว่าสามารถประหยัดเวลาในการคูณจำนวนเต็มได้ 10% ^{[ 18 ]}${\displaystyle {\sqrt {2}}}$${\displaystyle 2^{n+2}}$${\displaystyle \mathrm {GF} (2^{n+2}+1)}$${\displaystyle \theta ^{2^{n+2}}\equiv 1{\pmod {2^{n+2}+1}}}$

โดยการให้เราสามารถคำนวณ และร่วมกับ CRT (ทฤษฎีบทเศษเหลือของจีน) เพื่อหาค่าที่แน่นอนของการ^คูณ uv [ ^{19 ]}${\displaystyle m=N+h}$${\displaystyle uv{\bmod {2^{N}+1}}}$${\displaystyle (u{\bmod {2^{h}}})(v{\bmod {2}}^{h})}$