mersenneforum.org  

Go Back   mersenneforum.org > New To GIMPS? Start Here! > Information & Answers

Reply
 
Thread Tools
Old 2017-11-03, 06:36   #1
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

32410 Posts
Post 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,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].

Code:
(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

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.)

Code:
(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,

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:

Code:
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)

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>
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.
carpetpool is offline   Reply With Quote
Old 2017-11-03, 06:56   #2
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2·1,879 Posts
Default

Quote:
Originally Posted by carpetpool View Post

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>
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.
Code:
? Mod(3,139*461^42)^(2760*461^41)
Mod(1, 1043406809315900616956999799105701752849906128374948710828030894314678039911009065037910659790911409501482999082019)
paulunderwood is offline   Reply With Quote
Old 2017-11-03, 07:24   #3
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

224268 Posts
Default

Quote:
Originally Posted by carpetpool View Post
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)

Code:
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.
Batalov is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Question on modular exponentiation? ramshanker Math 2 2015-10-31 15:28
Modular question :) LaurV Homework Help 7 2012-05-16 16:52
PFGW 3.3.6 or PFGW 3.4.2 Please update now! Joe O Sierpinski/Riesel Base 5 5 2010-09-30 14:07
Exponentiation w/ independent variable Unregistered Homework Help 4 2010-08-04 06:38
optimum multiple exponentiation 'problem' Greenbank Math 5 2005-09-30 10:20

All times are UTC. The time now is 18:46.


Sat Jul 31 18:46:39 UTC 2021 up 8 days, 13:15, 0 users, load averages: 3.47, 3.08, 2.69

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.