84:
74:
53:
22:
406:
I was doing an experiment and when I computed IDFT(DFT()) in the integers mod 85 using 2 as my primitive 8th root mod 85, the result is , not as expected (and 8 has an inverse mod 85, 32). Eventually I figured out the problem: 2=16, and 16-1 = 15 is not invertible mod 85, so you can't divide by β-1
440:
is invertible for all 0 < k < n (I'm uncertain if this condition is necessary). This obviously applies with prime moduli, but I haven't figured out if it applies with Fermat/Mersenne numbers. Am I correct, and if so, where should I find a reference to back this up? Thanks!
190:
is primarily over the complex numbers (although other fields are briefly mentioned). I think this should stay as it is, because most people who need the DFT only need the complex case, the the added generality of field theory would benefit very few people.
248:
For the number theoretic transform to work in a useful way when the modulus is composite (for the inverse algorithm, convolution etc. to work), it suffices that the modulus is chosen so that a primitive root of order
140:
438:
400:
469:
367:
327:
203:
be merged into this (actually, it should be deleted and redirected here). That page is already in bad shape, and the content is entirely subsumed by this new article.
347:
307:
287:
267:
507:
451:
I found a source and fixed this by generalising the entire article to discuss rings rather than fields. The desired condition to make this work was that
130:
502:
106:
97:
58:
192:
158:
33:
221:
200:
187:
179:
somewhere we need a description of the discrete
Fourier transform over any field. This is used, for example, in
21:
39:
479:
445:
233:
214:
170:
83:
206:
162:
410:
372:
105:
on
Knowledge. If you would like to participate, please visit the project page, where you can join
210:
166:
89:
73:
52:
180:
157:
The article "Number-theoretic transform" has been merged into this article: See old talk-page
454:
352:
312:
229:
332:
292:
272:
252:
496:
476:
442:
225:
102:
79:
289:
is the transform length), and such that the multiplicative inverse of
15:
195:
already contains complaints that the content is too abstract.
240:
Requirements for convolution theorem with composite moduli
457:
413:
375:
355:
335:
315:
295:
275:
255:
101:, a collaborative effort to improve the coverage of
463:
432:
407:in the proof. So a sufficient condition would be:
394:
361:
341:
321:
301:
281:
261:
490:Final line: what is q? Should be subscripted p?
224:(suggested for two years with no complaints). --
175:Here is my rationale for creating this article:
199:I also propose that the existing page on the
8:
19:
47:
456:
418:
412:
380:
374:
369:is automatically invertible with inverse
354:
334:
314:
294:
274:
254:
49:
7:
95:This article is within the scope of
38:It is of interest to the following
14:
508:Mid-priority mathematics articles
186:the existing main article on the
115:Knowledge:WikiProject Mathematics
503:Start-Class mathematics articles
118:Template:WikiProject Mathematics
82:
72:
51:
20:
193:Talk:discrete Fourier transform
135:This article has been rated as
486:Typo in polynomial formulation
1:
480:05:43, 22 December 2011 (UTC)
446:06:53, 14 December 2011 (UTC)
433:{\displaystyle \alpha ^{k}-1}
395:{\displaystyle \alpha ^{n-1}}
329:is a primitive root of order
234:06:47, 21 December 2011 (UTC)
220:I have merged in the page on
109:and see a list of open tasks.
222:Discrete weighted transform
524:
244:Regarding this statement:
215:23:50, 14 March 2008 (UTC)
201:number theoretic transform
188:discrete Fourier transform
171:01:58, 24 June 2011 (UTC)
134:
67:
46:
141:project's priority scale
464:{\displaystyle \alpha }
362:{\displaystyle \alpha }
322:{\displaystyle \alpha }
98:WikiProject Mathematics
465:
434:
396:
363:
343:
323:
303:
283:
263:
28:This article is rated
466:
435:
397:
364:
344:
324:
309:exists. Note that if
304:
284:
264:
455:
411:
373:
353:
333:
313:
293:
273:
253:
121:mathematics articles
475:th root of unity.
461:
430:
392:
359:
339:
319:
299:
279:
259:
181:Reed-Solomon codes
90:Mathematics portal
34:content assessment
342:{\displaystyle n}
302:{\displaystyle n}
282:{\displaystyle n}
262:{\displaystyle n}
155:
154:
151:
150:
147:
146:
515:
470:
468:
467:
462:
439:
437:
436:
431:
423:
422:
401:
399:
398:
393:
391:
390:
368:
366:
365:
360:
348:
346:
345:
340:
328:
326:
325:
320:
308:
306:
305:
300:
288:
286:
285:
280:
268:
266:
265:
260:
123:
122:
119:
116:
113:
92:
87:
86:
76:
69:
68:
63:
55:
48:
31:
25:
24:
16:
523:
522:
518:
517:
516:
514:
513:
512:
493:
492:
488:
471:is a principal
453:
452:
414:
409:
408:
376:
371:
370:
351:
350:
331:
330:
311:
310:
291:
290:
271:
270:
251:
250:
242:
120:
117:
114:
111:
110:
88:
81:
61:
32:on Knowledge's
29:
12:
11:
5:
521:
519:
511:
510:
505:
495:
494:
487:
484:
483:
482:
460:
429:
426:
421:
417:
404:
403:
389:
386:
383:
379:
358:
338:
318:
298:
278:
269:exists (where
258:
241:
238:
237:
236:
197:
196:
184:
153:
152:
149:
148:
145:
144:
133:
127:
126:
124:
107:the discussion
94:
93:
77:
65:
64:
56:
44:
43:
37:
26:
13:
10:
9:
6:
4:
3:
2:
520:
509:
506:
504:
501:
500:
498:
491:
485:
481:
478:
474:
458:
450:
449:
448:
447:
444:
427:
424:
419:
415:
387:
384:
381:
377:
356:
336:
316:
296:
276:
256:
247:
246:
245:
239:
235:
231:
227:
223:
219:
218:
217:
216:
212:
208:
204:
202:
194:
189:
185:
182:
178:
177:
176:
173:
172:
168:
164:
160:
142:
138:
132:
129:
128:
125:
108:
104:
100:
99:
91:
85:
80:
78:
75:
71:
70:
66:
60:
57:
54:
50:
45:
41:
35:
27:
23:
18:
17:
489:
472:
405:
243:
205:
198:
174:
156:
137:Mid-priority
136:
96:
62:Mid‑priority
40:WikiProjects
112:Mathematics
103:mathematics
59:Mathematics
30:Start-class
497:Categories
477:Dcoetzee
443:Dcoetzee
207:Selinger
163:Selinger
349:, then
139:on the
226:Qetuth
36:scale.
230:talk
211:talk
167:talk
159:here
131:Mid
499::
459:α
425:−
416:α
385:−
378:α
357:α
317:α
232:)
213:)
169:)
161:.
473:n
428:1
420:k
402:.
388:1
382:n
337:n
297:n
277:n
257:n
228:(
209:(
183:.
165:(
143:.
42::
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
