Long division - Revision history

Rational Point: database corrupted

2025-01-20T16:57:24Z

database corrupted

← Older revision		Revision as of 16:57, 20 January 2025
Line 1:		Line 1:
	[[Category:Algorithms]]		[[Category:Algorithms]]



	== Polynomials ==		== 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.		'''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 ~~divisor~~ in this example of simple long division is from the [[Weierstraß normal form]] of an elliptic curve.		The dividend in this example of simple long division is from the [[Weierstraß normal form]] of an elliptic curve.

	:<math> \begin{array}{rr\|rrrr}		:<math> \begin{array}{rr\|rrrr}

Rational Point: partial fractions

2025-01-20T15:23:47Z

partial fractions

← Older revision		Revision as of 15:23, 20 January 2025
Line 3:		Line 3:
	== Polynomials ==		== 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.		'''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 '''partial fraction''' yielded by a polynomial long division is the remainder placed over the divisor as a “proper polynomial fraction” with the degree of the numerator less than that of the denominator. Successive long divisions yield more partial fractions until the dividend is completely factored.

	The divisor in this example of simple long division is from the [[Weierstraß normal form]] of an elliptic curve.		The divisor in this example of simple long division is from the [[Weierstraß normal form]] of an elliptic curve.
Line 10:		Line 8:
	:<math> \begin{array}{rr\|rrrr}		:<math> \begin{array}{rr\|rrrr}
	&&&x^2&{}+x_0x&{}+(a+x_0^2)\\ \hline		&&&x^2&{}+x_0x&{}+(a+x_0^2)\\ \hline
	x& {}-x_0 & x^3 & & {}+ax & {}+b~~-y^2~~\\		x& {}-x_0 & x^3 & & {}+ax & {}+b\\
	&& x^3 &{}-x_0x^2\\ \hline		&& x^3 &{}-x_0x^2\\ \hline
	&&& x_0x^2 &{}+ax\\		&&& x_0x^2 &{}+ax\\
	&&& x_0x^2 &{}-x_0^2x\\ \hline		&&& x_0x^2 &{}-x_0^2x\\ \hline
	&&&& (a+x_0^2)x &{}+b~~-y^2~~\\		&&&& (a+x_0^2)x &{}+b\\
	&&&&(a+x_0^2)x &{}-(ax_0+x_0^3)\\ \hline		&&&&(a+x_0^2)x &{}-(ax_0+x_0^3)\\ \hline
	&R=&&&& x_0^3+ax_0+b~~-y^2~~		&R=&&&& x_0^3+ax_0+b
	\end{array} </math>		\end{array} </math>
			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.

			:<math>\frac{x^3+ax+b}{x-x_0}=x^2+x_0x+(a+x_0^2)+\frac{x_0^3+ax_0+b}{x-x_0}</math>

			Successive long divisions will yield more partial fractions until the dividend is completely factored, if a complete “partial fractions decomposition” is desired.
	== Big integers ==		== 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<sup>32</sup> or 2<sup>64</sup> rather than 10, more convenient for computers to work with.		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<sup>32</sup> or 2<sup>64</sup> rather than 10, more convenient for computers to work with.

Rational Point: /* Polynomials */

2025-01-20T15:12:09Z

Polynomials

← Older revision		Revision as of 15:12, 20 January 2025
Line 2:		Line 2:

	== Polynomials ==		== 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.		'''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 divisor in this example is from the [[Weierstraß normal form]] of an elliptic curve.		The '''partial fraction''' yielded by a polynomial long division is the remainder placed over the divisor as a “proper polynomial fraction” with the degree of the numerator less than that of the denominator. Successive long divisions yield more partial fractions until the dividend is completely factored.

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

	:<math> \begin{array}{rr\|rrrr}		:<math> \begin{array}{rr\|rrrr}
Line 14:		Line 16:
	&&&& (a+x_0^2)x &{}+b-y^2\\		&&&& (a+x_0^2)x &{}+b-y^2\\
	&&&&(a+x_0^2)x &{}-(ax_0+x_0^3)\\ \hline		&&&&(a+x_0^2)x &{}-(ax_0+x_0^3)\\ \hline
	&&&&& -y^~~2+b~~+ax_0+~~x_0~~^3		&R=&&&& x_0^3+ax_0+b-y^2
	\end{array} </math>		\end{array} </math>

	== Big integers ==		== 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<sup>32</sup> or 2<sup>64</sup> rather than 10, more convenient for computers to work with.		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<sup>32</sup> or 2<sup>64</sup> rather than 10, more convenient for computers to work with.

Rational Point: /* Big integers */ or

2024-12-23T03:47:59Z

Big integers: or

← Older revision		Revision as of 03:47, 23 December 2024
Line 18:		Line 18:

	== Big integers ==		== 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<sup>32</sup> or 2<sup>64</sup>, more convenient for computers to work with.		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<sup>32</sup> or 2<sup>64</sup> rather than 10, more convenient for computers to work with.

Rational Point: polynomial long division in latex

2024-12-23T03:42:41Z

polynomial long division in latex

New page

[[Category:Algorithms]]

== 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.

:<math> \begin{array}{rr|rrrr}
&&&x^2&{}+x_0x&{}+(a+x_0^2)\\ \hline
x& {}-x_0 & x^3 & & {}+ax & {}+b-y^2\\
&& x^3 &{}-x_0x^2\\ \hline
&&& x_0x^2 &{}+ax\\
&&& x_0x^2 &{}-x_0^2x\\ \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} </math>

== 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<sup>32</sup> or 2<sup>64</sup>, more convenient for computers to work with.