- #1
simba31415
- 12
- 0
Hi all,
I've been set some holiday work by my study director which is meant to be teaching us all about algorithms and a few other mathematical bits and bobs - unfortunately I've come unstuck on one of the bobs, and was hoping for some help! I've asked for help elsewhere but was given very little detail and didn't get much further with the problem, so I thought I'd try here instead as I've been told PF is very reliable when it comes to helpful people :)
Essentially, working over the field GF(p) for some prime p, I've written out the code for a program to find the quotient and remainder from dividing 2 polynomials over GF(p), and another program using the first one which finds the highest common factor of 2 polynomials over GF(p) (implementing Euclid's algorithm). Next, he writes 'explain how to use your programs to efficiently calculate a large power of one polynomial modulo another polynomial'. He hasn't explicitly put over GF(p) here, but I assume that must be the case. Anyway, I can see how using the first program would give us an easy way to perform modular arithmetic, so the use of that is fairly obvious, but what I'm coming unstuck on is a way to use the knowledge of the highest common factor to make the calculation more efficient - is there actually such a way?
2 ways to improve the efficiency I can see are to use the method of successive squares to reduce the necessary number of multiplications, and to take the power to which we're raising our first polynomial mod p, since x^(p-1) will always be congruent to one for all x. Clearly though, neither of these make use of the HCF.
Could anyone please, -please- suggest a way of using the HCF to effectively increase the efficiency of the calculation, or at the very least put me out of my misery and tell me that there is no such way? I've been stuck on this one problem for ages now, and I'm a bit sick of it! Any help will be huuugely appreciated :) Thankyou!
I've been set some holiday work by my study director which is meant to be teaching us all about algorithms and a few other mathematical bits and bobs - unfortunately I've come unstuck on one of the bobs, and was hoping for some help! I've asked for help elsewhere but was given very little detail and didn't get much further with the problem, so I thought I'd try here instead as I've been told PF is very reliable when it comes to helpful people :)
Essentially, working over the field GF(p) for some prime p, I've written out the code for a program to find the quotient and remainder from dividing 2 polynomials over GF(p), and another program using the first one which finds the highest common factor of 2 polynomials over GF(p) (implementing Euclid's algorithm). Next, he writes 'explain how to use your programs to efficiently calculate a large power of one polynomial modulo another polynomial'. He hasn't explicitly put over GF(p) here, but I assume that must be the case. Anyway, I can see how using the first program would give us an easy way to perform modular arithmetic, so the use of that is fairly obvious, but what I'm coming unstuck on is a way to use the knowledge of the highest common factor to make the calculation more efficient - is there actually such a way?
2 ways to improve the efficiency I can see are to use the method of successive squares to reduce the necessary number of multiplications, and to take the power to which we're raising our first polynomial mod p, since x^(p-1) will always be congruent to one for all x. Clearly though, neither of these make use of the HCF.
Could anyone please, -please- suggest a way of using the HCF to effectively increase the efficiency of the calculation, or at the very least put me out of my misery and tell me that there is no such way? I've been stuck on this one problem for ages now, and I'm a bit sick of it! Any help will be huuugely appreciated :) Thankyou!
