Quartic point group operation

A “twisted infinity-bun” curve of degree four, which may or may not have many rational points or be suitable for cryptographic use.

The point group operation over quartic (or hyperelliptic ) curves (of degree four) is defined geometrically as follows. Let

$y^{2}=q_{4}x^{4}+q_{3}x^{3}+q_{2}x^{2}+q_{1}x+q_{0}$

be a quartic curve on the x-y plane of real numbers, the polynomial in x on the right having either the coefficient q₄>0 or at least two real roots counting multiplicity.

Preparing the equations for solution in general form

When the degree of a solvend equation is even and at least four, its resolvent is a generic polynomial exactly half of it in degree, and the resolvent is squared so that it “rises to meet” the solvend. The resultant is the difference, when the solvend is subtracted from the resolvent equation squared.

y =			ax2	+ bx	+ c		(resolvent equation)
y2 =	a2x4	+ 2abx3	+ (b2 + 2ac)x2	+ 2bcx	+ c2		(resolvent squared)
y2 =	q4x4	+ q3x3	+ q2x2	+ q1x	+ q0		(solvend equation)
	(a2 — q4)x4	+ (2ab — q3)x3	+ (b2 + 2ac — q3)x2	+ (2bc — q1)x	+ c2 — q0	= 0	(resultant equation)

The general objective is to find rational points (x,y) on the curve which satisfy the solvend equation. Any four points on the quartic curve, counting multiplicity, which simultaneously satify the same resolvent quadratic equation, are considered to “sum” to an “additional point at infinity” O, which serves as the identity for a certain abstract Abelian group operation which we denote here by the symbol ⨁.

In any case we would start from at least one known point (x₁,y₁), and as a first step reduce the resultant equation to a cubic by factoring out x – x₁, in order to eventually solve for the unknown coefficients of the resolvent equation and the coördinates of the unknown point in terms of known points.

${\begin{array}{r|rrrr}&&(a^{2}-q_{4})x^{3}&{}+{2ab-q_{3}+ \choose a^{2}x_{1}-q_{4}x_{1}}x^{2}&{}+{b^{2}+2ac-q_{2}+2abx_{1} \choose {}-q_{3}x_{1}+a^{2}x_{1}^{2}-q_{4}x_{1}^{2}}x&{}+{2bc-q_{1}+b^{2}x_{1}+2acx_{1}-q_{2}x_{1} \choose +2abx_{1}^{2}-q_{3}x_{1}^{2}+a^{2}x_{1}^{3}-q_{4}x_{1}^{3}}\\\hline x-x_{1}&(a^{2}-q_{4})x^{4}&{}+(2ab-q_{3})x^{3}&{}+(b^{2}+2ac-q_{2})x^{2}&{}+(2bc-q_{1})x&{}+c^{2}-q_{0}\\&(a^{2}-q_{4})x^{4}&{}-(a^{2}-q_{4})x_{1}x^{3}\\\hline &&{2ab-q_{3}+ \choose a^{2}x_{1}-q_{4}x_{1}}x^{3}&{}+(b^{2}+2ac-q_{2})x^{2}\\&&{2ab-q_{3}+ \choose a^{2}x_{1}-q_{4}x_{1}}x^{3}&{}-{2abx_{1}-q_{3}x_{1} \choose {}+a^{2}x_{1}^{2}-q_{4}x_{1}^{2}}x^{2}\\\hline &&&{b^{2}+2ac-q_{2}+2abx_{1} \choose {}-q_{3}x_{1}+a^{2}x_{1}^{2}-q_{4}x_{1}^{2}}x^{2}&{}+(2bc-q_{1})x\\&&&{b^{2}+2ac-q_{2}+2abx_{1} \choose {}-q_{3}x_{1}+a^{2}x_{1}^{2}-q_{4}x_{1}^{2}}x^{2}&{}-{b^{2}x_{1}+2acx_{1}-q_{2}x_{1}+2abx_{1}^{2} \choose -q_{3}x_{1}^{2}+a^{2}x_{1}^{3}-q_{4}x_{1}^{3}}x\\\hline &&&&{2bc-q_{1}+b^{2}x_{1}+2acx_{1}-q_{2}x_{1} \choose +2abx_{1}^{2}-q_{3}x_{1}^{2}+a^{2}x_{1}^{3}-q_{4}x_{1}^{3}}x&{}+c^{2}-q_{0}\\&&&&{2bc-q_{1}+b^{2}x_{1}+2acx_{1}-q_{2}x_{1} \choose +2abx_{1}^{2}-q_{3}x_{1}^{2}+a^{2}x_{1}^{3}-q_{4}x_{1}^{3}}x&{}-{2bcx_{1}-q_{1}x_{1}+b^{2}x_{1}^{2}+2acx_{1}^{2}-q_{2}x_{1}^{2} \choose +2abx_{1}^{3}-q_{3}x_{1}^{3}+a^{2}x_{1}^{4}-q_{4}x_{1}^{4}}\\\hline R=&&&&&{c^{2}-q_{0}+2bcx_{1}-q_{1}x_{1}+b^{2}x_{1}^{2}+2acx_{1}^{2} \choose -q_{2}x_{1}^{2}+2abx_{1}^{3}-q_{3}x_{1}^{3}+a^{2}x_{1}^{4}-q_{4}x_{1}^{4}}\end{array}}$

