Why does this work?

Revision en1, by usernameson, 2017-12-22 07:18:08

Somehow I managed to solve 901B - GCD of Polynomials however I don't know why my solution works. My idea was to pick two random polynomials of degrees n and n-1 check how many steps it takes to find the gcd and return the polynomials if the answer is n. However doing the gcd over is hard because of fractions. So I decided to pick a prime and do gcds over the finite field Fp. The strange thing is with a bigish prime like 1009 the algorithm took more steps over this field than over . Then I tried using the prime 43 just to see what would happen and it worked.

code
Tags #number theory, constructive algorithms, polynomials

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English usernameson 2017-12-22 07:34:28 23 Tiny change: 'ect answers and it worked fo' -> 'ect answer. Surprisingly using 43 worked fo' (published)
en2 English usernameson 2017-12-22 07:32:05 365
en1 English usernameson 2017-12-22 07:18:08 2767 Initial revision (saved to drafts)