1988:
1418:
1983:{\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})}.}
2517:
201:'s 1958 work on the PFA was cited as inspiration by Cooley and Tukey in their 1965 paper, and there was initially some confusion about whether the two algorithms were different. In fact, it was the only prior FFT work cited by them, as they were not then aware of the earlier research by Gauss and others.)
3415:
2243:
4128:
544:
3955:
1377:
4565:
4321:
2238:
3811:
2104:
3271:
4029:
3584:
2587:
3702:
732:
3094:
1085:
416:
411:
1251:
1002:
4676:
4452:
3510:
3149:
2980:
2888:
1192:
3627:
3266:
910:
4488:
4244:
3451:
1413:
679:
580:
2821:
2741:
2512:{\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}}.}
4922:
4875:
4774:
4727:
4612:
4388:
4034:
858:
643:
3192:
939:
766:
5076:
2680:
4991:
4180:
3836:
2761:
263:
4804:
3841:
4155:
5011:
786:
4341:
1256:
1112:
316:
236:
177:
5041:
4962:
4942:
4824:
4200:
3016:
2921:
2643:
2619:
2109:
336:
285:
158:, in addition to the smaller transforms. On the other hand, PFA has the disadvantages that it only works for relatively prime factors (e.g. it is useless for
4493:
4249:
3707:
194:
transform via more sophisticated two-dimensional convolution techniques. Some older papers therefore also call
Winograd's algorithm a PFA FFT.
1993:
154:
factors (not necessarily relatively prime), but it has the disadvantage that it also requires extra multiplications by roots of unity called
3960:
3515:
2522:
3632:
3410:{\displaystyle \eta ^{*}:{\frac {R}{\langle x^{n}-1\rangle }}\cong \bigotimes _{d}{\frac {R}{\langle x_{d}^{n_{d}}-1\rangle }}.}
684:
3021:
2685:
1007:
341:
1197:
944:
3099:
4617:
4393:
3456:
2926:
2826:
1121:
3589:
3197:
866:
4457:
4213:
4123:{\textstyle {\text{DFT}}_{\omega _{n}}=\eta '\circ \bigotimes _{d}{\text{DFT}}_{\omega _{n_{d}}}\circ \eta ^{*}}
3420:
1382:
648:
549:
116:
2773:
539:{\displaystyle {\hat {a}}_{j}=\sum _{i=0}^{n-1}a_{i}\omega _{n}^{ij}\quad {\text{ for all }}j=0,1,\dots ,n-1.}
4880:
4833:
4732:
4685:
4570:
4346:
5087:
803:
588:
5014:
3154:
2764:
34:
915:
861:
737:
169:. Note, however, that PFA can be combined with mixed-radix Cooley–Tukey, with the former factorizing
3950:{\textstyle \bigotimes _{d}\prod _{i_{d}}{\frac {R}{\langle x_{d}-\omega _{n_{d}}^{i_{d}}\rangle }}}
5092:
5046:
5259:
4967:
2746:
2648:
266:
241:
5199:
Chan, S. C.; Ho, K. L. (1991). "On indexing the prime-factor fast
Fourier transform algorithm".
5078:, demonstrating the two maps in the literature: the "CRT mapping" and the "Ruritanian mapping".
4783:
4133:
1372:{\textstyle \prod _{d=0}^{D-1}\omega _{n_{d}}=\omega _{n}^{\sum _{d=0}^{D-1}e_{d}}=\omega _{n}}
30:
4996:
771:
4160:
3816:
4326:
2598:
1090:
2233:{\displaystyle {\hat {a}}_{j_{0},\dots ,j_{D-1}}={\hat {a}}_{\sum _{d=0}^{D-1}j_{d}e_{d}}}
292:
212:
8:
5020:
5237:
5154:
5137:
4947:
4927:
4809:
4185:
2985:
2897:
2628:
2604:
1115:
321:
270:
5191:
4560:{\textstyle \eta '\circ \bigotimes _{d}{\text{DFT}}_{\omega _{n_{d}}}\circ \eta ^{*}}
4454:. Any additive group isomorphism will work. To count the number of ways transforming
4316:{\textstyle \eta '\circ \bigotimes _{d}{\text{DFT}}_{\omega _{n_{d}}}\circ \eta ^{*}}
3806:{\textstyle \prod _{i_{d}}{\frac {R}{\langle x_{d}-\omega _{n_{d}}^{i_{d}}\rangle }}}
2622:
166:
5229:
5208:
5187:
87:
5241:
162:
sizes) and that it requires more complicated re-indexing of the data based on the
5128:
Good, I. J. (1958). "The interaction algorithm and practical
Fourier analysis".
2891:
789:
163:
155:
5253:
5233:
5220:
Good, I. J. (1971). "The relationship between two fast
Fourier transforms".
4827:
4777:
4679:
4205:
173:
into relatively prime components and the latter handling repeated factors.
159:
5175:
2099:{\displaystyle a_{i_{0},\dots ,i_{D-1}}=a_{\sum _{d=0}^{D-1}i_{d}e_{d}}}
5165:
Thomas, L. H. (1963). "Using a computer to solve problems in physics".
5158:
5141:
4567:, we only need to count the number of additive group isomorphisms from
198:
5212:
4024:{\textstyle \prod _{i}{\frac {R}{\langle x-\omega _{n}^{i}\rangle }}}
3579:{\textstyle \prod _{i}{\frac {R}{\langle x-\omega _{n}^{i}\rangle }}}
105:
5176:"Fast Fourier transforms: a tutorial review and a state of the art"
2582:{\displaystyle \otimes _{d=0}^{D-1}{\text{DFT}}_{\omega _{n_{d}}}}
197:(Although the PFA is distinct from the Cooley–Tukey algorithm,
3123:
1957:
1721:
1695:
884:
3697:{\textstyle {\frac {R}{\langle {x_{d}}^{n_{d}}-1\rangle }}}
727:{\textstyle \bigotimes _{d}{\text{DFT}}_{\omega _{n_{d}}}}
3089:{\textstyle {\frac {R}{\langle x_{d}^{n_{d}}-1\rangle }}}
4206:
1080:{\textstyle (m_{d})\mapsto \sum _{d=0}^{D-1}e_{d}m_{d}}
4620:
4496:
4396:
4252:
4037:
3963:
3844:
3710:
3635:
3518:
3459:
3200:
3157:
3024:
2929:
2651:
1259:
1124:
1010:
947:
806:
774:
687:
591:
5049:
5023:
4999:
4970:
4950:
4930:
4883:
4836:
4812:
4786:
4735:
4688:
4573:
4460:
4349:
4329:
4216:
4188:
4163:
4136:
3819:
3592:
3423:
3274:
3102:
2988:
2900:
2829:
2776:
2749:
2688:
2631:
2607:
2525:
2246:
2112:
1996:
1421:
1385:
1200:
1093:
918:
869:
740:
651:
552:
419:
406:{\displaystyle ({\hat {a}}_{j})=(a(\omega _{n}^{j}))}
344:
324:
295:
273:
244:
215:
1246:{\displaystyle \omega _{n_{d}}=\omega _{n}^{e_{d}}}
997:{\textstyle \prod _{d=0}^{D-1}\mathbb {Z} _{n_{d}}}
5130:Journal of the Royal Statistical Society, Series B
5070:
5035:
5005:
4985:
4956:
4936:
4916:
4869:
4818:
4798:
4768:
4721:
4670:
4606:
4559:
4482:
4446:
4382:
4335:
4315:
4238:
4194:
4174:
4149:
4122:
4023:
3949:
3830:
3805:
3696:
3621:
3578:
3504:
3445:
3409:
3260:
3186:
3143:
3088:
3010:
2974:
2915:
2882:
2815:
2755:
2735:
2674:
2637:
2613:
2597:PFA can be stated in a high-level way in terms of
2581:
2511:
2232:
2098:
1982:
1407:
1371:
1245:
1186:
1106:
1079:
996:
933:
904:
852:
780:
760:
726:
673:
637:
574:
538:
405:
330:
310:
279:
257:
230:
4671:{\textstyle \prod _{d}(\mathbb {Z} _{n_{d}},+,0)}
4447:{\textstyle \prod _{d}(\mathbb {Z} _{n_{d}},+,0)}
3505:{\textstyle {\frac {R}{\langle x^{n}-1\rangle }}}
3144:{\displaystyle \eta =a\mapsto (a{\bmod {n}}_{d})}
2975:{\textstyle {\frac {R}{\langle x^{n}-1\rangle }}}
5251:
2883:{\displaystyle G_{d}=(\mathbb {Z} _{n_{d}},+,0)}
1187:{\textstyle \sum _{d=0}^{D-1}e_{d}=1{\pmod {n}}}
546:For simplicity, we denote the transformation as
5173:
4678:, or alternative, the number of additive group
3622:{\displaystyle {\text{DFT}}_{\omega _{n_{d}}}}
3261:{\textstyle \eta ^{*}:R\cong \bigotimes _{d}R}
2601:. We first recall that for a commutative ring
2519:Therefore, we have the multi-dimensional DFT,
4182:are re-indexing without actual arithmetic in
585:The PFA relies on a coprime factorization of
4015:
3991:
3941:
3896:
3797:
3752:
3688:
3653:
3570:
3546:
3496:
3477:
3398:
3367:
3324:
3305:
3080:
3049:
2966:
2947:
2682:, we have the following algebra isomorphism
4210:Notice that the condition for transforming
905:{\displaystyle m\mapsto (m{\bmod {n}}_{d})}
180:, where the latter performs the decomposed
4483:{\displaystyle {\text{DFT}}_{\omega _{n}}}
4323:relies on "an" additive group isomorphism
4239:{\displaystyle {\text{DFT}}_{\omega _{n}}}
3446:{\displaystyle {\text{DFT}}_{\omega _{n}}}
2592:
1408:{\displaystyle {\text{DFT}}_{\omega _{n}}}
674:{\displaystyle {\text{DFT}}_{\omega _{n}}}
575:{\displaystyle {\text{DFT}}_{\omega _{n}}}
176:PFA is also closely related to the nested
5201:IEEE Transactions on Circuits and Systems
4889:
4842:
4741:
4694:
4636:
4579:
4412:
4355:
2848:
2788:
977:
921:
3453:is actually an algebra isomorphism from
2816:{\displaystyle G=(\mathbb {Z} _{n},+,0)}
2736:{\displaystyle R\cong \bigotimes _{d}R}
795:
5252:
5198:
5164:
4917:{\displaystyle (\mathbb {Z} _{n},+,0)}
4870:{\displaystyle (\mathbb {Z} _{n},+,0)}
4769:{\displaystyle (\mathbb {Z} _{n},+,0)}
4722:{\displaystyle (\mathbb {Z} _{n},+,0)}
4607:{\displaystyle (\mathbb {Z} _{n},+,0)}
4383:{\displaystyle (\mathbb {Z} _{n},+,0)}
1116:central orthogonal idempotent elements
853:{\textstyle n=\prod _{d=0}^{D-1}n_{d}}
638:{\textstyle n=\prod _{d=0}^{D-1}n_{d}}
119:, which also subdivides a DFT of size
108:or by using some other FFT algorithm.
104:can then be evaluated by applying PFA
33:(FFT) algorithm that re-expresses the
4780:, any automorphism can be written as
5219:
5127:
5111:
111:PFA should not be confused with the
3187:{\textstyle G\cong \prod _{d}G_{d}}
1176:
1169:
90:. These smaller transforms of size
13:
5174:Duhamel, P.; Vetterli, M. (1990).
3194:, we have the algebra isomorphism
14:
5271:
5167:Applications of Digital Computers
3813:, we have an algebra isomorphism
4944:'s are exactly those coprime to
2770:To see how PFA works, we choose
934:{\displaystyle \mathbb {Z} _{n}}
136:into smaller transforms of size
18:Fast Fourier Transform algorithm
4964:. Therefore, there are exactly
3629:is an algebra isomorphism from
761:{\displaystyle \omega _{n_{d}}}
497:
150:. The latter algorithm can use
5222:IEEE Transactions on Computers
5105:
5059:
5053:
4980:
4974:
4911:
4884:
4864:
4837:
4790:
4763:
4736:
4716:
4689:
4665:
4631:
4601:
4574:
4441:
4407:
4377:
4350:
3986:
3980:
3891:
3878:
3747:
3734:
3648:
3642:
3541:
3535:
3472:
3466:
3362:
3349:
3300:
3294:
3255:
3242:
3223:
3217:
3138:
3115:
3112:
3044:
3031:
3005:
2992:
2942:
2936:
2910:
2904:
2877:
2843:
2810:
2783:
2730:
2717:
2698:
2692:
2254:
2174:
2120:
1972:
1949:
1736:
1713:
1710:
1687:
1429:
1180:
1170:
1027:
1024:
1011:
899:
876:
873:
427:
400:
397:
379:
373:
367:
355:
345:
305:
299:
225:
219:
115:generalization of the popular
1:
5120:
5071:{\displaystyle \varphi (n)=2}
5192:10.1016/0165-1684(90)90158-U
4031:. What PFA tells us is that
2675:{\textstyle \prod _{d}G_{d}}
800:For a coprime factorization
204:
23:prime-factor algorithm (PFA)
7:
5081:
4986:{\displaystyle \varphi (n)}
2756:{\displaystyle \bigotimes }
258:{\displaystyle \omega _{n}}
10:
5276:
5017:. The smallest example is
4799:{\displaystyle 1\mapsto g}
2765:tensor product of algebras
35:discrete Fourier transform
5088:Bluestein's FFT algorithm
4150:{\displaystyle \eta ^{*}}
3151:as the group isomorphism
5098:
5015:Euler's totient function
5006:{\displaystyle \varphi }
781:{\textstyle \bigotimes }
5234:10.1109/T-C.1971.223236
4877:. By the definition of
2593:As Algebra Isomorphisms
289:. We define the DFT of
5072:
5037:
5007:
4987:
4958:
4938:
4918:
4871:
4820:
4800:
4770:
4723:
4672:
4608:
4561:
4484:
4448:
4384:
4337:
4317:
4240:
4196:
4176:
4175:{\displaystyle \eta '}
4151:
4124:
4025:
3951:
3832:
3831:{\displaystyle \eta '}
3807:
3698:
3623:
3580:
3506:
3447:
3411:
3262:
3188:
3145:
3090:
3012:
2976:
2917:
2884:
2817:
2757:
2737:
2676:
2639:
2615:
2583:
2513:
2466:
2397:
2341:
2234:
2207:
2100:
2073:
1984:
1921:
1872:
1840:
1784:
1669:
1632:
1571:
1528:
1470:
1409:
1373:
1343:
1286:
1247:
1188:
1151:
1108:
1081:
1056:
998:
974:
935:
906:
854:
839:
782:
762:
728:
675:
639:
624:
576:
540:
468:
407:
332:
312:
281:
259:
232:
178:Winograd FFT algorithm
117:Cooley–Tukey algorithm
31:fast Fourier transform
5093:Rader's FFT algorithm
5073:
5038:
5008:
4993:many such maps where
4988:
4959:
4939:
4919:
4872:
4821:
4801:
4771:
4724:
4673:
4609:
4562:
4485:
4449:
4385:
4338:
4336:{\displaystyle \eta }
4318:
4241:
4197:
4177:
4152:
4125:
4026:
3952:
3833:
3808:
3699:
3624:
3581:
3507:
3448:
3412:
3263:
3189:
3146:
3091:
3013:
2977:
2918:
2885:
2818:
2758:
2738:
2677:
2640:
2616:
2584:
2514:
2440:
2345:
2301:
2235:
2181:
2101:
2047:
1985:
1895:
1846:
1788:
1744:
1643:
1606:
1545:
1502:
1444:
1410:
1374:
1317:
1260:
1248:
1189:
1125:
1109:
1107:{\displaystyle e_{d}}
1087:as its inverse where
1082:
1030:
999:
948:
936:
907:
862:Chinese remainder map
855:
813:
783:
763:
729:
676:
640:
598:
577:
541:
442:
408:
333:
313:
282:
260:
233:
54:as a two-dimensional
27:Good–Thomas algorithm
5153:(2), 373-375 (1960)
5047:
5021:
4997:
4968:
4948:
4928:
4881:
4834:
4810:
4784:
4733:
4686:
4618:
4571:
4494:
4458:
4394:
4347:
4327:
4250:
4214:
4186:
4161:
4134:
4035:
3961:
3842:
3817:
3708:
3633:
3590:
3516:
3457:
3421:
3272:
3268:, or alternatively,
3198:
3155:
3100:
3022:
2986:
2927:
2898:
2827:
2774:
2747:
2686:
2649:
2629:
2605:
2599:algebra isomorphisms
2523:
2244:
2110:
1994:
1419:
1383:
1257:
1198:
1122:
1091:
1008:
945:
916:
867:
804:
796:Mapping Based on CRT
772:
738:
734:for some choices of
685:
649:
589:
550:
417:
342:
322:
311:{\displaystyle a(x)}
293:
271:
242:
238:be a polynomial and
231:{\displaystyle a(x)}
213:
5036:{\displaystyle n=6}
4014:
3940:
3796:
3569:
3391:
3073:
2894:. We also identify
2552:
2505:
1976:
1740:
1498:
1355:
1242:
500: for all
496:
396:
72:for the case where
5068:
5033:
5003:
4983:
4954:
4934:
4914:
4867:
4816:
4796:
4766:
4719:
4668:
4630:
4604:
4557:
4517:
4480:
4444:
4406:
4380:
4333:
4313:
4273:
4236:
4192:
4172:
4147:
4120:
4080:
4021:
4000:
3973:
3947:
3912:
3871:
3854:
3828:
3803:
3768:
3727:
3694:
3619:
3576:
3555:
3528:
3502:
3443:
3407:
3370:
3342:
3258:
3238:
3184:
3173:
3141:
3086:
3052:
3008:
2972:
2913:
2880:
2813:
2753:
2733:
2713:
2672:
2661:
2635:
2611:
2579:
2526:
2509:
2467:
2230:
2096:
1980:
1922:
1670:
1481:
1405:
1369:
1307:
1243:
1221:
1184:
1104:
1077:
994:
931:
902:
850:
778:
758:
724:
697:
671:
635:
572:
536:
479:
413:. In other words,
403:
382:
328:
308:
277:
255:
228:
29:(1958/1963), is a
25:, also called the
5180:Signal Processing
4957:{\displaystyle n}
4937:{\displaystyle g}
4819:{\displaystyle g}
4621:
4522:
4508:
4465:
4397:
4278:
4264:
4221:
4195:{\displaystyle R}
4085:
4071:
4042:
4019:
3964:
3945:
3855:
3845:
3801:
3711:
3692:
3597:
3574:
3519:
3500:
3428:
3417:Now observe that
3402:
3333:
3328:
3229:
3164:
3084:
3011:{\displaystyle R}
2970:
2916:{\displaystyle R}
2704:
2652:
2638:{\displaystyle G}
2623:group isomorphism
2614:{\displaystyle R}
2557:
2257:
2177:
2123:
1432:
1390:
702:
688:
656:
557:
501:
430:
358:
331:{\displaystyle n}
287:-th root of unity
280:{\displaystyle n}
5267:
5245:
5216:
5213:10.1109/31.85638
5195:
5170:
5145:
5114:
5109:
5077:
5075:
5074:
5069:
5042:
5040:
5039:
5034:
5012:
5010:
5009:
5004:
4992:
4990:
4989:
4984:
4963:
4961:
4960:
4955:
4943:
4941:
4940:
4935:
4923:
4921:
4920:
4915:
4898:
4897:
4892:
4876:
4874:
4873:
4868:
4851:
4850:
4845:
4825:
4823:
4822:
4817:
4805:
4803:
4802:
4797:
4775:
4773:
4772:
4767:
4750:
4749:
4744:
4728:
4726:
4725:
4720:
4703:
4702:
4697:
4677:
4675:
4674:
4669:
4652:
4651:
4650:
4649:
4639:
4629:
4613:
4611:
4610:
4605:
4588:
4587:
4582:
4566:
4564:
4563:
4558:
4556:
4555:
4543:
4542:
4541:
4540:
4539:
4538:
4523:
4520:
4516:
4504:
4489:
4487:
4486:
4481:
4479:
4478:
4477:
4476:
4466:
4463:
4453:
4451:
4450:
4445:
4428:
4427:
4426:
4425:
4415:
4405:
4389:
4387:
4386:
4381:
4364:
4363:
4358:
4342:
4340:
4339:
4334:
4322:
4320:
4319:
4314:
4312:
4311:
4299:
4298:
4297:
4296:
4295:
4294:
4279:
4276:
4272:
4260:
4245:
4243:
4242:
4237:
4235:
4234:
4233:
4232:
4222:
4219:
4201:
4199:
4198:
4193:
4181:
4179:
4178:
4173:
4171:
4156:
4154:
4153:
4148:
4146:
4145:
4129:
4127:
4126:
4121:
4119:
4118:
4106:
4105:
4104:
4103:
4102:
4101:
4086:
4083:
4079:
4067:
4056:
4055:
4054:
4053:
4043:
4040:
4030:
4028:
4027:
4022:
4020:
4018:
4013:
4008:
3989:
3975:
3972:
3956:
3954:
3953:
3948:
3946:
3944:
3939:
3938:
3937:
3927:
3926:
3925:
3908:
3907:
3894:
3890:
3889:
3873:
3870:
3869:
3868:
3853:
3837:
3835:
3834:
3829:
3827:
3812:
3810:
3809:
3804:
3802:
3800:
3795:
3794:
3793:
3783:
3782:
3781:
3764:
3763:
3750:
3746:
3745:
3729:
3726:
3725:
3724:
3703:
3701:
3700:
3695:
3693:
3691:
3681:
3680:
3679:
3678:
3668:
3667:
3666:
3651:
3637:
3628:
3626:
3625:
3620:
3618:
3617:
3616:
3615:
3614:
3613:
3598:
3595:
3585:
3583:
3582:
3577:
3575:
3573:
3568:
3563:
3544:
3530:
3527:
3511:
3509:
3508:
3503:
3501:
3499:
3489:
3488:
3475:
3461:
3452:
3450:
3449:
3444:
3442:
3441:
3440:
3439:
3429:
3426:
3416:
3414:
3413:
3408:
3403:
3401:
3390:
3389:
3388:
3378:
3365:
3361:
3360:
3344:
3341:
3329:
3327:
3317:
3316:
3303:
3289:
3284:
3283:
3267:
3265:
3264:
3259:
3254:
3253:
3237:
3210:
3209:
3193:
3191:
3190:
3185:
3183:
3182:
3172:
3150:
3148:
3147:
3142:
3137:
3136:
3131:
3130:
3095:
3093:
3092:
3087:
3085:
3083:
3072:
3071:
3070:
3060:
3047:
3043:
3042:
3026:
3017:
3015:
3014:
3009:
3004:
3003:
2981:
2979:
2978:
2973:
2971:
2969:
2959:
2958:
2945:
2931:
2922:
2920:
2919:
2914:
2889:
2887:
2886:
2881:
2864:
2863:
2862:
2861:
2851:
2839:
2838:
2822:
2820:
2819:
2814:
2797:
2796:
2791:
2762:
2760:
2759:
2754:
2742:
2740:
2739:
2734:
2729:
2728:
2712:
2681:
2679:
2678:
2673:
2671:
2670:
2660:
2644:
2642:
2641:
2636:
2620:
2618:
2617:
2612:
2588:
2586:
2585:
2580:
2578:
2577:
2576:
2575:
2574:
2573:
2558:
2555:
2551:
2540:
2518:
2516:
2515:
2510:
2504:
2503:
2502:
2493:
2492:
2482:
2481:
2480:
2465:
2454:
2439:
2438:
2437:
2436:
2412:
2411:
2396:
2389:
2388:
2372:
2365:
2364:
2340:
2333:
2332:
2322:
2315:
2314:
2297:
2296:
2295:
2294:
2270:
2269:
2259:
2258:
2250:
2239:
2237:
2236:
2231:
2229:
2228:
2227:
2226:
2217:
2216:
2206:
2195:
2179:
2178:
2170:
2163:
2162:
2161:
2160:
2136:
2135:
2125:
2124:
2116:
2105:
2103:
2102:
2097:
2095:
2094:
2093:
2092:
2083:
2082:
2072:
2061:
2038:
2037:
2036:
2035:
2011:
2010:
1990:Finally, define
1989:
1987:
1986:
1981:
1975:
1971:
1970:
1965:
1964:
1948:
1947:
1937:
1936:
1935:
1920:
1909:
1894:
1893:
1892:
1891:
1882:
1881:
1871:
1860:
1839:
1832:
1831:
1815:
1808:
1807:
1783:
1776:
1775:
1765:
1758:
1757:
1739:
1735:
1734:
1729:
1728:
1709:
1708:
1703:
1702:
1685:
1684:
1683:
1668:
1657:
1642:
1641:
1631:
1620:
1602:
1601:
1593:
1589:
1588:
1587:
1586:
1585:
1570:
1559:
1538:
1537:
1527:
1516:
1497:
1489:
1480:
1479:
1469:
1458:
1440:
1439:
1434:
1433:
1425:
1414:
1412:
1411:
1406:
1404:
1403:
1402:
1401:
1391:
1388:
1378:
1376:
1375:
1370:
1368:
1367:
1354:
1353:
1352:
1342:
1331:
1315:
1303:
1302:
1301:
1300:
1285:
1274:
1252:
1250:
1249:
1244:
1241:
1240:
1239:
1229:
1217:
1216:
1215:
1214:
1193:
1191:
1190:
1185:
1183:
1161:
1160:
1150:
1139:
1113:
1111:
1110:
1105:
1103:
1102:
1086:
1084:
1083:
1078:
1076:
1075:
1066:
1065:
1055:
1044:
1023:
1022:
1003:
1001:
1000:
995:
993:
992:
991:
990:
980:
973:
962:
940:
938:
937:
932:
930:
929:
924:
911:
909:
908:
903:
898:
897:
892:
891:
859:
857:
856:
851:
849:
848:
838:
827:
787:
785:
784:
779:
767:
765:
764:
759:
757:
756:
755:
754:
733:
731:
730:
725:
723:
722:
721:
720:
719:
718:
703:
700:
696:
680:
678:
677:
672:
670:
669:
668:
667:
657:
654:
644:
642:
641:
636:
634:
633:
623:
612:
581:
579:
578:
573:
571:
570:
569:
568:
558:
555:
545:
543:
542:
537:
502:
499:
495:
487:
478:
477:
467:
456:
438:
437:
432:
431:
423:
412:
410:
409:
404:
395:
390:
366:
365:
360:
359:
351:
337:
335:
334:
329:
317:
315:
314:
309:
286:
284:
283:
278:
264:
262:
261:
256:
254:
253:
237:
235:
234:
229:
88:relatively prime
37:(DFT) of a size
5275:
5274:
5270:
5269:
5268:
5266:
5265:
5264:
5250:
5249:
5248:
5169:. Boston: Ginn.
5123:
5118:
5117:
5110:
5106:
5101:
5084:
5048:
5045:
5044:
5022:
5019:
5018:
4998:
4995:
4994:
4969:
4966:
4965:
4949:
4946:
4945:
4929:
4926:
4925:
4893:
4888:
4887:
4882:
4879:
4878:
4846:
4841:
4840:
4835:
4832:
4831:
4811:
4808:
4807:
4785:
4782:
4781:
4745:
4740:
4739:
4734:
4731:
4730:
4698:
4693:
4692:
4687:
4684:
4683:
4645:
4641:
4640:
4635:
4634:
4625:
4619:
4616:
4615:
4583:
4578:
4577:
4572:
4569:
4568:
4551:
4547:
4534:
4530:
4529:
4525:
4524:
4519:
4518:
4512:
4497:
4495:
4492:
4491:
4472:
4468:
4467:
4462:
4461:
4459:
4456:
4455:
4421:
4417:
4416:
4411:
4410:
4401:
4395:
4392:
4391:
4359:
4354:
4353:
4348:
4345:
4344:
4328:
4325:
4324:
4307:
4303:
4290:
4286:
4285:
4281:
4280:
4275:
4274:
4268:
4253:
4251:
4248:
4247:
4228:
4224:
4223:
4218:
4217:
4215:
4212:
4211:
4208:
4187:
4184:
4183:
4164:
4162:
4159:
4158:
4141:
4137:
4135:
4132:
4131:
4114:
4110:
4097:
4093:
4092:
4088:
4087:
4082:
4081:
4075:
4060:
4049:
4045:
4044:
4039:
4038:
4036:
4033:
4032:
4009:
4004:
3990:
3976:
3974:
3968:
3962:
3959:
3958:
3933:
3929:
3928:
3921:
3917:
3916:
3903:
3899:
3895:
3885:
3881:
3874:
3872:
3864:
3860:
3859:
3849:
3843:
3840:
3839:
3820:
3818:
3815:
3814:
3789:
3785:
3784:
3777:
3773:
3772:
3759:
3755:
3751:
3741:
3737:
3730:
3728:
3720:
3716:
3715:
3709:
3706:
3705:
3674:
3670:
3669:
3662:
3658:
3657:
3656:
3652:
3638:
3636:
3634:
3631:
3630:
3609:
3605:
3604:
3600:
3599:
3594:
3593:
3591:
3588:
3587:
3564:
3559:
3545:
3531:
3529:
3523:
3517:
3514:
3513:
3484:
3480:
3476:
3462:
3460:
3458:
3455:
3454:
3435:
3431:
3430:
3425:
3424:
3422:
3419:
3418:
3384:
3380:
3379:
3374:
3366:
3356:
3352:
3345:
3343:
3337:
3312:
3308:
3304:
3290:
3288:
3279:
3275:
3273:
3270:
3269:
3249:
3245:
3233:
3205:
3201:
3199:
3196:
3195:
3178:
3174:
3168:
3156:
3153:
3152:
3132:
3126:
3122:
3121:
3101:
3098:
3097:
3066:
3062:
3061:
3056:
3048:
3038:
3034:
3027:
3025:
3023:
3020:
3019:
2999:
2995:
2987:
2984:
2983:
2954:
2950:
2946:
2932:
2930:
2928:
2925:
2924:
2899:
2896:
2895:
2892:additive groups
2857:
2853:
2852:
2847:
2846:
2834:
2830:
2828:
2825:
2824:
2792:
2787:
2786:
2775:
2772:
2771:
2748:
2745:
2744:
2724:
2720:
2708:
2687:
2684:
2683:
2666:
2662:
2656:
2650:
2647:
2646:
2630:
2627:
2626:
2606:
2603:
2602:
2595:
2569:
2565:
2564:
2560:
2559:
2554:
2553:
2541:
2530:
2524:
2521:
2520:
2498:
2494:
2488:
2484:
2483:
2476:
2472:
2471:
2455:
2444:
2426:
2422:
2407:
2403:
2402:
2398:
2378:
2374:
2373:
2354:
2350:
2349:
2328:
2324:
2323:
2310:
2306:
2305:
2284:
2280:
2265:
2261:
2260:
2249:
2248:
2247:
2245:
2242:
2241:
2222:
2218:
2212:
2208:
2196:
2185:
2180:
2169:
2168:
2167:
2150:
2146:
2131:
2127:
2126:
2115:
2114:
2113:
2111:
2108:
2107:
2088:
2084:
2078:
2074:
2062:
2051:
2046:
2042:
2025:
2021:
2006:
2002:
2001:
1997:
1995:
1992:
1991:
1966:
1960:
1956:
1955:
1943:
1939:
1938:
1931:
1927:
1926:
1910:
1899:
1887:
1883:
1877:
1873:
1861:
1850:
1845:
1841:
1821:
1817:
1816:
1797:
1793:
1792:
1771:
1767:
1766:
1753:
1749:
1748:
1730:
1724:
1720:
1719:
1704:
1698:
1694:
1693:
1686:
1679:
1675:
1674:
1658:
1647:
1637:
1633:
1621:
1610:
1594:
1581:
1577:
1576:
1572:
1560:
1549:
1544:
1540:
1539:
1533:
1529:
1517:
1506:
1490:
1485:
1475:
1471:
1459:
1448:
1435:
1424:
1423:
1422:
1420:
1417:
1416:
1397:
1393:
1392:
1387:
1386:
1384:
1381:
1380:
1363:
1359:
1348:
1344:
1332:
1321:
1316:
1311:
1296:
1292:
1291:
1287:
1275:
1264:
1258:
1255:
1254:
1235:
1231:
1230:
1225:
1210:
1206:
1205:
1201:
1199:
1196:
1195:
1168:
1156:
1152:
1140:
1129:
1123:
1120:
1119:
1098:
1094:
1092:
1089:
1088:
1071:
1067:
1061:
1057:
1045:
1034:
1018:
1014:
1009:
1006:
1005:
986:
982:
981:
976:
975:
963:
952:
946:
943:
942:
925:
920:
919:
917:
914:
913:
893:
887:
883:
882:
868:
865:
864:
844:
840:
828:
817:
805:
802:
801:
798:
773:
770:
769:
750:
746:
745:
741:
739:
736:
735:
714:
710:
709:
705:
704:
699:
698:
692:
686:
683:
682:
663:
659:
658:
653:
652:
650:
647:
646:
629:
625:
613:
602:
590:
587:
586:
564:
560:
559:
554:
553:
551:
548:
547:
498:
488:
483:
473:
469:
457:
446:
433:
422:
421:
420:
418:
415:
414:
391:
386:
361:
350:
349:
348:
343:
340:
339:
323:
320:
319:
294:
291:
290:
272:
269:
268:
249:
245:
243:
240:
239:
214:
211:
210:
207:
193:
186:
156:twiddle factors
149:
142:
135:
129:
103:
96:
85:
78:
67:
60:
53:
47:
19:
12:
11:
5:
5273:
5263:
5262:
5260:FFT algorithms
5247:
5246:
5228:(3): 310–317.
5217:
5207:(8): 951–953.
5196:
5186:(4): 259–299.
5171:
5162:
5136:(2): 361–372.
5124:
5122:
5119:
5116:
5115:
5103:
5102:
5100:
5097:
5096:
5095:
5090:
5083:
5080:
5067:
5064:
5061:
5058:
5055:
5052:
5032:
5029:
5026:
5002:
4982:
4979:
4976:
4973:
4953:
4933:
4913:
4910:
4907:
4904:
4901:
4896:
4891:
4886:
4866:
4863:
4860:
4857:
4854:
4849:
4844:
4839:
4815:
4795:
4792:
4789:
4765:
4762:
4759:
4756:
4753:
4748:
4743:
4738:
4718:
4715:
4712:
4709:
4706:
4701:
4696:
4691:
4667:
4664:
4661:
4658:
4655:
4648:
4644:
4638:
4633:
4628:
4624:
4603:
4600:
4597:
4594:
4591:
4586:
4581:
4576:
4554:
4550:
4546:
4537:
4533:
4528:
4515:
4511:
4507:
4503:
4500:
4475:
4471:
4443:
4440:
4437:
4434:
4431:
4424:
4420:
4414:
4409:
4404:
4400:
4379:
4376:
4373:
4370:
4367:
4362:
4357:
4352:
4332:
4310:
4306:
4302:
4293:
4289:
4284:
4271:
4267:
4263:
4259:
4256:
4231:
4227:
4207:
4204:
4191:
4170:
4167:
4144:
4140:
4117:
4113:
4109:
4100:
4096:
4091:
4078:
4074:
4070:
4066:
4063:
4059:
4052:
4048:
4017:
4012:
4007:
4003:
3999:
3996:
3993:
3988:
3985:
3982:
3979:
3971:
3967:
3943:
3936:
3932:
3924:
3920:
3915:
3911:
3906:
3902:
3898:
3893:
3888:
3884:
3880:
3877:
3867:
3863:
3858:
3852:
3848:
3826:
3823:
3799:
3792:
3788:
3780:
3776:
3771:
3767:
3762:
3758:
3754:
3749:
3744:
3740:
3736:
3733:
3723:
3719:
3714:
3690:
3687:
3684:
3677:
3673:
3665:
3661:
3655:
3650:
3647:
3644:
3641:
3612:
3608:
3603:
3572:
3567:
3562:
3558:
3554:
3551:
3548:
3543:
3540:
3537:
3534:
3526:
3522:
3498:
3495:
3492:
3487:
3483:
3479:
3474:
3471:
3468:
3465:
3438:
3434:
3406:
3400:
3397:
3394:
3387:
3383:
3377:
3373:
3369:
3364:
3359:
3355:
3351:
3348:
3340:
3336:
3332:
3326:
3323:
3320:
3315:
3311:
3307:
3302:
3299:
3296:
3293:
3287:
3282:
3278:
3257:
3252:
3248:
3244:
3241:
3236:
3232:
3228:
3225:
3222:
3219:
3216:
3213:
3208:
3204:
3181:
3177:
3171:
3167:
3163:
3160:
3140:
3135:
3129:
3125:
3120:
3117:
3114:
3111:
3108:
3105:
3082:
3079:
3076:
3069:
3065:
3059:
3055:
3051:
3046:
3041:
3037:
3033:
3030:
3007:
3002:
2998:
2994:
2991:
2968:
2965:
2962:
2957:
2953:
2949:
2944:
2941:
2938:
2935:
2912:
2909:
2906:
2903:
2879:
2876:
2873:
2870:
2867:
2860:
2856:
2850:
2845:
2842:
2837:
2833:
2812:
2809:
2806:
2803:
2800:
2795:
2790:
2785:
2782:
2779:
2763:refers to the
2752:
2732:
2727:
2723:
2719:
2716:
2711:
2707:
2703:
2700:
2697:
2694:
2691:
2669:
2665:
2659:
2655:
2634:
2610:
2594:
2591:
2572:
2568:
2563:
2550:
2547:
2544:
2539:
2536:
2533:
2529:
2508:
2501:
2497:
2491:
2487:
2479:
2475:
2470:
2464:
2461:
2458:
2453:
2450:
2447:
2443:
2435:
2432:
2429:
2425:
2421:
2418:
2415:
2410:
2406:
2401:
2395:
2392:
2387:
2384:
2381:
2377:
2371:
2368:
2363:
2360:
2357:
2353:
2348:
2344:
2339:
2336:
2331:
2327:
2321:
2318:
2313:
2309:
2304:
2300:
2293:
2290:
2287:
2283:
2279:
2276:
2273:
2268:
2264:
2256:
2253:
2225:
2221:
2215:
2211:
2205:
2202:
2199:
2194:
2191:
2188:
2184:
2176:
2173:
2166:
2159:
2156:
2153:
2149:
2145:
2142:
2139:
2134:
2130:
2122:
2119:
2091:
2087:
2081:
2077:
2071:
2068:
2065:
2060:
2057:
2054:
2050:
2045:
2041:
2034:
2031:
2028:
2024:
2020:
2017:
2014:
2009:
2005:
2000:
1979:
1974:
1969:
1963:
1959:
1954:
1951:
1946:
1942:
1934:
1930:
1925:
1919:
1916:
1913:
1908:
1905:
1902:
1898:
1890:
1886:
1880:
1876:
1870:
1867:
1864:
1859:
1856:
1853:
1849:
1844:
1838:
1835:
1830:
1827:
1824:
1820:
1814:
1811:
1806:
1803:
1800:
1796:
1791:
1787:
1782:
1779:
1774:
1770:
1764:
1761:
1756:
1752:
1747:
1743:
1738:
1733:
1727:
1723:
1718:
1715:
1712:
1707:
1701:
1697:
1692:
1689:
1682:
1678:
1673:
1667:
1664:
1661:
1656:
1653:
1650:
1646:
1640:
1636:
1630:
1627:
1624:
1619:
1616:
1613:
1609:
1605:
1600:
1597:
1592:
1584:
1580:
1575:
1569:
1566:
1563:
1558:
1555:
1552:
1548:
1543:
1536:
1532:
1526:
1523:
1520:
1515:
1512:
1509:
1505:
1501:
1496:
1493:
1488:
1484:
1478:
1474:
1468:
1465:
1462:
1457:
1454:
1451:
1447:
1443:
1438:
1431:
1428:
1400:
1396:
1379:), we rewrite
1366:
1362:
1358:
1351:
1347:
1341:
1338:
1335:
1330:
1327:
1324:
1320:
1314:
1310:
1306:
1299:
1295:
1290:
1284:
1281:
1278:
1273:
1270:
1267:
1263:
1238:
1234:
1228:
1224:
1220:
1213:
1209:
1204:
1182:
1179:
1175:
1172:
1167:
1164:
1159:
1155:
1149:
1146:
1143:
1138:
1135:
1132:
1128:
1101:
1097:
1074:
1070:
1064:
1060:
1054:
1051:
1048:
1043:
1040:
1037:
1033:
1029:
1026:
1021:
1017:
1013:
989:
985:
979:
972:
969:
966:
961:
958:
955:
951:
928:
923:
901:
896:
890:
886:
881:
878:
875:
872:
860:, we have the
847:
843:
837:
834:
831:
826:
823:
820:
816:
812:
809:
797:
794:
790:tensor product
777:
753:
749:
744:
717:
713:
708:
695:
691:
666:
662:
632:
628:
622:
619:
616:
611:
608:
605:
601:
597:
594:
567:
563:
535:
532:
529:
526:
523:
520:
517:
514:
511:
508:
505:
494:
491:
486:
482:
476:
472:
466:
463:
460:
455:
452:
449:
445:
441:
436:
429:
426:
402:
399:
394:
389:
385:
381:
378:
375:
372:
369:
364:
357:
354:
347:
327:
307:
304:
301:
298:
276:
252:
248:
227:
224:
221:
218:
206:
203:
191:
184:
164:additive group
147:
140:
133:
127:
101:
94:
83:
76:
65:
58:
51:
45:
17:
9:
6:
4:
3:
2:
5272:
5261:
5258:
5257:
5255:
5243:
5239:
5235:
5231:
5227:
5223:
5218:
5214:
5210:
5206:
5202:
5197:
5193:
5189:
5185:
5181:
5177:
5172:
5168:
5163:
5160:
5156:
5152:
5149:
5143:
5139:
5135:
5131:
5126:
5125:
5113:
5108:
5104:
5094:
5091:
5089:
5086:
5085:
5079:
5065:
5062:
5056:
5050:
5030:
5027:
5024:
5016:
5000:
4977:
4971:
4951:
4931:
4908:
4905:
4902:
4899:
4894:
4861:
4858:
4855:
4852:
4847:
4829:
4813:
4793:
4787:
4779:
4760:
4757:
4754:
4751:
4746:
4713:
4710:
4707:
4704:
4699:
4681:
4680:automorphisms
4662:
4659:
4656:
4653:
4646:
4642:
4626:
4622:
4598:
4595:
4592:
4589:
4584:
4552:
4548:
4544:
4535:
4531:
4526:
4513:
4509:
4505:
4501:
4498:
4473:
4469:
4438:
4435:
4432:
4429:
4422:
4418:
4402:
4398:
4374:
4371:
4368:
4365:
4360:
4330:
4308:
4304:
4300:
4291:
4287:
4282:
4269:
4265:
4261:
4257:
4254:
4229:
4225:
4203:
4189:
4168:
4165:
4142:
4138:
4115:
4111:
4107:
4098:
4094:
4089:
4076:
4072:
4068:
4064:
4061:
4057:
4050:
4046:
4010:
4005:
4001:
3997:
3994:
3983:
3977:
3969:
3965:
3934:
3930:
3922:
3918:
3913:
3909:
3904:
3900:
3886:
3882:
3875:
3865:
3861:
3856:
3850:
3846:
3824:
3821:
3790:
3786:
3778:
3774:
3769:
3765:
3760:
3756:
3742:
3738:
3731:
3721:
3717:
3712:
3685:
3682:
3675:
3671:
3663:
3659:
3645:
3639:
3610:
3606:
3601:
3565:
3560:
3556:
3552:
3549:
3538:
3532:
3524:
3520:
3493:
3490:
3485:
3481:
3469:
3463:
3436:
3432:
3404:
3395:
3392:
3385:
3381:
3375:
3371:
3357:
3353:
3346:
3338:
3334:
3330:
3321:
3318:
3313:
3309:
3297:
3291:
3285:
3280:
3276:
3250:
3246:
3239:
3234:
3230:
3226:
3220:
3214:
3211:
3206:
3202:
3179:
3175:
3169:
3165:
3161:
3158:
3133:
3127:
3118:
3109:
3106:
3103:
3077:
3074:
3067:
3063:
3057:
3053:
3039:
3035:
3028:
3000:
2996:
2989:
2963:
2960:
2955:
2951:
2939:
2933:
2907:
2901:
2893:
2874:
2871:
2868:
2865:
2858:
2854:
2840:
2835:
2831:
2807:
2804:
2801:
2798:
2793:
2780:
2777:
2768:
2766:
2750:
2725:
2721:
2714:
2709:
2705:
2701:
2695:
2689:
2667:
2663:
2657:
2653:
2632:
2624:
2608:
2600:
2590:
2570:
2566:
2561:
2548:
2545:
2542:
2537:
2534:
2531:
2527:
2506:
2499:
2495:
2489:
2485:
2477:
2473:
2468:
2462:
2459:
2456:
2451:
2448:
2445:
2441:
2433:
2430:
2427:
2423:
2419:
2416:
2413:
2408:
2404:
2399:
2393:
2390:
2385:
2382:
2379:
2375:
2369:
2366:
2361:
2358:
2355:
2351:
2346:
2342:
2337:
2334:
2329:
2325:
2319:
2316:
2311:
2307:
2302:
2298:
2291:
2288:
2285:
2281:
2277:
2274:
2271:
2266:
2262:
2251:
2223:
2219:
2213:
2209:
2203:
2200:
2197:
2192:
2189:
2186:
2182:
2171:
2164:
2157:
2154:
2151:
2147:
2143:
2140:
2137:
2132:
2128:
2117:
2089:
2085:
2079:
2075:
2069:
2066:
2063:
2058:
2055:
2052:
2048:
2043:
2039:
2032:
2029:
2026:
2022:
2018:
2015:
2012:
2007:
2003:
1998:
1977:
1967:
1961:
1952:
1944:
1940:
1932:
1928:
1923:
1917:
1914:
1911:
1906:
1903:
1900:
1896:
1888:
1884:
1878:
1874:
1868:
1865:
1862:
1857:
1854:
1851:
1847:
1842:
1836:
1833:
1828:
1825:
1822:
1818:
1812:
1809:
1804:
1801:
1798:
1794:
1789:
1785:
1780:
1777:
1772:
1768:
1762:
1759:
1754:
1750:
1745:
1741:
1731:
1725:
1716:
1705:
1699:
1690:
1680:
1676:
1671:
1665:
1662:
1659:
1654:
1651:
1648:
1644:
1638:
1634:
1628:
1625:
1622:
1617:
1614:
1611:
1607:
1603:
1598:
1595:
1590:
1582:
1578:
1573:
1567:
1564:
1561:
1556:
1553:
1550:
1546:
1541:
1534:
1530:
1524:
1521:
1518:
1513:
1510:
1507:
1503:
1499:
1494:
1491:
1486:
1482:
1476:
1472:
1466:
1463:
1460:
1455:
1452:
1449:
1445:
1441:
1436:
1426:
1398:
1394:
1364:
1360:
1356:
1349:
1345:
1339:
1336:
1333:
1328:
1325:
1322:
1318:
1312:
1308:
1304:
1297:
1293:
1288:
1282:
1279:
1276:
1271:
1268:
1265:
1261:
1236:
1232:
1226:
1222:
1218:
1211:
1207:
1202:
1177:
1173:
1165:
1162:
1157:
1153:
1147:
1144:
1141:
1136:
1133:
1130:
1126:
1117:
1099:
1095:
1072:
1068:
1062:
1058:
1052:
1049:
1046:
1041:
1038:
1035:
1031:
1019:
1015:
987:
983:
970:
967:
964:
959:
956:
953:
949:
926:
894:
888:
879:
870:
863:
845:
841:
835:
832:
829:
824:
821:
818:
814:
810:
807:
793:
791:
775:
751:
747:
742:
715:
711:
706:
693:
689:
664:
660:
630:
626:
620:
617:
614:
609:
606:
603:
599:
595:
592:
583:
565:
561:
533:
530:
527:
524:
521:
518:
515:
512:
509:
506:
503:
492:
489:
484:
480:
474:
470:
464:
461:
458:
453:
450:
447:
443:
439:
434:
424:
392:
387:
383:
376:
370:
362:
352:
325:
302:
296:
288:
274:
250:
246:
222:
216:
202:
200:
195:
190:
183:
179:
174:
172:
168:
165:
161:
157:
153:
146:
139:
132:
126:
122:
118:
114:
109:
107:
100:
93:
89:
82:
75:
71:
64:
57:
50:
44:
40:
36:
32:
28:
24:
16:
5225:
5221:
5204:
5200:
5183:
5179:
5166:
5150:
5147:
5133:
5129:
5107:
4209:
2769:
2596:
2240:, we have
1415:as follows:
1253:(therefore,
799:
584:
208:
196:
188:
181:
175:
170:
167:isomorphisms
160:power-of-two
151:
144:
137:
130:
124:
120:
112:
110:
98:
91:
80:
73:
69:
62:
55:
48:
42:
38:
26:
22:
20:
15:
3096:. Choosing
1194:. Choosing
1114:'s are the
113:mixed-radix
106:recursively
5146:Addendum,
5121:References
645:and turns
267:principal
5112:Good 1971
5051:φ
5001:φ
4972:φ
4828:generator
4791:↦
4623:∏
4553:∗
4549:η
4545:∘
4527:ω
4510:⨂
4506:∘
4499:η
4470:ω
4399:∏
4331:η
4309:∗
4305:η
4301:∘
4283:ω
4266:⨂
4262:∘
4255:η
4226:ω
4166:η
4143:∗
4139:η
4116:∗
4112:η
4108:∘
4090:ω
4073:⨂
4069:∘
4062:η
4047:ω
4016:⟩
4002:ω
3998:−
3992:⟨
3966:∏
3942:⟩
3914:ω
3910:−
3897:⟨
3857:∏
3847:⨂
3822:η
3798:⟩
3770:ω
3766:−
3753:⟨
3713:∏
3689:⟩
3683:−
3654:⟨
3602:ω
3586:and each
3571:⟩
3557:ω
3553:−
3547:⟨
3521:∏
3497:⟩
3491:−
3478:⟨
3433:ω
3399:⟩
3393:−
3368:⟨
3335:⨂
3331:≅
3325:⟩
3319:−
3306:⟨
3281:∗
3277:η
3231:⨂
3227:≅
3207:∗
3203:η
3166:∏
3162:≅
3113:↦
3104:η
3081:⟩
3075:−
3050:⟨
2967:⟩
2961:−
2948:⟨
2751:⨂
2706:⨂
2702:≅
2654:∏
2562:ω
2546:−
2528:⊗
2469:ω
2460:−
2442:∏
2431:−
2417:…
2391:−
2383:−
2359:−
2347:∑
2343:⋯
2335:−
2303:∑
2289:−
2275:…
2255:^
2201:−
2183:∑
2175:^
2155:−
2141:…
2121:^
2067:−
2049:∑
2030:−
2016:…
1924:ω
1915:−
1897:∏
1866:−
1848:∑
1834:−
1826:−
1802:−
1790:∑
1786:⋯
1778:−
1746:∑
1672:ω
1663:−
1645:∏
1626:−
1608:∑
1574:ω
1565:−
1547:∏
1522:−
1504:∑
1483:ω
1464:−
1446:∑
1430:^
1395:ω
1361:ω
1337:−
1319:∑
1309:ω
1289:ω
1280:−
1262:∏
1223:ω
1203:ω
1145:−
1127:∑
1050:−
1032:∑
1028:↦
968:−
950:∏
874:↦
833:−
815:∏
776:⨂
768:'s where
743:ω
707:ω
690:⨂
661:ω
618:−
600:∏
562:ω
531:−
522:…
481:ω
462:−
444:∑
428:^
384:ω
356:^
247:ω
205:Algorithm
68:DFT, but
5254:Category
5082:See also
4729:. Since
4502:′
4258:′
4169:′
4065:′
3825:′
5159:2984108
5142:2983896
5013:is the
788:is the
338:-tuple
318:as the
5242:585818
5240:
5157:
5140:
5043:where
4806:where
4778:cyclic
4130:where
2743:where
2621:and a
5238:S2CID
5155:JSTOR
5148:ibid.
5138:JSTOR
5099:Notes
4826:is a
4490:into
4343:from
4246:into
3838:from
2625:from
1118:with
1004:with
912:from
681:into
265:be a
4157:and
2982:and
2823:and
2106:and
209:Let
199:Good
143:and
97:and
86:are
79:and
70:only
21:The
5230:doi
5226:100
5209:doi
5188:doi
4830:of
4776:is
4682:on
4614:to
4521:DFT
4464:DFT
4390:to
4277:DFT
4220:DFT
4084:DFT
4041:DFT
3957:to
3704:to
3596:DFT
3512:to
3427:DFT
3124:mod
3018:as
2923:as
2890:be
2645:to
2556:DFT
1958:mod
1722:mod
1696:mod
1389:DFT
1174:mod
941:to
885:mod
701:DFT
655:DFT
556:DFT
187:by
152:any
5256::
5236:.
5224:.
5205:38
5203:.
5184:19
5182:.
5178:.
5151:22
5134:20
5132:.
4924:,
4202:.
2767:.
2589:.
792:.
582:.
534:1.
123:=
41:=
5244:.
5232::
5215:.
5211::
5194:.
5190::
5161:.
5144:.
5066:2
5063:=
5060:)
5057:n
5054:(
5031:6
5028:=
5025:n
4981:)
4978:n
4975:(
4952:n
4932:g
4912:)
4909:0
4906:,
4903:+
4900:,
4895:n
4890:Z
4885:(
4865:)
4862:0
4859:,
4856:+
4853:,
4848:n
4843:Z
4838:(
4814:g
4794:g
4788:1
4764:)
4761:0
4758:,
4755:+
4752:,
4747:n
4742:Z
4737:(
4717:)
4714:0
4711:,
4708:+
4705:,
4700:n
4695:Z
4690:(
4666:)
4663:0
4660:,
4657:+
4654:,
4647:d
4643:n
4637:Z
4632:(
4627:d
4602:)
4599:0
4596:,
4593:+
4590:,
4585:n
4580:Z
4575:(
4536:d
4532:n
4514:d
4474:n
4442:)
4439:0
4436:,
4433:+
4430:,
4423:d
4419:n
4413:Z
4408:(
4403:d
4378:)
4375:0
4372:,
4369:+
4366:,
4361:n
4356:Z
4351:(
4292:d
4288:n
4270:d
4230:n
4190:R
4099:d
4095:n
4077:d
4058:=
4051:n
4011:i
4006:n
3995:x
3987:]
3984:x
3981:[
3978:R
3970:i
3935:d
3931:i
3923:d
3919:n
3905:d
3901:x
3892:]
3887:d
3883:x
3879:[
3876:R
3866:d
3862:i
3851:d
3791:d
3787:i
3779:d
3775:n
3761:d
3757:x
3748:]
3743:d
3739:x
3735:[
3732:R
3722:d
3718:i
3686:1
3676:d
3672:n
3664:d
3660:x
3649:]
3646:x
3643:[
3640:R
3611:d
3607:n
3566:i
3561:n
3550:x
3542:]
3539:x
3536:[
3533:R
3525:i
3494:1
3486:n
3482:x
3473:]
3470:x
3467:[
3464:R
3437:n
3405:.
3396:1
3386:d
3382:n
3376:d
3372:x
3363:]
3358:d
3354:x
3350:[
3347:R
3339:d
3322:1
3314:n
3310:x
3301:]
3298:x
3295:[
3292:R
3286::
3256:]
3251:d
3247:G
3243:[
3240:R
3235:d
3224:]
3221:G
3218:[
3215:R
3212::
3180:d
3176:G
3170:d
3159:G
3139:)
3134:d
3128:n
3119:a
3116:(
3110:a
3107:=
3078:1
3068:d
3064:n
3058:d
3054:x
3045:]
3040:d
3036:x
3032:[
3029:R
3006:]
3001:d
2997:G
2993:[
2990:R
2964:1
2956:n
2952:x
2943:]
2940:x
2937:[
2934:R
2911:]
2908:G
2905:[
2902:R
2878:)
2875:0
2872:,
2869:+
2866:,
2859:d
2855:n
2849:Z
2844:(
2841:=
2836:d
2832:G
2811:)
2808:0
2805:,
2802:+
2799:,
2794:n
2789:Z
2784:(
2781:=
2778:G
2731:]
2726:d
2722:G
2718:[
2715:R
2710:d
2699:]
2696:G
2693:[
2690:R
2668:d
2664:G
2658:d
2633:G
2609:R
2571:d
2567:n
2549:1
2543:D
2538:0
2535:=
2532:d
2507:.
2500:d
2496:j
2490:d
2486:i
2478:d
2474:n
2463:1
2457:D
2452:0
2449:=
2446:d
2434:1
2428:D
2424:i
2420:,
2414:,
2409:0
2405:i
2400:a
2394:1
2386:1
2380:D
2376:n
2370:0
2367:=
2362:1
2356:D
2352:i
2338:1
2330:0
2326:n
2320:0
2317:=
2312:0
2308:i
2299:=
2292:1
2286:D
2282:j
2278:,
2272:,
2267:0
2263:j
2252:a
2224:d
2220:e
2214:d
2210:j
2204:1
2198:D
2193:0
2190:=
2187:d
2172:a
2165:=
2158:1
2152:D
2148:j
2144:,
2138:,
2133:0
2129:j
2118:a
2090:d
2086:e
2080:d
2076:i
2070:1
2064:D
2059:0
2056:=
2053:d
2044:a
2040:=
2033:1
2027:D
2023:i
2019:,
2013:,
2008:0
2004:i
1999:a
1978:.
1973:)
1968:d
1962:n
1953:j
1950:(
1945:d
1941:i
1933:d
1929:n
1918:1
1912:D
1907:0
1904:=
1901:d
1889:d
1885:i
1879:d
1875:e
1869:1
1863:D
1858:0
1855:=
1852:d
1843:a
1837:1
1829:1
1823:D
1819:n
1813:0
1810:=
1805:1
1799:D
1795:i
1781:1
1773:0
1769:n
1763:0
1760:=
1755:0
1751:i
1742:=
1737:)
1732:d
1726:n
1717:j
1714:(
1711:)
1706:d
1700:n
1691:i
1688:(
1681:d
1677:n
1666:1
1660:D
1655:0
1652:=
1649:d
1639:i
1635:a
1629:1
1623:n
1618:0
1615:=
1612:i
1604:=
1599:j
1596:i
1591:)
1583:d
1579:n
1568:1
1562:D
1557:0
1554:=
1551:d
1542:(
1535:i
1531:a
1525:1
1519:n
1514:0
1511:=
1508:i
1500:=
1495:j
1492:i
1487:n
1477:i
1473:a
1467:1
1461:n
1456:0
1453:=
1450:i
1442:=
1437:j
1427:a
1399:n
1365:n
1357:=
1350:d
1346:e
1340:1
1334:D
1329:0
1326:=
1323:d
1313:n
1305:=
1298:d
1294:n
1283:1
1277:D
1272:0
1269:=
1266:d
1237:d
1233:e
1227:n
1219:=
1212:d
1208:n
1181:)
1178:n
1171:(
1166:1
1163:=
1158:d
1154:e
1148:1
1142:D
1137:0
1134:=
1131:d
1100:d
1096:e
1073:d
1069:m
1063:d
1059:e
1053:1
1047:D
1042:0
1039:=
1036:d
1025:)
1020:d
1016:m
1012:(
988:d
984:n
978:Z
971:1
965:D
960:0
957:=
954:d
927:n
922:Z
900:)
895:d
889:n
880:m
877:(
871:m
846:d
842:n
836:1
830:D
825:0
822:=
819:d
811:=
808:n
752:d
748:n
716:d
712:n
694:d
665:n
631:d
627:n
621:1
615:D
610:0
607:=
604:d
596:=
593:n
566:n
528:n
525:,
519:,
516:1
513:,
510:0
507:=
504:j
493:j
490:i
485:n
475:i
471:a
465:1
459:n
454:0
451:=
448:i
440:=
435:j
425:a
401:)
398:)
393:j
388:n
380:(
377:a
374:(
371:=
368:)
363:j
353:a
346:(
326:n
306:)
303:x
300:(
297:a
275:n
251:n
226:)
223:x
220:(
217:a
192:2
189:N
185:1
182:N
171:N
148:2
145:N
141:1
138:N
134:2
131:N
128:1
125:N
121:N
102:2
99:N
95:1
92:N
84:2
81:N
77:1
74:N
66:2
63:N
61:Ă—
59:1
56:N
52:2
49:N
46:1
43:N
39:N
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
