mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Programming

Reply
 
Thread Tools
Old 2009-01-23, 10:05   #1
wpolly
 
wpolly's Avatar
 
Sep 2002
Vienna, Austria

3·73 Posts
Default 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?
wpolly is offline   Reply With Quote
Old 2009-01-23, 22:08   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by wpolly View Post
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.
R.D. Silverman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Basic Number Theory 19: Introducing rings and fields Nick Number Theory Discussion Group 0 2017-04-11 18:37
Cyclotomic primes (degree>=5) Batalov And now for something completely different 0 2016-06-21 21:02
Cyclotomic Polynomial Factoring methods mickfrancis Factoring 2 2015-01-11 18:31
Discrete Ordered Rings? jinydu Abstract Algebra & Algebraic Number Theory 2 2013-11-25 09:08
Cyclotomic Phi plandon Math 22 2009-07-29 18:59

All times are UTC. The time now is 08:27.

Sun May 9 08:27:52 UTC 2021 up 31 days, 3:08, 0 users, load averages: 2.40, 2.58, 2.71

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.