20100612, 17:03  #1 
Dec 2008
Boycotting the Soapbox
2^{4}×3^{2}×5 Posts 
parigp and trigonometry in Galois fields
Is there a straightforward way to compute roots modulo p^2 with parigp?
Specifically, if p=2^1071, 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. 
20100612, 20:09  #2  
Dec 2008
Boycotting the Soapbox
2^{4}×3^{2}×5 Posts 
Quote:
Code:
Mod(127316999246511176001337524256693, 162259276829213363391578010288127) + Mod(100755747211248383624389262455139, 162259276829213363391578010288127)*I 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] 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] I looked at some of the 'karatsubized' results div/mod 2^57 and 2^58 but everything remained messy. Apparently a 2/8 splitradix is the best we can get. 

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