Help Needed: Calculating a Large Power of a Polynomial Modulo Another

In summary, the person is asking for help with a problem and is looking for someone who can provide a solution. They have written code for two programs to calculate a power of one and a polynomial, but they are not able to use the knowledge of the highest common factor to make the calculation more efficient.
  • #1
simba31415
13
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!
 
Physics news on Phys.org
  • #2


Incidentally, if anyone can point me in the right direction for this then I'd be very happy to read up on it myself, I don't need the whole concept explained to me if you can just nudge me in the right area :)
 
  • #3


Please could the mods delete this thread? I believe I found a way myself, so I'd appreciate it if they could get rid of this :)
 

1. How do I calculate a large power of a polynomial modulo another?

To calculate a large power of a polynomial modulo another, you can use the binomial theorem and modular arithmetic. First, expand the polynomial to its binomial form. Then, use the binomial theorem to calculate the large power of each term. Finally, use modular arithmetic to reduce the result modulo the other polynomial.

2. What is the binomial theorem?

The binomial theorem is a mathematical formula that allows you to expand a binomial expression raised to a power. It states that (a+b)^n = sum from k=0 to n of (n choose k) * a^(n-k) * b^k, where (n choose k) is the binomial coefficient.

3. How does modular arithmetic work?

Modular arithmetic is a type of arithmetic that deals with integers and a specific modulus. It involves finding the remainder when an integer is divided by the modulus. This remainder is known as the residue and is used to reduce the result of a calculation modulo the modulus.

4. Can I use a calculator for this calculation?

Yes, you can use a calculator for this calculation, but make sure it has a function for calculating binomial coefficients and modular arithmetic. Alternatively, you can use a computer algebra system like Mathematica or Wolfram Alpha.

5. Why do we need to calculate a large power of a polynomial modulo another?

Calculating a large power of a polynomial modulo another is useful in many areas of mathematics and computer science. It can be used in cryptography, number theory, and coding theory, among others. It allows us to manipulate and analyze large numbers more efficiently and can also provide insights into the underlying structure of the problem at hand.

Similar threads

  • Engineering and Comp Sci Homework Help
Replies
8
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
748
  • Linear and Abstract Algebra
Replies
3
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
9
Views
1K
Replies
8
Views
2K
  • Electrical Engineering
2
Replies
36
Views
2K
Replies
3
Views
2K
  • Linear and Abstract Algebra
Replies
17
Views
4K
  • Linear and Abstract Algebra
Replies
2
Views
1K
Back
Top