How to determine whether a point is at infinity in homogenous coordinates?

DannyNiu

5/14/23, 9:04 AM

I'm implementing ECC in my spare time project. I'm referencing RFC-6090 for point arithmetic algorithm over homogeneous coordinates.

In Appendix F subsection 2, there are 5 case labels when determining which formula to use depending on how many if any point-at-infinity exists in operands. For me, implementing these case labels in constant-time isn't too big a problem, but I'm not too sure about determining whether a point is at infinity.

When the point-at-infinity occurs within point arithmetic, it has the homogeneous coordinates $(0,y,0)$ where $y\ne 0$. So Q: is it sufficient to check $Z = 0$ for point at infinity, or all 3 dimensions has to be checked?

0 + 0

implementation

elliptic-curves

Score:3

Crypto

kelalaka

5/14/23, 3:08 PM

In homogenous coordinates, we have the equivalence relation as $(X, Y, Z) \sim (\lambda X, \lambda Y, \lambda Z)$ where $\lambda \neq 0$.

if $Z \neq 0$ then we can convert $(X, Y, Z)$ into the affine point as $(X/Z,Y/Z)$ ( notice that $\lambda$s cancels)
if $Z = 0$ then with the equivalence class definition $(\lambda X, \lambda Y, 0)$ all represents the point at infinity. I.e. $$(x,y,0)\sim(2x,2y,0)\sim(-x,-y,0)$$

Therefore, when one sees $Z=0$ in the projective coordinates it is the point at infinity.

And, if the affine point $(0,0)$ doesn't satisfy the curve equation, i.e. $b \neq 0$ in the short Weierstrass $y^2 = x^3 + ax +b$, then it is a good place to store the point at infinity in the affine coordinates where normally it doesn't have a representation.

Note that it is common to use $(X: Y: Z)$ notation for homogenous coordinates, that I did not use here.

0 + 0

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: How to determine whether a point is at infinity in homogenous coordinates?

TH: จะทราบได้อย่างไรว่าจุดที่ไม่มีที่สิ้นสุดในพิกัดที่เป็นเนื้อเดียวกัน?

RO: Cum se determină dacă un punct este la infinit în coordonate omogene?

RU: Как определить, удалена ли точка на бесконечность в однородных координатах?

VI: Làm cách nào để xác định xem một điểm có ở vô cực trong tọa độ đồng nhất không?

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.