faster GCD computation

asked 2018-03-01 13:24:56 +0200

santoshi gravatar image

how to obtained faster gcd computation over large prime field. if f1 and f2 are two polynomial over large prime field ex. p=256 it takes lot of time to perform gcd(f1,f2). how to speed up this computation.

edit retag flag offensive close merge delete

Comments

May you be more precise? First, $p=256$ is not a prime, so you're note working over a large prime field, but on the contrary in a large extension of some small prime field... And what size of polynomials do you want to handle? A very quick test on polynomials of degree up to 250 (with a common factor of degree 100) is for instance fast enough to appear instant on my (standard) laptop.

B r u n o gravatar imageB r u n o ( 2018-03-01 15:56:53 +0200 )edit

p=256 thst is elliptic curve of 256 bits

santoshi gravatar imagesantoshi ( 2018-03-01 17:34:10 +0200 )edit
1

You should simply give an example of the computation you are trying to perform! Because I am not able to make any sense of you latest comment.

B r u n o gravatar imageB r u n o ( 2018-03-01 18:30:13 +0200 )edit

As @B r u n o suggests, it would be a lot easier to answer the question if instead of

if f1 and f2 are two polynomial over large prime field ex. p=256 it takes lot of time to perform gcd(f1,f2)

you provided an actual example that illustrates the problem and that other users can copy and paste into a Sage session to explore the problem in order to give help.

Something like:

sage: F = GF(256)
sage: F
Finite Field in z8 of size 2^8
sage: R.<x> = F[]
sage: f = x^203 + x^15 + 1
sage: g = x^34 + x^23 + 1
sage: %time gcd(f, g)
CPU times: user 449 µs, sys: 59 µs, total: 508 µs
Wall time: 511 µs
1

Here the answer is computed in half a millisecond.

slelievre gravatar imageslelievre ( 2018-03-05 13:05:44 +0200 )edit