Wikipedia:Reference desk/Archives/Mathematics/2010 September 25

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

September 25

Calculating powers of one polynomial modulo another efficiently over GF(p)

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!

Essentially, working over the field GF(p) for some prime p, I've been told to (and have done so!) work 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) (both essentially implementations of 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 - I can't imagine we can really go from 2 algorithms over GF(p) to find a power of one polynomial modulo another over, say, $\mathbb{Z}$. Anyway, I've tried writing out the modular arithmetic and playing around with things for hours but I really can't find any way to 'calculate this efficiently', as everything I end up with tends to still involve calculating a power of equal size of the original, and there's no guarantee it's going to be any easier to calculate than the original computation.

Could anyone suggest anything please? Thankyou very much, the more help you could provide the better! (I've been stuck on this one problem for ages now :)) Simba31415 (talk) 15:37, 25 September 2010 (UTC)

Our article on exponentiation by squaring may give you some ideas. Gandalf61 (talk) 16:24, 25 September 2010 (UTC)

I see, so you can make use of the method of successive squares to minimise the calculations needed - is there any way you can also utilise the highest common factor to make things more efficient too? I don't need a hugely detailed answer (because it's probably not terribly exciting for you!), but I don't want to spend hours trying to use the HCF in some way to make things easier if it's futile! Thankyou again, Simba31415 (talk) 19:38, 25 September 2010 (UTC)

Also if you find the order of the field you can just do the power modulo that. Dmcq (talk) 12:27, 26 September 2010 (UTC)

I shall take that as a no, there is no way to improve efficiency by using the highest common factor - good point about the order of the field though, thankyou! Perhaps I'll give up on hunting for a way to use the HCF :) Simba31415 (talk) 00:01, 28 September 2010 (UTC)

Here's one way you could use the gcd, but I'm not sure how much savings this will get you. Suppose you're looking for fⁿ mod g, and f = ab, and g = ac. Then suppose bⁿ reduces to d mod c. Now fⁿ = aⁿd mod g, so you just need to reduce aⁿd. I'm not sure if breaking it into those two steps actually helps though. Plus I don't know how often you can expect f and g to have a common factor. Rckrone (talk) 00:36, 28 September 2010 (UTC)

Limit question

hello again. I'm having some trouble with demonstrating a limit using the formal definition. I understand the formal definition, but how do I use it, for example, to demonstrate something like $\lim _{x\to 3}x^{3}$ is 27? Also I read that the derivative of a circle is -x/y. How is this derived, and more broadly, how do you find the derivatives of nonfunctions in general. THanks. 24.92.78.167 (talk) 21:33, 25 September 2010 (UTC)

on the second a circle can be defined as (cos t, sin t), i.e. x = cos t, y = sin t To find its gradient you differentiate:

dx⁄dt = –sin t, dy⁄dt = cos t,

then

dy⁄dx = dy⁄dt ÷ dx⁄dt = –cos t / sin t = –x / y

--JohnBlackburne^words_deeds 22:10, 25 September 2010 (UTC)

Or implicitly differentiate x² + y² = 1 to give 2x + 2y dy/dx = 0 and then solve for dy/dx. -- ToE^T 08:43, 26 September 2010 (UTC)

Regarding limits, by "formal definition" I assume you mean the Epsilon-delta definition. If you were given a specific numerical value for ε, can you come up with suitable values for δ? Can you then figure out a general formula for δ as a function of an unspecified ε? -- ToE^T 08:59, 26 September 2010 (UTC)

All good calculus books will provide a few theorems related to limits. Logically, the first two are two trivial theorems.

• The first says The limit of a constant is that constant. (In other words, as x approaches x₀, the constant A approaches A.)
• The second says The limit of a polynomial can be found by direct substitution. (In other words, as x approaches x₀, the polynomial f(x) approaches f(x₀). So in your example of $\lim _{x\to 3}x^{3}$ all you have to do is apply the second of these two trivial theorems. Dolphin (t) 05:52, 27 September 2010 (UTC)

Yes, it is important to understand the theorems, but it is also important to be able to work through the formal definition even in simple cases. Stating and understanding the formal definition is calculus, but working it through involves algebra (including some inequality identities) that trips up a lot of students. In your case you are trying to show that:

$\forall \varepsilon >0\ \exists \ \delta >0:\forall x\ (0<|x-3|<\delta \ \Rightarrow \ |x^{3}-27|<\varepsilon ).$

A good way to do this is to work backwards; start with the value you want to minimize, namely |x³-27|, and manipulate it into terms of what you control, namely |x-3|. So:

$|x^{3}-27|=|x-3||x^{2}+3x+9|$

You can make |x-3| as small as you wish, and you can bound |x²+3x+9| by bounding x, say by limiting $\delta <1$ so that |x| < 4. Then:

$|x-3||x^{2}+3x+9|\leq |x-3|(|x^{2}|+|3x|+|9|)<|x-3|(16+12+9)$

So choose $\delta =min(1,{\tfrac {1}{37}}\varepsilon )$. You may now wish to state the whole thing in the forward direction.

$\forall \varepsilon >0,$ let $\delta =min(1,{\tfrac {1}{37}}\varepsilon )$. Then $\forall x$ such that $0<|x-3|<\delta$ we have

$|x^{3}-27|=|x-3||x^{2}+3x+9|\leq |x-3|(|x^{2}|+|3x|+|9|)$

$<|x-3|(16+12+9)=37|x-3|<\varepsilon$. So $\lim _{x\to 3}x^{3}=27$.

Note that it was no coincidence that you could factor an x-3 out of the x³-27. Since p(x)=27, you know that 3 is a root of p(3)-27. -- 58.147.60.241 (talk) 11:34, 27 September 2010 (UTC)

You might be interested in reading wikibooks:Calculus/Formal Definition of the Limit and wikibooks:Calculus/Choosing delta. -- 124.157.247.193 (talk) 13:21, 27 September 2010 (UTC)