# Can I move elements from cyclic subgroup to its cyclic parent group?

The following context is based on elliptic curves in short-weierstrass form y^2 = x^3 + b.

I know that elements of a non-prime order cyclic group G can be moved to its subgroup H by a process called "cofactor clearing". You just have to simply multiply a cofactor by an element of main group that ends up giving an element in its subgroup. Example given on- Why such a complicated way of cofactor clearing?

I want to know if there's a way/formula/algorithm for we can do the things in opposite, i.e., "moving elements from cyclic subgroup to its cyclic parent group" such that we get elements which belong to the parent group (respecting group laws ofc). I have tried taking (cofactor^-1) but didn't work.

NOTE: homomorphism should not be used as it would map the element of subgroup order to an element of same subgroup order. Here we want element of parent group order.

If someone can help me with this (with a good example) would be really appreciated...

EDIT: Let me clarify what I am looking for in a simple terms, pls read carefully - I need a formula that can be applied on any curve, say for e.g. y^2 = x^3 + 2 with prime = 157, parent group order = 172 and subgroups = 4 x 43. Suppose I have a random generator point "A" (on subgroup 43) and multiply it with some unknown scalar k that gives point "B" (on subgroup 43). So how should I get resulting points A' and B' on parent group G having order 172 keeping the scalar k preserved (and unknown)? A SAGE code would be helpful. You can think of a mapping of two points A and B H→G where all properties are preserved along with scalar mult. but the resulting points A' and B' have to belong to the parent group G (which has order 172) respecting scalar k.

• The most obvious meaningful way is contruct $C\cong C_n\times C_p$ where $C_n$ and $C_p$ are cylic. Find their smallest generator, and map it to the smallest generator of the $C$ Sep 22 at 11:18
• @kelalaka Say we have two points A and B in subgroup Cn, where A is a random generator point and B is its additive element. How can I move these points to parent group C such that the resulting points A' and B' have order of C, not Cn ? Sep 22 at 12:57
• @Josh666: Please clarify if in this verbatim extract of revision 4 of the question: "resulting points A' and B' on parent group having order 172", the member of phrase "having order 172" applies (1) to the " parent group"; or (2) to the "points A' and B'". That's not the same!
– fgrieu
Sep 23 at 9:48
• "having order 172" means A' and B' are the resulting points on parent group G and their group orders are 172 means A' ∈ G and B' ∈ G. Sep 23 at 9:51
• @fgrieu pls continue this discussion on crypto.stackexchange.com/questions/108069/…. I have highlighted main terms there. Sep 23 at 11:00

Consider the Ed25519 curve, which has a co-factor of 8. The prime-order group has the order $$\ell=2^{252} + 27742317777372353535851937790883648493$$. The total number of points on the curve is $$8\ell$$.

If you take random points on the curve and multiply them by $$\ell$$, you will find that you only get 8 possible resulting points. In hex, their compressed representations are as follows:

1: c7176a703d4dd84fba3c0b760d10670f2a2053fa2c39ccc64ec7fd7792ac03fa
2: 0000000000000000000000000000000000000000000000000000000000000000
3: 26e8958fc2b227b045c3f489f2ef98f0d5dfac05d3c63339b13802886d53fc85
4: ecffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f
5: 26e8958fc2b227b045c3f489f2ef98f0d5dfac05d3c63339b13802886d53fc05
6: 0000000000000000000000000000000000000000000000000000000000000080
7: c7176a703d4dd84fba3c0b760d10670f2a2053fa2c39ccc64ec7fd7792ac037a
8: 0100000000000000000000000000000000000000000000000000000000000000


You may recognize that the 8th item is the identity element for the Ed25519 prime-order group.

If you take the 1st point and add it to itself, you get the 2nd point. If you keep adding the 1st point, you'll get all of the remaining points.

To know if you have a point in the prime-order group, you multiply it by $$\ell$$ and check that the answer is the 8th point. No matter what you multiply a point in the prime-order group by, it'll stay in the prime-order group.

To knock a point out of the prime-order group, all you have to do is add the 1st point to it.

• thx for answer. I will try this and let you know if it works for me. Sep 22 at 14:19
• Does this method preserve scalar multiplication? Like I took a random generator point "A" (on prime-order subgroup ℓ) and multiply it with scalar k = 15 that gives point "B". Will the resulting points A' and B' on parent group 8ℓ preserve scalar k = 15? Please let me know. Sep 22 at 14:48
• @Josh666 think of a point in the prime-order group as a multiple of $8\Delta$, where $\Delta$ is the 1st point in the list (c717...03fa). If you have a random point $A$ in the prime-order group, then $A=a8\Delta$ for some value of $a$. If you knock it out of that group, you have e.g. $A'=a8\Delta+\Delta$. This means that if you have $B=15A$ and $B'=15A'$, then $B'=B+15\Delta=15a8\Delta+15\Delta$. This is why you can "clear the cofactor" by ensuring that you scalar multiply by a multiple of 8, because it means the resulting point must be of the form $P=x8\Delta$ Sep 22 at 15:31
• What if scalar of A and B is unknown? will this work? Or is there some other way to move points without needing scalar for subgroup to parent group map? Sep 22 at 16:03
• @Josh666 You can add $\Delta$ to any point in the prime-order group to bump it out of the prime-order group Sep 22 at 16:07

Assuming that by

keep the scalar preserved

you mean: $$B=k*A \implies B'=k*A'$$ then the map must include the value of $$k$$.

Reasoning: an element of the larger group can be written as addition of points on the smaller groups. So that $$A'=A+C$$, multiplying by $$k$$ will give $$kA+kC$$ so in order to maintain your property on $$B=kA$$ you should add $$kC$$ to it. $$B'=kA+kC$$.

Since $$C$$ has small order $$n$$ you can do that scalar multiplication just by $$k \mod n$$

This will work as map, see the following sage script for an example curve of order 3*61 (as the curve you proposed doesn't really work as there is no element with order 172)

#define the elliptic curve
ec = EllipticCurve(GF(157),[0,11])
#compute its order
print (ec.order(), factor(ec.order()))
#take a generator and verify its order is the cardinality of the curve
Gall=ec.gens()
assert (Gall.order()==ec.cardinality())
#derive A as generator of the larger subgroup
A = 3*Gall
print ("A's order = ", A.order())
#derive C as generator of the smaller subgroup (of order 3)
C = Gall*61
print ("C's order = ",C.order())
for k in range(1,A.order()-1):
B = k*A
Ap = A + C
Bp = B + k*C
assert k*Ap == Bp


On the security side it depends on what you disclose because if you disclose $$A$$ and $$A'$$ an attacker can easily recover $$C$$ and the value of $$k$$ modulo the smaller subgroup's order.

• check new question with new params here. Oct 26 at 16:39