Modular Exponentiation results in PFGW

[carpetpool]

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.

J = idealhnf(bnfinit(polcyclo(n)),p,x-w);
idealnorm(bnfinit(polcyclo(n)),J)
Jp = bnfisprincipal(bnfinit(polcyclo(n)),J)
u = nfbasistoalg(bnfinit(polcyclo(n)),Jp[2])
norm(u)

The following code above computes the norm of an ideal in the cyclotomic field Kn, and finds an element (if any) with norm p in Kn. If p is principal, then its principal generators are integers. For example, the principal generators (as shown below) for p = 11 are [1, -1, -1, 0].

(22:40) gp > J = idealhnf(bnfinit(polcyclo(5)),11,x-3);
(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 >

The code

w = Mod(x,f=polcyclo(n));bnf = bnfinit(f);
uu = bnfisintnorm(bnf,p); #uu

Gives all such elements or principal generators of norm p, if they exist. (All of these code assumes p is a prime congruent to 1 (mod n), FYI.)

(22:48) gp > w = Mod(x,f=polcyclo(5));bnf = bnfinit(f);
(22:48) gp > uu = bnfisintnorm(bnf,11); #uu
%407 = 4

Now on the other hand, if the class number of Kn is greater than 1, we will have some primes p which are not norms of principal ideals. In this case, p will still have principal generators, but they will be non-integer fractions. The polynomial (at the third step of the first code) will be a polynomial with terms of the form a/b*x^n, not a*x^n.

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*k-2*k).

To come up with all elements of norm p*b^(n*k-2*k), we can refer to this code,

w = Mod(x,f=polcyclo(n));bnf = bnfinit(f);
uu = bnfisintnorm(bnf,p); #uu

but when n and k become really large, the code for finding all such elements will no longer work, however, generating the norm of an ideal, then coming up with principal generators for it is easier.

Here we can use:

J = idealhnf(bnfinit(polcyclo(n)),p*b^(n*k-2*k),x-w);
idealnorm(bnfinit(polcyclo(n)),J)
Jp = bnfisprincipal(bnfinit(polcyclo(n)),J)
u = nfbasistoalg(bnfinit(polcyclo(n)),Jp[2])
norm(u)

The ideal norm of J = idealhnf(bnfinit(polcyclo(n)),p*b^(n*k-2*k),x-w) is p*b^(n*k-2*k) if and only if w^n-1 divides (D = p*b^(n*k-2*k)) and w is not 1 (mod D). We can find w simply by choosing a base c, and computing

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 non-principal, 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*2-2*2))/23) (mod 139*461^(23*2-2*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)

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>

I know PFGW is much more capable of doing this, because it can compute these type of work for base 3-PRP tests, and other bases as well, for numbers thousands of digits long. This is not even near that size. Can someone please look into this and figure out how to compute these modular exponentiation results exactly? Thank you for your help.

[paulunderwood]

Originally Posted by carpetpool

I tried running it into PFGW using % to represent modulo, and attempted to compute 3^(2760*461^41) (mod 139*461^42)

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>

I know PFGW is much more capable of doing this, because it can compute these type of work for base 3-PRP tests, and other bases as well, for numbers thousands of digits long. This is not even near that size. Can someone please look into this and figure out how to compute these modular exponentiation results exactly? Thank you for your help.

? Mod(3,139*461^42)^(2760*461^41)
Mod(1, 1043406809315900616956999799105701752849906128374948710828030894314678039911009065037910659790911409501482999082019)

[Batalov]

Originally Posted by carpetpool

Long story short, ...
I tried running it into PFGW using % to represent modulo, and attempted to compute 3^(2760*461^41) (mod 139*461^42)

C:\Users\Documents\PFGW\PFGW>pfgw64.exe code.txt

3^(2760*461^41)%(139*461^42) - Evaluator failed

I know PFGW is much more capable of doing this, ...

Trying to compute 3^(2760*461^41)%(139*461^42) is like trying to do Lucas test by plain squaring ...and only take %(2^p-1) at the very end.

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.