Ask Your Question

gcd computation of two polynomial

asked 2018-07-01 13:53:42 +0200

santoshi gravatar image

updated 2018-07-01 16:18:22 +0200

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 );
R.<z> = PolynomialRing( K, sparse=True );
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 flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted

answered 2018-07-03 14:49:46 +0200

B r u n o gravatar image

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

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower


Asked: 2018-07-01 13:53:42 +0200

Seen: 510 times

Last updated: Jul 03 '18