Revision history [back]

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. = PolynomialRing( F ); K.=GF(p^2);#K.modulus(); R.<z> = PolynomialRing( K, sparse=True ); print'hi' fE=(1978526766708317676482043677132634a + 989263383354158838241021838566317)z^13355055675281144316253794820645281 + (2967790150062476514723065515698951a + 1483895075031238257361532757849475)z^8903370450187429544169196547096855 + 2967790150062476514723065515698951z^8903370450187429544169196547096854 + (1483895075031238257361532757849476a + 2967790150062476514723065515698951)z^4451685225093714772084598273548429 + 2967790150062476514723065515698952z^4451685225093714772084598273548428 + (a + 2)z^4451685225093714772084598273548427 + (2473158458385397095602554596415793a + 3462421841739555933843576434982110)z^3 + 2967790150062476514723065515698951z^2 + (4451685225093714772084598273548426a + 1)z + 2390566828285061569181602107159913

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. S.<a> = PolynomialRing( F );
K.=GF(p^2);#K.modulus();
K.<a>=GF(p^2);#K.modulus();
R.<z> = PolynomialRing( K, sparse=True );
print'hi'
fE=(1978526766708317676482043677132634a fE=(1978526766708317676482043677132634*a + 989263383354158838241021838566317)z^13355055675281144316253794820645281 989263383354158838241021838566317)*z^13355055675281144316253794820645281 + (2967790150062476514723065515698951a (2967790150062476514723065515698951*a + 1483895075031238257361532757849475)z^8903370450187429544169196547096855 1483895075031238257361532757849475)*z^8903370450187429544169196547096855 + 2967790150062476514723065515698951z^8903370450187429544169196547096854 2967790150062476514723065515698951*z^8903370450187429544169196547096854 + (1483895075031238257361532757849476a (1483895075031238257361532757849476*a + 2967790150062476514723065515698951)z^4451685225093714772084598273548429 2967790150062476514723065515698951)*z^4451685225093714772084598273548429 + 2967790150062476514723065515698952z^4451685225093714772084598273548428 2967790150062476514723065515698952*z^4451685225093714772084598273548428 + (a + 2)z^4451685225093714772084598273548427 2)*z^4451685225093714772084598273548427 + (2473158458385397095602554596415793a (2473158458385397095602554596415793*a + 3462421841739555933843576434982110)z^3 3462421841739555933843576434982110)*z^3 + 2967790150062476514723065515698951z^2 2967790150062476514723065515698951*z^2 + (4451685225093714772084598273548426a (4451685225093714772084598273548426*a + 1)z 1)*z + 2390566828285061569181602107159913
2390566828285061569181602107159913
 
Phi10=z^2477187667914709744689409953417368724452959475301832810429239271791 + 44516852250937147720845982735484264451685225093714772084598273548426
  
x10=gcd(fE,Phi10);print"\n gcd(fE,Phi10) x10=",x10x10=",x10