View source for Quartic point group operation

[[Image:Quart.svg|frame|right|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 a '''quartic''' (or, rarely, '''biquadratic''') '''curve''' (i.e., a  '''hyperelliptic''' <ref>https://hyperelliptic.org/</ref> curve of degree four) in ''y''<sup>2</sup> is defined geometrically as follows. Let
:<math>y^2 = q_4x^4+q_3x^3+q_2x^2+q_1x+q_0</math>
be a quartic curve on the ''x''-''y'' plane of real numbers, the polynomial in ''x'' on the right having either the coefficient ''q''<sub>4</sub>&gt;0 or at least two real roots counting multiplicity. Quartic curves of this form include various lemniscates and ovals with a negative leading coefficient as well as open curves with a positive leading coefficient and two or three disconnected components.

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

{|style="text-align:right;clear:both"
|-
||''y'' =|| || ||''ax''<sup>2</sup>||+ ''bx''||+ c|| ||(resolvent equation)
|-
||''y''<sup>2</sup> =||''a''<sup>2</sup>''x''<sup>4</sup>||+ 2''abx''<sup>3</sup>||+ (''b''<sup>2</sup> + 2''ac'')''x''<sup>2</sup>
||+ 2''bcx''||+ ''c''<sup>2</sup> || ||(resolvent squared)
|-
||''y''<sup>2</sup> =||''q''<sub>4</sub>''x''<sup>4</sup>
|| + ''q''<sub>3</sub>''x''<sup>3</sup>
|| + ''q''<sub>2</sub>''x''<sup>2</sup>
|| + ''q''<sub>1</sub>''x''
|| + ''q''<sub>0</sub>|| 
||(solvend equation)
|-
|| ||(''a''<sup>2</sup> — ''q''<sub>4</sub>)''x''<sup>4</sup>
|| + (2''ab'' — ''q''<sub>3</sub>)''x''<sup>3</sup>
|| + (''b''<sup>2</sup> + 2''ac'' — ''q''<sub>3</sub>)''x''<sup>2</sup>
|| + (2''bc'' — ''q''<sub>1</sub>)''x''
|| + ''c''<sup>2</sup> — ''q''<sub>0</sub>
|| = 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''<sub>1</sub>,''y''<sub>1</sub>), and as a first step reduce the resultant equation to a cubic by factoring out ''x'' – ''x''<sub>1</sub>, 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.

<math>\begin{array}{r|rrrr}
&&(a^2-q_4)x^3&{}+{2ab-q_3+\choose a^2x_1-q_4x_1}x^2&{}+{b^2+2ac-q_2+2abx_1\choose{}-q_3x_1+a^2x_1^2-q_4x_1^2}x&{}+{2bc-q_1+b^2x_1+2acx_1-q_2x_1\choose+ 2abx_1^2-q_3x_1^2+a^2x_1^3-q_4x_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_1x^3\\\hline
&&{2ab-q_3+\choose a^2x_1-q_4x_1}x^3&{}+(b^2+2ac-q_2)x^2\\
&&{2ab-q_3+\choose a^2x_1-q_4x_1}x^3&{}-{2abx_1-q_3x_1\choose{}+a^2x_1^2-q_4x_1^2}x^2\\\hline
&&&{b^2+2ac-q_2+2abx_1\choose{}-q_3x_1+a^2x_1^2-q_4x_1^2}x^2&{}+(2bc-q_1)x\\
&&&{b^2+2ac-q_2+2abx_1\choose{}-q_3x_1+a^2x_1^2-q_4x_1^2}x^2&
{}-{b^2x_1+2acx_1-q_2x_1+ 2abx_1^2\choose-q_3x_1^2+a^2x_1^3-q_4x_1^3}x\\\hline
&&&&{2bc-q_1+b^2x_1+2acx_1-q_2x_1\choose+ 2abx_1^2-q_3x_1^2+a^2x_1^3-q_4x_1^3}x&{}+c^2-q_0\\
&&&&{2bc-q_1+b^2x_1+2acx_1-q_2x_1\choose+ 2abx_1^2-q_3x_1^2+a^2x_1^3-q_4x_1^3}x&{}-{2bcx_1-q_1x_1+b^2x_1^2+2acx_1^2-q_2x_1^2\choose+ 2abx_1^3-q_3x_1^3+a^2x_1^4-q_4x_1^4}\\\hline
R=&&&&&{c^2-q_0+2bcx_1-q_1x_1+b^2x_1^2+2acx_1^2\choose-q_2x_1^2+ 2abx_1^3-q_3x_1^3+a^2x_1^4-q_4x_1^4}
\end{array}</math>

The remainder is equal to the value of the resultant polynomial at the point ''x''<sub>1</sub>.

[[Image:Square dance equations solved.svg|frame|right]]
== 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 <ref>Borrowed perhaps from [[:Category:conic section cryptography]] but that is another matter.</ref> whose axis is parallel to the ''y''-axis, and otherwise to be determined.

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

:<math>P\oplus Q\oplus R\oplus S=O</math>

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

The equation of this parabola is known as the '''resolvent equation''' of the point group operation, and a '''resultant equation''' is determined whose roots are the four points of intersection of the resolvent parabolic trajectory with the quartic curve, called the '''solvend''' as it is the main equation to be solved, in ''y''<sup>2</sup>, for rational points which satisfy the point group operation.

Equations involving four distinct points are easiest, since any points of tangency require solving the '''gunners’ equations''' to fit parabolic trajectories, and these are much more difficult, as they inevitably involve derivatives, and are actually systems of differential equations, but are still essential to performing the point group operation over a quartic curve.

More general quartic curves in the plane might be met with more general conics having parallel axes to serve as resolvents, unless they are first brought into a canonical form in ''y''<sup>2</sup> by a conformal mapping, but be warned that the “group law” introduced by Bernstein, Edwards, Hamburg et al. for government-approved “elliptic” curve cryptography schemes [[Ed25519]] and [[Ed448]] promulgated <ref>There is language that the government does not wish to be inferred to say that it has '''“promulgated”''' various technical schemes and protocols as official internet standards, that is to say it published the schemes on a less formal “Request-For-Comment” or hats-off-for-the-ladies “RFC” basis only. The government with that language is attempting to slam the brakes on the train and stop short of a legal position of having '''“homologated”''' certain proposed cryptographic schemes and not others for use by the general public, as particularly in Europe that tends to imply an undue, unlawful or unconstitutional arbitrary rule-making authority on the part of undirected and meddlesome government officials in technical matters.</ref> in in official government standards such as [https://www.rfc-editor.org/rfc/rfc7748 RFC 7748], is essentially of the second degree only in character, and does not satisfy the proper resolvent equations for quartic curves which are not simply conics with squared coördinates.

== Additive inverses ==

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

:<math>P\oplus P\oplus Q\oplus Q=O</math>

where the resolvent parabola <math>y=ax^2+bx+c</math> is required to be '''tangent''' <ref>Latin for “touching.”</ref> to the original curve both at the point ''P'' = (''x''<sub>1</sub>,''y''<sub>1</sub>) and at the unknown point ''Q'' = (''x'',''y''). 

=== Another long division ===
We begin by dividing ''x''&nbsp;–&nbsp;''x''<sub>1</sub> into the quotient resulting from the previous division of the same binomial into the resultant polynomial.

<math>\begin{array}{r|rrrr}
&&(a^2-q_4)x^2&{}+{2ab-q_3+\choose 2a^2x_1-2q_4x_1}x&{}+{b^2+2ac-q_2+4abx_1\choose-2q_3x_1+3a^2x_1^2-3q_4x_1^2}\\\hline
x-x_1&(a^2-q_4)x^3&{}+{2ab-q_3+\choose a^2x_1-q_4x_1}x^2&{}+{b^2+2ac-q_2+2abx_1\choose{}-q_3x_1+a^2x_1^2-q_4x_1^2}x&{}+{2bc-q_1+b^2x_1+2acx_1-q_2x_1\choose+ 2abx_1^2-q_3x_1^2+a^2x_1^3-q_4x_1^3}\\
&(a^2-q_4)x^3&{}-(a^2x_1-q_4x_1)x^2\\\hline
&&{2ab-q_3+\choose 2a^2x_1-2q_4x_1}x^2
&{}+{b^2+2ac-q_2+2abx_1\choose{}-q_3x_1+a^2x_1^2-q_4x_1^2}x\\
&&{2ab-q_3+\choose 2a^2x_1-2q_4x_1}x^2
&{}-{2abx_1-q_3x_1\choose+2a^2x_1^2-2q_4x_1^2}x\\\hline
&&&{b^2+2ac-q_2+4abx_1\choose-2q_3x_1+3a^2x_1^2-3q_4x_1^2}x&{}+{2bc-q_1+b^2x_1+2acx_1-q_2x_1\choose+ 2abx_1^2-q_3x_1^2+a^2x_1^3-q_4x_1^3}\\
&&&{b^2+2ac-q_2+4abx_1\choose-2q_3x_1+3a^2x_1^2-3q_4x_1^2}x&{}-{b^2x_1+2acx_1-q_2x_1+4abx_1^2\choose-2q_3x_1^2+3a^2x_1^3-3q_4x_1^3}\\\hline
R=&&&&{2bc-q_1+2b^2x_1+4acx_1-2q_2x_1\choose +6abx_1^2-3q_3x_1^2+4a^2x_1^3-4q_4x_1^3}
\end{array}</math>
[[Image:Quartic point inverse.svg|frame|right|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.]]

This remainder, on dividing ''x''&nbsp;&ndash;&nbsp;''x''<sub>1</sub> into the resultant polynomial for the second time, is equal to the ''derivative'' of the original resultant at the point ''x''<sub>1</sub>, and may be set equal to zero as part of system of equations; there are many different ways to express the system of equations we need to solve, and this may not be the simplest.

=== The system of equations ===

In any case 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''<sub>4</sub>, ''q''<sub>3</sub>, ''q''<sub>2</sub>, ''q''<sub>1</sub>, ''q''<sub>0</sub>, ''x''<sub>1</sub>, ''y''<sub>1</sub> and ''y''<sub>1</sub>’ may be derived most simply by passing the parabola through the point (''x''<sub>1</sub>,''y''<sub>1</sub>) with a slope or derivative of ''y''<sub>1</sub>’ at that point, and then setting both the quotient from the last division and its derivative equal to zero at the point (''x'',''y'').


<math>\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^2x_1-2q_4x_1}x+{b^2+2ac-q_2+4abx_1\choose-2q_3x_1+3a^2x_1^2-3q_4x_1^2}&=&0\\
2(a^2-q_4)x+2ab-q_3+2a^2x_1-2q_4x_1&=&0\\
\end{array}</math>

where

:<math>\begin{array}{rcl}
y_1&=&\pm\sqrt{q_4x_1^4+q_3x_1^3+q_2x_1^2+q_1x_1+q_0}\\
y_1'&=&\dfrac{\pm\left(4q_4x_1^3+3q_3x_1^2+2q_2x_1+q_1\right)}{2\sqrt{q_4x_1^4+q_3x_1^3+q_2x_1^2+q_1x_1+q_0}}
\end{array}</math>

These equations result from setting both a simplified resultant and its derivative equal to zero at points of tangency both at the known point ''x''<sub>1</sub> and at the unknown point ''x'' we seek. The residuals from this system of four equations are shown below, as very nearly solved numerically, from the data plotted on the chart to the right with ''x''<sub>1</sub>&nbsp;=&nbsp;2, ''x''&nbsp;=&nbsp;–2.4, and ''a''&nbsp;=&nbsp;0.2 as an example on the same quartic curve as pictured above.

[[Image:Quart-max.png]]
<syntaxhighlight style="clear:both;" lang="R">
> 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
</syntaxhighlight>

The term of ''a''<sup>2</sup>''x''<sup>2</sup>, 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.

<math>\begin{array}{rcl}
2(a^2-q_4)x^2+2{2ab-q_3+\choose 2a^2x_1-2q_4x_1}x+2{b^2+2ac-q_2+4abx_1\choose-2q_3x_1+3a^2x_1^2-3q_4x_1^2}&=&0\\
2(a^2-q_4)x^2+2abx-q_3x+2a^2x_1x-2q_4x_1x&=&0\\\hline
{2ab-q_3+\choose 2a^2x_1-2q_4x_1}x+2{b^2+2ac-q_2+4abx_1\choose-2q_3x_1+3a^2x_1^2-3q_4x_1^2}&=&0
\end{array}</math>

Replace the third equation:

<math>\begin{array}{rcl}
ax_1^2+bx_1+c-y_1&=&0\\2ax_1+b-y_1'&=&0\\
{2ab-q_3+\choose 2a^2x_1-2q_4x_1}x+2{b^2+2ac-q_2+4abx_1\choose-2q_3x_1+3a^2x_1^2-3q_4x_1^2}&=&0\\
2(a^2-q_4)x+2ab-q_3+2a^2x_1-2q_4x_1&=&0\\
\end{array}</math>

The first two of these equations can be solved for ''b'' and ''c'' and the resulting substitutions, <math>b=y_1'-2ax_1</math> and <math>c=y_1+ax_1^2-x_1y_1'</math> made in the third and fourth equations.

<math>\begin{array}{rcl}
{2a(y_1'-2ax_1)-q_3\choose+2a^2x_1-2q_4x_1}x+2{(y_1'-2ax_1)^2+2a(y_1+ax_1^2-x_1y_1')-q_2+\choose 4a(y_1'-2ax_1)x_1-2q_3x_1+3a^2x_1^2-3q_4x_1^2}&=&0\\
2(a^2-q_4)x+2a(y_1'-2ax_1)-q_3+2a^2x_1-2q_4x_1&=&0\\
\end{array}</math>

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

<math>{2a(y_1'-2ax_1)-q_3\choose{}+2a^2x_1-2q_4x_1}^2
-4(a^2-q_4){(y_1'-2ax_1)^2+2a(y_1+ax_1^2-x_1y_1')-q_2+\choose 4a(y_1'-2ax_1)x_1-2q_3x_1+3a^2x_1^2-3q_4x_1^2}=0</math>

Begin multiplying out the terms.

<math>{2ay_1'-4a^2x_1-q_3\choose{}+2a^2x_1-2q_4x_1}^2
-4(a^2-q_4){y_1'^2-4ax_1y_1'+4a^2x_1^2+2ay_1+2a^2x_1^2-2ax_1y_1'\choose -q_2+4ax_1y_1'-8a^2x_1^2-2q_3x_1+3a^2x_1^2-3q_4x_1^2}=0</math>


[[Image:Gunners’ equations.svg|frame|right|The parabolic trajectory <math>y=ax^2+bx+c</math> is solved for parameters ''a'', ''b'' and ''c'', and the point (''x'',''y'') is found from the given point (''x''<sub>1</sub>,''y''<sub>1</sub>) where ''x''<sub>1</sub>&nbsp;=&nbsp;‑''π''.]]

<math>{2ay_1'-2a^2x_1\choose{}-q_3-2q_4x_1}^2
-4(a^2-q_4){y_1'^2+a^2x_1^2+2ay_1-2ax_1y_1'\choose -q_2-2q_3x_1-3q_4x_1^2}=0</math>

<math>\begin{align}
-8y_1&a^3\\
{}+(24q_4x_1^2 + 12q_3x_1 + 4q_2 - 4y_1^2 + 4y_1'^2)&a^2\\
{}+(8q_4y_1 - 16q_4x_1y_1' - 4q_3y_1')&a\\
{} + q_3^2 - 4q_4q_3x_1 -8q_4^2x_1^2 +4q_4y_1'^2 - 4q_4q_2 &\quad=0
\end{align}</math>

This equation is solved numerically in <big>'''[https://www.r-project.org/ R]'''</big>, and the first solution for ''a'' found by R’s <tt><span style="color:blue">polyroot</span>()</tt> function is verified to satisfy the resolvent quadratic equations and their derivatives, collectively known as the '''gunners’ equations''', with very small residuals both at the given point ''x''<sub>1</sub> and at the point ''x'' which is derived from ''a'' when the cubic equation is solved.

<p style="overflow:auto;border:1pt solid;background-color:#8080ff">There is much unwritten history on these equations dating back to the Civil War in the United States. While the white Confederate belles were square-dancing with the gentlemen of the district, at formal balls catered by their black slaves, the Union railroad engineers and military officers were hard at work solving the gunners’ equations for the trajectories of cannonballs and artillery shells. And even at times of peace, nobody had ever heard of a square dance hall where gentlemanly duels and gunfights didn’t take place on a regular basis. Later on of course, Albert Einstein continued in the long tradition of gunners solving mathematical equations, to great and devastating effect on two particular Japanese small-town red-light disticts.</p>

The [[discriminant]] of the cubic equation for ''a'' turns out to be equal to zero, and the equation has both a single root and a double root; only the single root is useful for determining the point of tangency (''x'',''y'') we seek. By altering ''a'' slightly it must be possible to either overshoot or undershoot the solution slightly, and a double root must be cancelled out.

== Point averaging ==

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

:<math>P\oplus Q\oplus R\oplus R = O</math>

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: <math>\frac{P\oplus Q}2=-R</math>.

== Point trebling ==

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

:<math>P\oplus P\oplus P\oplus Q=O</math>

and then take the inverse of ''Q'' to find <math>3P=-Q</math>. Here the parabola is required to '''osculate''' <ref>Latin for “kiss.” The  ''y''-coördinate and the first and second derivatives must be equal for the two curves which are said to ''osculate'' at that ''x''-coördinate.</ref> 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''.

:<math>P\oplus Q\oplus Q\oplus Q=O</math>.

Now take the inverse of ''Q'' to find <math>\frac P3=-Q</math>.

== Point doubling ==

Point doubling is performed by trebling and then averaging

:<math>2P = \frac{P\oplus 3P}2</math>.

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

:<math>2P = -\left(\frac{-P\oplus(-3P)}2\right).</math>

== Point bisection ==

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

:<math>\frac12P = \frac{2P\oplus(-P)}2</math>

== Point group addition ==

:<math>P\oplus Q=\dfrac{\left(\dfrac{P\oplus Q}2\right)\oplus 3\left(\dfrac{P\oplus Q}2\right)}2</math>

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 [[height]]s 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 ==
<syntaxhighlight lang="R" line="1">
#! /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)
</syntaxhighlight>