[Cryptography] Existence of point of order 4 in a Montgomery curve and its quadratic twist

Viktor Dukhovni cryptography at dukhovni.org
Tue Feb 13 15:19:52 EST 2018



> On Feb 12, 2018, at 6:38 PM, Ondrej Mikle <ondrej.mikle at gmail.com> wrote:
> 
> owever in the proof, it mentions that both the curve and its twist have
> subgroup that is isomorphic to Z/2Z x Z/2Z.
> 
> But a property of group isomorphism states that:
> 
> "If (G, *) is a group that is isomorphic to (H, .) [where f is the isomorphism],
> then if a belongs to G and has order n, then so does f(a)"
> 
> Shouldn't it mean that either both curve and its twist contain a point of order
> 4, or at least one doesn't have a subgroup isomorphic to Z/2Z x Z/2Z?

No.  Z/2Z x Z/2Z has no elements of order 4, it has 3 elements of order 2, and
the identity.  The element of order 4 in whichever group has one is not a member
of this subgroup.  The subgroups in question were just used to establish that
the order of both groups is divisible by 4, so given the sum of their orders
one has order 4 mod mod 8 and the other order 0 mod 8.

The group with order 4 mod 8 is Z/2Z x Z/2Z x "odd-order", so has no
order 4 elements.  Now you just need to observe why the group whose order
is divisible by 8 must have an order 4 element.  This is not explained,
and relies on a non-trivial result about elliptic curves.

The reason is that an elliptic curve can have at most 3 points of order
2 (elements of order n are found in a subgroup of Z/nZ x Z/nZ) while
Z/2 x Z/2 x Z/2 has 7 elements of order 2, and so can't occur.  Thus,
Z/2 x Z/2 x Z/2 is ruled out as a subgroup of order 8, but a subgroup
of order 8 must exist to yield 0 mod 8 for the group order.  Therefore,
there must be an element of order 4 for the group to have order
divisible by 8.

-- 
	Viktor.



More information about the cryptography mailing list