The remainder is equal to the value of the resultant polynomial at the point x₁.

A quartic square dance

Every operation over a quartic curve will be defined geometrically by a “square dance” of the four points of intersection of the quartic curve and a parabola whose axis is parallel to the y-axis, and otherwise to be determined.

Namely if P, Q, R, and S are four points of the quartic curve, through which a parabola with an axis parallel to the y-axis passes, then we will say that

$P\oplus Q\oplus R\oplus S=O$

where O is the additional “point at infinity” which serves as the additive group identity.

Additive inverses

If P is a point on the quartic curve, then its inverse is found by solving for $Q=-P$ in this “square dance” equation

$P\oplus P\oplus Q\oplus Q=O$

where the resolvent parabola $y=ax^{2}+bx+c$ is required to be tangent to the original curve both at the point P = (x₁,y₁) and at the unknown point Q = (x,y). File:Denis-DiscussionCasesTwo-1903-9-jam8-join.pdf

However by now we are at the point of dispensing entirely with the computer algebra system and doing our own long division to verify the partial fractions decomposition and derive the symbolic solutions.

To be verified very thoroughly. (You don’t work in the financial industry if you double-check!)

${\begin{array}{r|rrrr}&&(a^{2}-q_{4})x^{2}&{}+{2ab-q_{3}+ \choose 2a^{2}x_{1}-2q_{4}x_{1}}x&{}+{b^{2}+2ac-q_{2}+4abx_{1} \choose -2q_{3}x_{1}+3a^{2}x_{1}^{2}-3q_{4}x_{1}^{2}}\\\hline x-x_{1}&(a^{2}-q_{4})x^{3}&{}+{2ab-q_{3}+ \choose a^{2}x_{1}-q_{4}x_{1}}x^{2}&{}+{b^{2}+2ac-q_{2}+2abx_{1} \choose {}-q_{3}x_{1}+a^{2}x_{1}^{2}-q_{4}x_{1}^{2}}x&{}+{2bc-q_{1}+b^{2}x_{1}+2acx_{1}-q_{2}x_{1} \choose +2abx_{1}^{2}-q_{3}x_{1}^{2}+a^{2}x_{1}^{3}-q_{4}x_{1}^{3}}\\&(a^{2}-q_{4})x^{3}&{}-(a^{2}x_{1}-q_{4}x_{1})x^{2}\\\hline &&{2ab-q_{3}+ \choose 2a^{2}x_{1}-2q_{4}x_{1}}x^{2}&{}+{b^{2}+2ac-q_{2}+2abx_{1} \choose {}-q_{3}x_{1}+a^{2}x_{1}^{2}-q_{4}x_{1}^{2}}x\\&&{2ab-q_{3}+ \choose 2a^{2}x_{1}-2q_{4}x_{1}}x^{2}&{}-{2abx_{1}-q_{3}x_{1} \choose +2a^{2}x_{1}^{2}-2q_{4}x_{1}^{2}}x\\\hline &&&{b^{2}+2ac-q_{2}+4abx_{1} \choose -2q_{3}x_{1}+3a^{2}x_{1}^{2}-3q_{4}x_{1}^{2}}x&{}+{2bc-q_{1}+b^{2}x_{1}+2acx_{1}-q_{2}x_{1} \choose +2abx_{1}^{2}-q_{3}x_{1}^{2}+a^{2}x_{1}^{3}-q_{4}x_{1}^{3}}\\&&&{b^{2}+2ac-q_{2}+4abx_{1} \choose -2q_{3}x_{1}+3a^{2}x_{1}^{2}-3q_{4}x_{1}^{2}}x&{}-{b^{2}x_{1}+2acx_{1}-q_{2}x_{1}+4abx_{1}^{2} \choose -2q_{3}x_{1}^{2}+3a^{2}x_{1}^{3}-3q_{4}x_{1}^{3}}\\\hline R=&&&&{2bc-q_{1}+2b^{2}x_{1}+4acx_{1}-2q_{2}x_{1} \choose +6abx_{1}^{2}-3q_{3}x_{1}^{2}+3a^{2}x_{1}^{3}-3q_{4}x_{1}^{3}}\end{array}}$

