Long division

Polynomials

Long division of polynomials is pehaps better known as a method of perfoming “partial fractions decomposition.” It is exactly as you learned in grade school, except that the place values are powers of an unknown variable and it is impossible to carry or borrow.

The dividend in this example of simple long division is from the Weierstraß normal form of an elliptic curve.

${\begin{array}{rr|rrrr}&&&x^{2}&{}+x_{0}x&{}+(a+x_{0}^{2})\\\hline x&{}-x_{0}&x^{3}&&{}+ax&{}+b\\&&x^{3}&{}-x_{0}x^{2}\\\hline &&&x_{0}x^{2}&{}+ax\\&&&x_{0}x^{2}&{}-x_{0}^{2}x\\\hline &&&&(a+x_{0}^{2})x&{}+b\\&&&&(a+x_{0}^{2})x&{}-(ax_{0}+x_{0}^{3})\\\hline &R=&&&&x_{0}^{3}+ax_{0}+b\end{array}}$

The partial fraction yielded by a polynomial long division is simply the remainder placed over the divisor as a “proper polynomial fraction” with the degree of the numerator less than that of the denominator.

${\frac {x^{3}+ax+b}{x-x_{0}}}=x^{2}+x_{0}x+(a+x_{0}^{2})+{\frac {x_{0}^{3}+ax_{0}+b}{x-x_{0}}}$

Successive long divisions will yield more partial fractions until the dividend is completely factored, if a complete “partial fractions decomposition” is desired.

Big integers

Long division on big integers is of course also valuable for performing the point group operation and other arithmetic on elliptic curves over finite fields. These are long numbers with many, many digits, and the carrying or borrowing is performed exactly as in the grade school algorithm, but generally with a base that is a power of two, 2³² or 2⁶⁴ rather than 10, more convenient for computers to work with.