mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Factoring (https://www.mersenneforum.org/forumdisplay.php?f=19)
-   -   Check my arithmetic (https://www.mersenneforum.org/showthread.php?t=5963)

R.D. Silverman 2006-06-05 18:46

Check my arithmetic
 
I derived (by hand) the following polynomial for N = 2,1526L/2,218L =

2^654 + 2^600 + 2^545 - 2^436 - 2^382 - 2^327 - 2^273 - 2^218 - 2^109
+ 2^55 + 1

The polynomial is: f(x) =

x^6 + 2x^5 - 10x^4 - 20x^3 + 16x^2 - 48x + 72 with root
2^55 + 2^-54.

This polynomial sends (2z + 1/z) to (64z^12 + 64z^11 + 32z^10 - 16z^8
-16z^7 - 8z^6 - 8z^5 - 4z^4 + 2z^2 + 2z + 1)/z^6

The 12'th degree polynomial is equal to 2,1526L/2,218L with z = 2^54
(or should be if I did the arithmetic correctly)

Would someone with access to Maple/Mathematica please check this?
It was tedious to do by hand. i.e. please verify that f(2z + 1/z) equals
the 12th degree polynomial divided by z^6.

R. Gerbicz 2006-06-05 20:25

[QUOTE=R.D. Silverman]
It was tedious to do by hand. i.e. please verify that f(2z + 1/z) equals
the 12th degree polynomial divided by z^6.[/QUOTE]

Using Pari-Gp I've gotten:

(22:20) gp > f(x)=x^6+2*x^5-10*x^4-20*x^3+16*x^2-48*x+72
(22:20) gp > substpol(f(x),x,2*z+1/z)
%7 = (64*z^12 + 64*z^11 + 32*z^10 - 16*z^8 - 176*z^7 + 56*z^6 - 8*z^5 - 4*z^4 + 2*z^2 + 2*z + 1)/z^6
(22:20) gp >

So there are errors in your polynom.

R. Gerbicz 2006-06-05 21:19

There was also an error in N:

N=2,1526L/2,218L=2^654+2^600+2^545-2^436-2^382-2^327-2^273-2^218+2^109+2^55+1

I think the correct polynom ( I've found this by hand ) is the following: (checking this by Pari-Gp ):

(23:15) gp > f(x)=x^6+2*x^5-10*x^4-20*x^3+16*x^2+32*x+8
(23:15) gp > g(z)=substpol(f(x),x,2*z+1/z)
%4 = (64*z^12 + 64*z^11 + 32*z^10 - 16*z^8 - 16*z^7 - 8*z^6 - 8*z^5 - 4*z^4 + 2*z^2 + 2*z + 1)/z^6
(23:15) gp >

Further checking to see that g(z) has a root of 2^54 modulo N:

(23:28) gp > lift(g(Mod(2^54,N)))
%13 = 0
(23:28) gp >

R.D. Silverman 2006-06-05 23:49

[QUOTE=R. Gerbicz]There was also an error in N:

N=2,1526L/2,218L=2^654+2^600+2^545-2^436-2^382-2^327-2^273-2^218+2^109+2^55+1

I think the correct polynom ( I've found this by hand ) is the following: (checking this by Pari-Gp ):

(23:15) gp > f(x)=x^6+2*x^5-10*x^4-20*x^3+16*x^2+32*x+8
(23:15) gp > g(z)=substpol(f(x),x,2*z+1/z)
%4 = (64*z^12 + 64*z^11 + 32*z^10 - 16*z^8 - 16*z^7 - 8*z^6 - 8*z^5 - 4*z^4 + 2*z^2 + 2*z + 1)/z^6
(23:15) gp >

Further checking to see that g(z) has a root of 2^54 modulo N:

(23:28) gp > lift(g(Mod(2^54,N)))
%13 = 0
(23:28) gp >[/QUOTE]

I got the coefficient of x wrong, and that led to an incorrect constant as
well

Thanks.


All times are UTC. The time now is 01:07.

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