answering machine:

When working with elliptic curves like secp256k1, and considering higher-level endomorphic rings or subgroups of specific order (e.g., 149 or 631), you're dealing with subgroups of the elliptic curve group
𝐸
(
𝐹
𝑝
)
E(F
p
​
 ). Determining whether two points lie in the same subgroup without exhaustively generating the subgroup is a subtle but important question.

Let’s break it down and clarify whether there’s a "quick trick" based solely on
(
𝑥
,
𝑦
)
(x,y) of the points.

✅ What You’re Asking:
Can you quickly determine if two points
𝑃
P and
𝑄
Q on secp256k1 lie in the same subgroup of a given order, like 149 or 631, just by looking at
𝑃
=
(
𝑥
1
,
𝑦
1
)
P=(x
1
​
 ,y
1
​
 ) and
𝑄
=
(
𝑥
2
,
𝑦
2
)
Q=(x
2
​
 ,y
2
​
 )?

🔍 Short Answer:
No, you cannot definitively determine if two points lie in the same subgroup just by their
𝑥
,
𝑦
x,y coordinates without further computation.
However, there are efficient algebraic techniques (better than full subgroup enumeration) to test subgroup membership.

🧠 Conceptual Explanation:
1. Elliptic Curve Group Structure:
For a curve like secp256k1, the full curve group
𝐸
(
𝐹
𝑝
)
E(F
p
​
 ) is a large cyclic (or nearly cyclic) abelian group. It can be decomposed into subgroups of different orders.

The endomorphism ring refers to the set of algebraic maps from the curve to itself that preserve structure.

Higher-level endomorphic rings like order 149 or 631 refer to small cyclic subgroups inside the full group.

2. Subgroup Membership Test:
To check whether
𝑃
∈
𝐺
P∈G, where
𝐺
G is a subgroup of known order
𝑛
n, do:

[
𝑛
]
𝑃
=
𝑂
[n]P=O
If true, then
𝑃
∈
𝐺
P∈G.
This is fast with scalar multiplication, especially for small
𝑛
n like 149 or 631.

So if you want to check whether both
𝑃
P and
𝑄
Q are in subgroup of order 149:

text
Kopioi
Muokkaa
Is [149]P = O?
Is [149]Q = O?
If both are, then they lie in the subgroup of order 149 (they may still generate different cyclic subgroups within, though).

3. Using Discrete Logs / Cosets:
If you know a generator
𝐺
G of the subgroup, then:

You can express each point
𝑃
=
[
𝑘
]
𝐺
P=[k]G.

Then points that are scalar multiples of each other lie in the same cyclic subgroup.

But solving for
𝑘
k requires solving the discrete logarithm problem (DLP), which is hard even for small groups unless you brute force or use baby-step giant-step.

4. No Visual Trick from (x, y):
There is no visual or quick coordinate-only check that will tell you definitively whether two points lie in the same subgroup of order 149 or 631 — those coordinates can be totally arbitrary even within the same subgroup.

Even worse: many
𝑥
x-coordinates may correspond to points in different subgroups depending on
𝑦
y, and the same point can belong to multiple subgroups if those subgroups intersect.

✅ Practical Method to Check Subgroup Membership
Given a point
𝑃
P, and a subgroup order
𝑛
n:

python
Kopioi
Muokkaa
def is_in_subgroup(P, n):
    return n * P == INFINITY
And to check whether two points lie in the same subgroup:

python
Kopioi
Muokkaa
def are_in_same_subgroup(P, Q, n):
    return n * P == INFINITY and n * Q == INFINITY
If you want to go further (e.g., check if they generate the same cyclic subgroup), you’d need to:

Confirm both are in the subgroup.

Compute
𝑑
=
gcd
⁡
(
𝑘
𝑃
,
𝑘
𝑄
,
𝑛
)
d=gcd(k
P
​
 ,k
Q
​
 ,n), where
𝑃
=
[
𝑘
𝑃
]
𝐺
P=[k
P
​
 ]G,
𝑄
=
[
𝑘
𝑄
]
𝐺
Q=[k
Q
​
 ]G, and
𝐺
G is a known generator.

But again, solving for
𝑘
𝑃
k
P
​
  and
𝑘
𝑄
k
Q
​
  requires solving discrete logs.

🧩 Bonus: Trick Using Pairings (Not Available on secp256k1)
On pairing-friendly curves (e.g., BLS12-381), you can sometimes use pairings to test subgroup membership efficiently. But secp256k1 is not pairing-friendly, so this trick doesn't apply.