mersenneforum.org > Math pari-gp and trigonometry in Galois fields
 Register FAQ Search Today's Posts Mark Forums Read

 2010-06-12, 17:03 #1 __HRB__     Dec 2008 Boycotting the Soapbox 2D016 Posts pari-gp and trigonometry in Galois fields Is there a straightforward way to compute roots modulo p^2 with pari-gp? Specifically, if p=2^107-1, then 4th roots of unity are free, 8th roots are computationally cheap (i.e. +/-2^53 +/- i*2^53, which can be done with rotate/add/sub), so the question is whether 16th roots have an exploitable special structure, too.
2010-06-12, 20:09   #2
__HRB__

Dec 2008
Boycotting the Soapbox

24·32·5 Posts

Quote:
 Originally Posted by __HRB__ Is there a straightforward way to compute roots modulo p^2 with pari-gp? Specifically, if p=2^107-1, then 4th roots of unity are free, 8th roots are computationally cheap (i.e. +/-2^53 +/- i*2^53, which can be done with rotate/add/sub), so the question is whether 16th roots have an exploitable special structure, too.
After some fudging I managed to find:

Code:
Mod(127316999246511176001337524256693, 162259276829213363391578010288127) + Mod(100755747211248383624389262455139, 162259276829213363391578010288127)*I
Which is:

Code:
[1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1,  0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1,  0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1,  1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1,  1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1]
for the real part and

Code:
[1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1]
for the imaginary part. It's a mess!

I looked at some of the 'karatsubized' results div/mod 2^57 and 2^58 but everything remained messy. Apparently a 2/8 split-radix is the best we can get.

 Similar Threads Thread Thread Starter Forum Replies Last Post carpetpool Abstract Algebra & Algebraic Number Theory 0 2018-01-30 06:10 carpetpool Abstract Algebra & Algebraic Number Theory 3 2018-01-13 18:13 devarajkandadai Number Theory Discussion Group 7 2017-12-06 01:46 Raman Miscellaneous Math 5 2013-06-12 13:54 meng_luckywolf Math 6 2007-12-13 04:21

All times are UTC. The time now is 14:32.

Mon Jun 27 14:32:52 UTC 2022 up 74 days, 12:34, 2 users, load averages: 1.68, 1.27, 1.13