mersenneforum.org Multiplication in cyclotomic rings
 User Name Remember Me? Password
 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

22×5×373 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.

 Thread Tools

 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 17:44.

Fri Apr 16 17:44:55 UTC 2021 up 8 days, 12:25, 0 users, load averages: 3.23, 3.37, 3.33

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.