อัลกอริทึมตัวประกอบเฉพาะ (PFA)หรือที่เรียกว่าอัลกอริทึม Good–Thomas (1958/1963) เป็น อัลกอริทึม การแปลงฟูริเยร์แบบเร็ว (FFT) ที่แปลงการแปลงฟูริเยร์แบบไม่ต่อเนื่อง (DFT) ขนาดN = N ₁ N ₂ให้เป็น DFT สองมิติขนาด N ₁ × N ₂แต่เฉพาะในกรณีที่N ₁และN ₂เป็นจำนวนเฉพาะสัมพัทธ์ เท่านั้น การแปลงขนาดเล็กเหล่านี้ที่มีขนาดN ₁และN ₂สามารถคำนวณได้โดยการใช้ PFA ซ้ำๆหรือโดยใช้อัลกอริทึม FFT อื่นๆ

PFA ไม่ควรสับสนกับ การขยายแบบ ผสมฐานของอัลกอริทึม Cooley–Tukey ที่ได้รับความนิยม ซึ่งก็แบ่ง DFT ขนาดN = N ₁ N ₂ออกเป็นทรานส์ฟอร์มขนาดเล็กกว่าขนาดN ₁และN ₂ เช่น กันอัลกอริทึมหลังนี้สามารถใช้ ตัวประกอบ ใดก็ได้ (ไม่จำเป็นต้องเป็นจำนวนเฉพาะสัมพัทธ์) แต่มีข้อเสียคือต้องมีการคูณเพิ่มเติมด้วยรากของเอกภาพที่เรียกว่าตัวประกอบทวิเดิล นอกเหนือจากทรานส์ฟอร์มขนาดเล็กกว่า ในทางกลับกัน PFA มีข้อเสียคือใช้ได้เฉพาะกับตัวประกอบจำนวนเฉพาะสัมพัทธ์เท่านั้น (เช่น ใช้ไม่ได้กับขนาด ที่เป็นกำลังของสอง ) และต้องมีการจัดทำดัชนีข้อมูลใหม่ที่ซับซ้อนกว่าโดยอิงจากไอโซมอร์ฟิซึมของกลุ่มบวก อย่างไรก็ตาม โปรดทราบว่า PFA สามารถใช้ร่วมกับ Cooley–Tukey แบบผสมฐานได้ โดย PFA จะแยกตัวประกอบ Nออกเป็นส่วนประกอบจำนวนเฉพาะสัมพัทธ์ และ Cooley–Tukey จะจัดการกับตัวประกอบที่ซ้ำ กัน

PFA ยังมีความเกี่ยวข้องอย่างใกล้ชิดกับอัลกอริธึม Winograd FFT แบบซ้อนกัน โดยที่อัลกอริธึมหลังนี้จะทำการ แปลง N ₁ x N ₂ ที่แยกส่วนแล้ว ผ่านเทคนิคการสังเคราะห์แบบสองมิติที่ซับซ้อนกว่า ดังนั้นเอกสารเก่าบางฉบับจึงเรียกอัลกอริธึมของ Winograd ว่า PFA FFT ด้วยเช่นกัน

(แม้ว่า PFA จะแตกต่างจากอัลกอริธึม Cooley–Tukey แต่ ผลงานของ Goodในปี 1958 เกี่ยวกับ PFA ก็ถูกอ้างถึงว่าเป็นแรงบันดาลใจโดย Cooley และ Tukey ในบทความของพวกเขาในปี 1965 และในตอนแรกก็มีความสับสนอยู่บ้างว่าอัลกอริธึมทั้งสองแตกต่างกันหรือไม่ อันที่จริง มันเป็นงานวิจัย FFT ก่อนหน้านี้เพียงชิ้นเดียวที่พวกเขาอ้างถึง เนื่องจากในขณะนั้นพวกเขายังไม่ทราบถึงงานวิจัยก่อนหน้านี้ของ Gauss และคนอื่นๆ)

ให้เป็นพหุนาม และเป็น รากที่ n หลักของเอกภาพเรากำหนด DFT ของเป็นทูเปิล n ตัวกล่าวอีกนัยหนึ่งคือ ${\displaystyle a(x)}$${\displaystyle \omega _{n}}$${\displaystyle n}$${\displaystyle a(x)}$${\displaystyle n}$${\displaystyle ({\hat {a}}_{j})=(a(\omega _{n}^{j}))}$$${\displaystyle {\hat {a}}_{j}=\sum _{i=0}^{n-1}a_{i}\omega _{n}^{ij}\quad {\text{ สำหรับทุก }}j=0,1,\dots ,n-1.}$$

เพื่อความง่าย เราจะใช้สัญลักษณ์ แทนการแปลงนี้ ${\displaystyle {\text{DFT}}_{\omega _{n}}}$

