faster GCD computation

edit

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.

p=256 thst is elliptic curve of 256 bits

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.

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.