gcd computation of two polynomial

the following code for gcd computation for two polynomials . the code for 112-bit elliptic curve but as the polynomials are two large it is difficult to compute gcd. the codes are given below. what is the solution for large polynomials.

p=0xDB7C2ABF62E35E668076BEAD208B  #Secp112r1 Elliptic curve;
F = GF(p);
S.<a> = PolynomialRing( F );
K.<a>=GF(p^2);#K.modulus();
R.<z> = PolynomialRing( K, sparse=True );
print'hi'
fE=(1978526766708317676482043677132634*a + 989263383354158838241021838566317)*z^13355055675281144316253794820645281 + (2967790150062476514723065515698951*a + 1483895075031238257361532757849475)*z^8903370450187429544169196547096855 + 2967790150062476514723065515698951*z^8903370450187429544169196547096854 + (1483895075031238257361532757849476*a + 2967790150062476514723065515698951)*z^4451685225093714772084598273548429 + 2967790150062476514723065515698952*z^4451685225093714772084598273548428 + (a + 2)*z^4451685225093714772084598273548427 + (2473158458385397095602554596415793*a + 3462421841739555933843576434982110)*z^3 + 2967790150062476514723065515698951*z^2 + (4451685225093714772084598273548426*a + 1)*z + 2390566828285061569181602107159913

Phi10=z^2477187667914709744689409953417368724452959475301832810429239271791 + 4451685225093714772084598273548426

x10=gcd(fE,Phi10);print"\n gcd(fE,Phi10) x10=",x10

edit retag close merge delete

Sort by » oldest newest most voted

I do not know whether there is a good solution. Actually, the problem you are trying to solve is NP-hard so there is probably no efficient algorithm. (Note that of course computing the GCD of two dense (or low-degree) polynomials in not hard, the problem here is the degree. )

more