mersenneforum.org Multiplication in cyclotomic rings
 Register FAQ Search Today's Posts Mark Forums Read

 2009-01-23, 10:05 #1 wpolly     Sep 2002 Vienna, Austria 3×73 Posts Multiplication in cyclotomic rings I am working on an implementation of the APR-CL algorithm, and encountered the problem of efficient multiplication in $Z[\zeta_{p^k}]$. The original paper of Cohen and Lenstra only gives the cases $p^k=3,4,5,7,8,11,16$. Is there any general method to construct an multiplication algorithm which takes $O(p^k)$ integer-multiplies?
2009-01-23, 22:08   #2
R.D. Silverman

Nov 2003

746010 Posts

Quote:
 Originally Posted by wpolly I am working on an implementation of the APR-CL algorithm, and encountered the problem of efficient multiplication in $Z[\zeta_{p^k}]$. The original paper of Cohen and Lenstra only gives the cases $p^k=3,4,5,7,8,11,16$. Is there any general method to construct an multiplication algorithm which takes $O(p^k)$ integer-multiplies?
AFAIK, it is like FFT schemes for non powers of two length; Each multiplication
scheme gets specially constructed. Wieb Bosma's dissertation is a good
source of information on this subject. When I did my implementation many
years ago, I added k = 9, 17, 18, and 25, but I worked out the schemes
using a lot of trial-and-error and a lot of help from a CAS.

 Similar Threads Thread Thread Starter Forum Replies Last Post Nick Number Theory Discussion Group 0 2017-04-11 18:37 Batalov And now for something completely different 0 2016-06-21 21:02 mickfrancis Factoring 2 2015-01-11 18:31 jinydu Abstract Algebra & Algebraic Number Theory 2 2013-11-25 09:08 plandon Math 22 2009-07-29 18:59

All times are UTC. The time now is 18:41.

Tue Apr 13 18:41:49 UTC 2021 up 5 days, 13:22, 1 user, load averages: 3.77, 4.22, 4.56