Graphical depiction of inverse points on a quartic curve, showing the two points of tangency of the parabola with the quartic curve, and the vertical line which bisects the line segment between the inverse points and also intersects at the same point where the tangent lines do.

To verify: the remainder, on dividing x – x₁ into the resultant polynomial for the second time, is equal to the derivative of the original resultant at the point x₁. We are now looking for the second point of tangency x between the quartic curve and the parabola of the resolvent quadratic equation. Hence four equations to be solved simultaneously for a, b, c and x in terms of q₄, q₃, q₂, q₁, q₀, x₁, y₁ and y₁’.

${\begin{array}{rcl}ax_{1}^{2}+bx_{1}+c-y_{1}&=&0\\2ax_{1}+b-y_{1}'&=&0\\(a^{2}-q_{4})x^{2}+{2ab-q_{3}+ \choose 2a^{2}x_{1}-2q_{4}x_{1}}x+{b^{2}+2ac-q_{2}+4abx_{1} \choose -2q_{3}x_{1}+3a^{2}x_{1}^{2}-3q_{4}x_{1}^{2}}&=&0\\2(a^{2}-q_{4})x+2ab-q_{3}+2a^{2}x_{1}-2q_{4}x_{1}&=&0\\\end{array}}$

where

${\begin{array}{rcl}y_{1}&=&\pm {\sqrt {q_{4}x_{1}^{4}+q_{3}x_{1}^{3}+q_{2}x_{1}^{2}+q_{1}x_{1}+q_{0}}}\\y_{1}'&=&{\dfrac {\pm \left(4q_{4}x_{1}^{3}+3q_{3}x_{1}^{2}+2q_{2}x_{1}+q_{1}\right)}{2{\sqrt {q_{4}x_{1}^{4}+q_{3}x_{1}^{3}+q_{2}x_{1}^{2}+q_{1}x_{1}+q_{0}}}}}\end{array}}$

The residuals from this system of four equations are shown here, as very nearly solved numerically, from the data plotted on the chart to the right with x₁ = 2 and x = –2.4 as an example on the same quartic curve as pictured above.

> a * x1^2 + b*x1 + c - y1
[1] 0
> 2*a*x1 + b - y1_
[1] 0
> (a^2 - q4)*x^2 + (2*a*b - q3 + 2*a^2*x1 - 2*q4*x1)*x +
+       b^2 + 2*a*c - q2 + 4*a*b*x1 - 2*q3*x1 + 3*a^2*x1^2 - 3*q4*x1^2
[1] 0.004125696
> 2*(a^2 - q4)*x + 2*a*b - q3 + 2*a^2*x1 - 2*q4*x1
[1] 0.0003871946

The term of a²x², in the fourth degree in the unknowns, may be eliminated, reducing the degree of the system of equations to three. Multiply the 3rd equation by 2 and the 4th equation by x, and then subtract.

${\begin{array}{rcl}2(a^{2}-q_{4})x^{2}+2{2ab-q_{3}+ \choose 2a^{2}x_{1}-2q_{4}x_{1}}x+2{b^{2}+2ac-q_{2}+4abx_{1} \choose -2q_{3}x_{1}+3a^{2}x_{1}^{2}-3q_{4}x_{1}^{2}}&=&0\\2(a^{2}-q_{4})x^{2}+2abx-q_{3}x+2a^{2}x_{1}x-2q_{4}x_{1}x&=&0\\\hline {2ab-q_{3}+ \choose 2a^{2}x_{1}-2q_{4}x_{1}}x+2{b^{2}+2ac-q_{2}+4abx_{1} \choose -2q_{3}x_{1}+3a^{2}x_{1}^{2}-3q_{4}x_{1}^{2}}&=&0\end{array}}$

Replace the third equation:

${\begin{array}{rcl}ax_{1}^{2}+bx_{1}+c-y_{1}&=&0\\2ax_{1}+b-y_{1}'&=&0\\{2ab-q_{3}+ \choose 2a^{2}x_{1}-2q_{4}x_{1}}x+2{b^{2}+2ac-q_{2}+4abx_{1} \choose -2q_{3}x_{1}+3a^{2}x_{1}^{2}-3q_{4}x_{1}^{2}}&=&0\\2(a^{2}-q_{4})x+2ab-q_{3}+2a^{2}x_{1}-2q_{4}x_{1}&=&0\\\end{array}}$

The first two of these equations can be solved for b and c and the resulting substitutions, $b=y_{1}'-2ax_{1}$ and $c=y_{1}+ax_{1}^{2}-x_{1}y_{1}'$ made in the third and fourth equations.

${\begin{array}{rcl}{2a(y_{1}'-2ax_{1})-q_{3} \choose +2a^{2}x_{1}-2q_{4}x_{1}}x+2{(y_{1}'-2ax_{1})^{2}+2a(y_{1}+ax_{1}^{2}-x_{1}y_{1}')-q_{2}+ \choose 4a(y_{1}'-2ax_{1})x_{1}-2q_{3}x_{1}+3a^{2}x_{1}^{2}-3q_{4}x_{1}^{2}}&=&0\\2(a^{2}-q_{4})x+2a(y_{1}'-2ax_{1})-q_{3}+2a^{2}x_{1}-2q_{4}x_{1}&=&0\\\end{array}}$

Now the variable x can be eliminated, with the remaining equations combined into a single equation of degree no more than four to be solved for a.

${2a(y_{1}'-2ax_{1})-q_{3} \choose {}+2a^{2}x_{1}-2q_{4}x_{1}}^{2}-4(a^{2}-q_{4}){(y_{1}'-2ax_{1})^{2}+2a(y_{1}+ax_{1}^{2}-x_{1}y_{1}')-q_{2}+ \choose 4a(y_{1}'-2ax_{1})x_{1}-2q_{3}x_{1}+3a^{2}x_{1}^{2}-3q_{4}x_{1}^{2}}=0$

Begin multiplying out the terms.

${2ay_{1}'-4a^{2}x_{1}-q_{3} \choose {}+2a^{2}x_{1}-2q_{4}x_{1}}^{2}-4(a^{2}-q_{4}){y_{1}'^{2}-4ax_{1}y_{1}'+4a^{2}x_{1}^{2}+2ay_{1}+2a^{2}x_{1}^{2}-2ax_{1}y_{1}' \choose -q_{2}+4ax_{1}y_{1}'-8a^{2}x_{1}^{2}-2q_{3}x_{1}+3a^{2}x_{1}^{2}-3q_{4}x_{1}^{2}}=0$

Cancel and collect like terms.

${2ay_{1}'-2a^{2}x_{1} \choose {}-q_{3}-2q_{4}x_{1}}^{2}-4(a^{2}-q_{4}){y_{1}'^{2}+a^{2}x_{1}^{2}+2ay_{1}-2ax_{1}y_{1}' \choose -q_{2}-2q_{3}x_{1}-3q_{4}x_{1}^{2}}=0$

${\begin{array}{l}(2a^{2}x_{1}-2ay_{1}'+q_{3}+2q_{4}x_{1})^{2}\\\quad {}-4(a^{2}-q_{4})(a^{2}x_{1}^{2}+2a(y_{1}-x_{1}y_{1}')+y_{1}'^{2}-q_{2}-2q_{3}x_{1}-3q_{4}x_{1}^{2})=0\end{array}}$

${\begin{array}{l}4a^{4}x_{1}^{2}-8a^{3}x_{1}y_{1}'+4a^{2}(y_{1}'^{2}+x_{1}(q_{3}+2q_{4}x_{1}))-4ay_{1}'(q_{3}+2q_{4}x_{1})+(q_{3}+2q_{4}x_{1})^{2}\\\quad {}-4a^{2}(a^{2}x_{1}^{2}+2a(y_{1}-x_{1}y_{1}')+y_{1}'^{2}-q_{2}-2q_{3}x_{1}-3q_{4}x_{1}^{2})\\\quad {}+4q_{4}(a^{2}x_{1}^{2}+2a(y_{1}-x_{1}y_{1}')+y_{1}'^{2}-q_{2}-2q_{3}x_{1}-3q_{4}x_{1}^{2})=0\end{array}}$

The terms of highest order cancel out, leaving a cubic equation to be solved for a.

${\begin{aligned}(-8x_{1}y_{1}'+2(y_{1}-x_{1}y_{1}'))&a^{3}\\{}+(4(y_{1}'^{2}+x_{1}(q_{3}+2q_{4}x_{1}))+4(q_{2}+2q_{3}x_{1}+3q_{4}x_{1}^{2}-y_{1}'^{2})+4q_{4}x_{1}^{2})&a^{2}\\{}+(-4y_{1}'(q_{3}+2q_{4}x_{1})+8q_{4}(y_{1}-x_{1}y_{1}'))&a\\{}+(q_{3}+2q_{4}x_{1})^{2}+4q_{4}(y_{1}'^{2}-q_{2}-2q_{3}x_{1}-3q_{4}x_{1}^{2})&\quad =0\end{aligned}}$

Point averaging

The average or “mean” of two points P and Q may be found by solving the square dance equation

$P\oplus Q\oplus R\oplus R=O$

Here let the parabola pass through the points P and Q and be tangent to the quartic curve at R. Take the inverse to find the mean: ${\frac {P\oplus Q}{2}}=-R$.

Point trebling

To treble a point P, solve the “square dance” equation

$P\oplus P\oplus P\oplus Q=O$

and then take the inverse of Q to find $3P=-Q$. Here the parabola is required to osculate the quartic curve at the point P which appears with a multiplicity of three in the equation, and intersect simply at the point Q.

Point trisection

Trisecting a point is exactly the same as trebling, except that it is at the unknown point Q where the parabola and the quartic curve are required to osculate, and a simple intersection is permitted at the point P.

$P\oplus Q\oplus Q\oplus Q=O$.

Now take the inverse of Q to find ${\frac {P}{3}}=-Q$.

Point doubling

Point doubling is performed by trebling and then averaging

$2P={\frac {P\oplus 3P}{2}}$.

Some of the steps of taking additive inverses may be eliminated or simplified. This might be calculated with one less step.

$2P=-\left({\frac {-P\oplus (-3P)}{2}}\right).$

Point bisection

Point bisection or “halving” is performed by doubling a point and averaging with its additive inverse.

${\frac {1}{2}}P={\frac {2P\oplus (-P)}{2}}$

Point group addition

$P\oplus Q={\dfrac {\left({\dfrac {P\oplus Q}{2}}\right)\oplus 3\left({\dfrac {P\oplus Q}{2}}\right)}{2}}$

The most essential and basic operation of “adding” two points, which should serve as the point group operation for cryptographic purposes, is now derived at the end of a long, roundabout square dance routine by calculating the mean of two points, and then doubling by means of trebling and averaging.

The algebra and calculus equations should be simplified, and made as efficient as possible. The operation has been suitably defined, and nothing has been introduced here that should violate the axioms of an Abelian group.

Next steps

Once you have mastered the quartic point group operation, the proof of Mordell’s theorem by infinite descent, methods of bounding heights of rational numbers, and the theory of numerical and floating point approximations for curve fitting, you may move on to the quintic point group operation.

Appendix: R code for example curve plot

#! /usr/bin/R -f

H <- function(x){
    sqrt((5/17)*(11-2*x^2/3)*(x+2/7)^2)
}

xvals <- seq(0,sqrt(16.5),0.0001)

plot(x=c(xvals,rev(xvals),-xvals,-rev(xvals)),
    y=c(H(xvals),-H(rev(xvals)),-H(-xvals),H(-rev(xvals))),
    type="l", lwd=3, col="brown",
    xlab="x", ylab="y", asp="1",
    main=expression(17*y^2 == 5*(11-2*x^2/3)*(x+2/7)^2)
)
abline(0,0)