Long division

Polynomials

Long division of polynomials is very important for doing arithmetic on elliptic curves. 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 divisor in this example 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-y^{2}\\&&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-y^{2}\\&&&&(a+x_{0}^{2})x&{}-(ax_{0}+x_{0}^{3})\\\hline &&&&&-y^{2}+b+ax_{0}+x_{0}^{3}\end{array}}$

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 and borrowing is performed exactly as in the grade school algorithm, but generally with a base that is a power of two, 2³² or 2⁶⁴, more convenient for computers to work with.