pari-gp and trigonometry in Galois fields

__HRB__ · 2010-06-12, 17:03

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.

__HRB__ · 2010-06-12, 20:09

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.

2010-06-12, 17:03	#1
__HRB__ Dec 2008 Boycotting the Soapbox 2D0₁₆ 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.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Cyclic fields with class number h	carpetpool	Abstract Algebra & Algebraic Number Theory	0	2018-01-30 06:10
Ideal groupings in number fields	carpetpool	Abstract Algebra & Algebraic Number Theory	3	2018-01-13 18:13
Pseudoprimes in special fields	devarajkandadai	Number Theory Discussion Group	7	2017-12-06 01:46
Questions about Number Fields	Raman	Miscellaneous Math	5	2013-06-12 13:54
On the basis of finite fields	meng_luckywolf	Math	6	2007-12-13 04:21