20171103, 06:36  #1 
"Sam"
Nov 2016
5×67 Posts 
Modular Exponentiation results in PFGW
Long story short, I am working with PARI/GP to explore and discover more about cyclotmic field extensions as described here.
Here, polcyclo(n) is the nth cyclotomic polynomial. Code:
J = idealhnf(bnfinit(polcyclo(n)),p,xw); idealnorm(bnfinit(polcyclo(n)),J) Jp = bnfisprincipal(bnfinit(polcyclo(n)),J) u = nfbasistoalg(bnfinit(polcyclo(n)),Jp[2]) norm(u) Code:
(22:40) gp > J = idealhnf(bnfinit(polcyclo(5)),11,x3); (22:40) gp > idealnorm(bnfinit(polcyclo(5)),J) %402 = 11 (22:40) gp > Jp = bnfisprincipal(bnfinit(polcyclo(5)),J) %403 = [[]~, [1, 1, 1, 0]~] (22:40) gp > u = nfbasistoalg(bnfinit(polcyclo(5)),Jp[2]) %404 = Mod(x^2  x + 1, x^4 + x^3 + x^2 + x + 1) (22:40) gp > norm(u) %405 = 11 (22:40) gp > Code:
w = Mod(x,f=polcyclo(n));bnf = bnfinit(f); uu = bnfisintnorm(bnf,p); #uu Code:
(22:48) gp > w = Mod(x,f=polcyclo(5));bnf = bnfinit(f); (22:48) gp > uu = bnfisintnorm(bnf,11); #uu %407 = 4 In the field Kn, if there are no principal ideals of norm p, then its principal generators are of the form a/b. Here b is any prime q = 1 (mod n), or a product of prime factors congruent to 1 (mod n). Let b be a perfect kth power (This will be important later, look at ***). The resulting polynomial P(x) in Mod(P(x),polcyclo(n) will have terms of the form a/b*x^n where a, b, n are all integers. If we were to get rid of the "/b" part in P(x), we would have a polynomial Q(x) with integer coefficients, and terms of the form a*x^n, where a, n are integers. (***) If u = Mod(Q(x),polcyclo(n)), then the norm of u is p*b^(n*k2*k). To come up with all elements of norm p*b^(n*k2*k), we can refer to this code, Code:
w = Mod(x,f=polcyclo(n));bnf = bnfinit(f); uu = bnfisintnorm(bnf,p); #uu Here we can use: Code:
J = idealhnf(bnfinit(polcyclo(n)),p*b^(n*k2*k),xw); idealnorm(bnfinit(polcyclo(n)),J) Jp = bnfisprincipal(bnfinit(polcyclo(n)),J) u = nfbasistoalg(bnfinit(polcyclo(n)),Jp[2]) norm(u) c^(phi(D)/n) (mod D) = w This may seem like an easy task, but it is not. Let us work with polcyclo(23), n = 23, K23. Here we choose p = 139, which is nonprincipal, b = 461, k = 2, and base c = 3. In order to find w and solve this problem, we need to compute, 3^(phi(139*461^(23*22*2))/23) (mod 139*461^(23*22*2)) = w 3^(2760*461^41) (mod 139*461^42) = w I tried running it into PFGW using % to represent modulo, and attempted to compute 3^(2760*461^41) (mod 139*461^42) Code:
C:\Users\Documents\PFGW\PFGW>pfgw64.exe code.txt PFGW Version 3.8.3.64BIT.20161203.Win_Dev [GWNUM 28.6] ***WARNING! file code.txt may have already been fully processed. 3^(2760*461^41)%(139*461^42)  Evaluator failed C:\Users\Documents\PFGW\PFGW> 
20171103, 06:56  #2  
Sep 2002
Database er0rr
1000010011100_{2} Posts 
Quote:
Code:
? Mod(3,139*461^42)^(2760*461^41) Mod(1, 1043406809315900616956999799105701752849906128374948710828030894314678039911009065037910659790911409501482999082019) 

20171103, 07:24  #3  
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
9,901 Posts 
Quote:
You can't do that for any sufficiently large (which is really quite small) number. You will run out of atoms in the universe to hold your intermediate result. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Question on modular exponentiation?  ramshanker  Math  2  20151031 15:28 
Modular question :)  LaurV  Homework Help  7  20120516 16:52 
PFGW 3.3.6 or PFGW 3.4.2 Please update now!  Joe O  Sierpinski/Riesel Base 5  5  20100930 14:07 
Exponentiation w/ independent variable  Unregistered  Homework Help  4  20100804 06:38 
optimum multiple exponentiation 'problem'  Greenbank  Math  5  20050930 10:20 