PFA อาศัยการแยกตัวประกอบร่วมเฉพาะของและเปลี่ยนเป็นสำหรับบางตัวเลือกของโดยที่คือผลคูณเทนเซอร์ ${\textstyle n=\prod _{d=0}^{D-1}n_{d}}$${\displaystyle {\text{DFT}}_{\omega _{n}}}$${\textstyle \bigotimes _{d}{\text{DFT}__{\omega _{n_{d}}}}$${\displaystyle \omega _{n_{d}}}$${\textstyle \bigotimes }$

สำหรับการแยกตัวประกอบเฉพาะสัมพัทธ์เรามี${\displaystyle \textstyle n=\prod _{d=0}^{D-1}n_{d}}$แผนที่เศษเหลือแบบจีน จากไปโดยมี เป็นอินเวอร์ส โดยที่' sคือองค์ประกอบเอกลักษณ์เชิงตั้งฉากส่วนกลางที่มีเมื่อเลือก(ดังนั้น) เราเขียนใหม่ได้ดังนี้: ${\displaystyle m\mapsto (m{\bmod {n}__{d})}$${\displaystyle \mathbb {Z} _{n}}$${\textstyle \prod _{d=0}^{D-1}\mathbb {Z} _{n_{d}}}$${\textstyle (m_{d})\mapsto \sum _{d=0}^{D-1}e_{d}m_{d}}$${\displaystyle e_{d}}$${\textstyle \sum _{d=0}^{D-1}e_{d}=1{\pmod {n}}}$${\displaystyle \omega _{n_{d}}=\omega _{n}^{e_{d}}}$${\displaystyle \prod _{d=0}^{D-1}\omega _{n_{d}}=\omega _{n}^{\sum _{d=0}^{D-1}e_{d}}=\omega _{n}}$${\displaystyle {\text{DFT}}_{\omega _{n}}}$

$${\displaystyle {\hat {a}}_{j}=\sum _{i=0}^{n-1}a_{i}\omega _{n}^{ij}=\sum _{i=0}^{n-1}a_{i}\left(\prod _{d=0}^{D-1}\omega _{n_{d}}\right)^{ij}=\sum _{i=0}^{n-1}a_{i}\prod _{d=0}^{D-1}\omega _{n_{d}}^{(i{\bmod {n}}_{d})(j{\bmod {n}}_{d})}=\sum _{i_{0}=0}^{n_{0}-1}\cdots \sum _{i_{D-1}=0}^{n_{D-1}-1}a_{\sum _{d=0}^{D-1}e_{d}i_{d}}\prod _{d=0}^{D-1}\omega _{n_{d}}^{i_{d}(j{\bmod {n}}_{d})}.}$$

สุดท้ายนี้ ให้กำหนดและ⁠ ⁠แล้วเราจะได้ ${\displaystyle a_{i_{0},\dots ,i_{D-1}}=a_{\sum _{d=0}^{D-1}i_{d}e_{d}}}$${\displaystyle {\hat {a}}_{j_{0},\dots ,j_{D-1}}={\hat {a}}_{\sum _{d=0}^{D-1}j_{d}e_{d}}}$

$${\displaystyle {\hat {a}}_{j_{0},\dots ,j_{D-1}}=\sum _{i_{0}=0}^{n_{0}-1}\cdots \sum _{i_{D-1}=0}^{n_{D-1}-1}a_{i_{0},\dots ,i_{D-1}}\prod _{d=0}^{D-1}\omega _{n_{d}}^{i_{d}j_{d}}.}$$

ดังนั้น เราจึงได้ DFT แบบหลายมิติ⁠ ⁠${\displaystyle \textstyle \otimes _{d=0}^{D-1}{\text{DFT}}_{\omega _{n_{d}}}}$ .

PFA สามารถอธิบายได้ในระดับสูงโดยใช้ไอโซมอร์ฟิซึมของพีชคณิตก่อนอื่นเราต้องระลึกว่าสำหรับวงแหวนสลับที่และไอโซมอร์ฟิซึมกลุ่มจากไป⁠ ⁠เรามีไอโซมอร์ฟิซึมของพีชคณิตดังต่อไปนี้ ${\displaystyle R}$${\displaystyle G}$${\displaystyle \textstyle \prod _{d}G_{d}}$

$${\displaystyle R[G]\cong \bigotimes _{d}R[G_{d}],}$$

โดยที่หมายถึงผลคูณเทนเซอร์ของพีชคณิต ${\displaystyle \bigotimes }$

เพื่อดูว่า PFA ทำงานอย่างไร เราเลือกและเป็นกลุ่มบวกเรายังระบุเป็นและเป็น โดยเลือกเป็นไอโซมอร์ฟิซึมของกลุ่มเรา จะได้ไอโซมอร์ฟิซึม ของพีชคณิตหรืออีกทางหนึ่ง คือ${\displaystyle G=(\mathbb {Z} _{n},+,0)}$${\displaystyle G_{d}=(\mathbb {Z} _{n_{d}},+,0)}$${\displaystyle R[G]}$${\textstyle {\frac {R[x]}{\langle x^{n}-1\rangle }}}$${\displaystyle R[G_{d}]}$${\displaystyle \textstyle {\frac {R[x_{d}]}{\langle x_{d}^{n_{d}}-1\rangle }}}$${\displaystyle \eta =a\mapsto (a{\bmod {n}}_{d})}$${\displaystyle \textstyle G\cong \prod _{d}G_{d}}$${\textstyle \eta ^{*}:R[G]\cong \bigotimes _{d}R[G_{d}]}$

$${\displaystyle \eta ^{*}:{\frac {R[x]}{\langle x^{n}-1\rangle }}\cong \bigotimes _{d}{\frac {R[x_{d}]}{\langle x_{d}^{n_{d}}-1\rangle }}.}$$

ทีนี้ลองสังเกตดูว่าจริงๆ แล้วเป็นไอโซมอร์ฟิซึมทางพีชคณิตจากไปและแต่ละเป็นไอโซมอร์ฟิซึมทางพีชคณิตจากไปดังนั้นเราจึงมีไอโซมอร์ฟิซึมทางพีชคณิตจากไปสิ่งที่ PFA บอกเราก็คือโดยที่และเป็นการจัดเรียงดัชนีใหม่โดยไม่มีการคำนวณทางคณิตศาสตร์จริงใน ${\displaystyle {\text{DFT}}_{\omega _{n}}}$${\textstyle {\frac {R[x]}{\langle x^{n}-1\rangle }}}$${\textstyle \prod _{i}{\frac {R[x]}{\langle x-\omega _{n}^{i}\rangle }}}$${\displaystyle {\text{DFT}}_{\omega _{n_{d}}}}$${\textstyle {\frac {R[x]}{\langle {x_{d}}^{n_{d}}-1\rangle }}}$${\textstyle \prod _{i_{d}}{\frac {R[x_{d}]}{\langle x_{d}-\omega _{n_{d}}^{i_{d}}\rangle }}}$${\displaystyle \eta '}$${\textstyle \bigotimes _{d}\prod _{i_{d}}{\frac {R[x_{d}]}{\langle x_{d}-\omega _{n_{d}}^{i_{d}}\rangle }}}$${\textstyle \prod _{i}{\frac {R[x]}{\langle x-\omega _{n}^{i}\rangle }}}$${\textstyle {\text{DFT}}_{\omega _{n}}=\eta '\circ \bigotimes _{d}{\text{DFT}}_{\omega _{n_{d}}}\circ \eta ^{*}}$${\displaystyle \eta ^{*}}$${\displaystyle \eta '}$${\displaystyle R}$

โปรดสังเกตว่าเงื่อนไขสำหรับการแปลงเป็นขึ้นอยู่กับ "" ไอโซมอร์ฟิซึมกลุ่มบวกจากไปไอโซมอร์ฟิซึมกลุ่มบวกใดๆ ก็ใช้ได้ ในการนับจำนวนวิธีที่แปลงเป็นเราจำเป็นต้องนับจำนวนไอโซมอร์ฟิซึมกลุ่มบวกจากไปหรืออีกทางเลือกหนึ่งคือจำนวนออโตมอร์ฟิซึมกลุ่ม บวก บนเนื่องจากเป็นวัฏจักร ออโตมอร์ฟิ ซึมใดๆ ก็สามารถเขียนได้เป็น โดยที่เป็นตัวสร้างของตามนิยามของค่า' s คือค่าที่ไม่มีตัวหารร่วมกับดังนั้น จึงมีแผนที่ดังกล่าวจำนวน โดยที่คือฟังก์ชันโทเทียนต์ของออยเลอร์ตัวอย่างที่เล็กที่สุดคือโดยที่แสดงให้เห็นแผนที่สองแบบในเอกสาร: "การแมป CRT" และ "การแมป Ruritanian" ^{[ 1 ]}${\displaystyle {\text{DFT}}_{\omega _{n}}}$${\textstyle \eta '\circ \bigotimes _{d}{\text{DFT}}_{\omega _{n_{d}}}\circ \eta ^{*}}$${\displaystyle \eta }$${\displaystyle (\mathbb {Z} _{n},+,0)}$${\displaystyle \textstyle \prod _{d}(\mathbb {Z} _{n_{d}},+,0)}$${\displaystyle {\text{DFT}}_{\omega _{n}}}$${\displaystyle \textstyle \eta '\circ \bigotimes _{d}{\text{DFT}}_{\omega _{n_{d}}}\circ \eta ^{*}}$${\displaystyle (\mathbb {Z} _{n},+,0)}$${\textstyle \prod _{d}(\mathbb {Z} _{n_{d}},+,0)}$${\displaystyle (\mathbb {Z} _{n},+,0)}$${\displaystyle (\mathbb {Z} _{n},+,0)}$${\displaystyle 1\mapsto g}$${\displaystyle g}$${\displaystyle (\mathbb {Z} _{n},+,0)}$${\displaystyle (\mathbb {Z} _{n},+,0)}$${\displaystyle g}$${\displaystyle n}$${\displaystyle \varphi (n)}$${\displaystyle \varphi }$${\displaystyle n=6}$${\displaystyle \varphi (n)=2}$

• อัลกอริทึม FFT ของบลูสไตน์
• อัลกอริทึม FFT ของเรเดอร์