3
$\begingroup$

I read that non-primes only have co-factors, but Edwards have a co-factor and it is defined over Fp s.t. P = 2^255 -19 which is prime right?

How is the co-factor created, some have co-factor 4 and some have co-factor 8?

Am I right in saying that P256 for example, has no co-factor because it is of prime order?

I have seen a Twisted Edwards Curve with prime order, but also had a co-factor, was I mistaken?

I have also seen the case where co-factor = 1. This is strange because in order to make sure that the value is in the subgroup, we must multiply it by the co-factor. If co-factor is 1, then this is irrelevant.

Improve this question
$\endgroup$
  • $\begingroup$ Unless all curves have co-factors and the ones with prime fields have co-factor = 1. Still does not explain how the small sub groups arise though $\endgroup$ – WeCanBeFriends Jan 12 '19 at 20:51
1
$\begingroup$

I will attempt to answer some parts of my own question.

Short answer: All of them.

We define curves over Fields which have size n. We then operate in some subgroup of it, which has size/order r.

The cofactor is calculated by doing n/r . if the cofactor is equal to 1, then it means that n = r and the subgroup is equal to the whole field.

I would like to say by intuition that this means that since the co-factor is an integer. If n is prime, then the co-factor is either n or 1. The case where the co-factor is n means that the subgroup has one element. Could this be the empty set? or just the neutral element?

The case where the co-factor is one would be the only logical or useful case, which means that the subgroup is equal to the order of the field. My intuition tells me that every prime field would therefore creator subgroups that are equal to it's size.

If n is not prime, then this means that there are other numbers that it can divide by. 8 and 4 seem to be special numbers.

I would like to say that we the 8 and 4, or any multiple of two, pops up because these curves normally have orders of 2^m.

h = 2^m / r => r must be even and so must h. Does this imply that h must be a multiple of 2?

Yes. h*r = 2^m => that h and r must be multiples of 2.

I've not seen curves with odd primes, however I do not see any reason for there to not be any.

I have seen a Twisted Edwards Curve with prime order, but also had a co-factor, was I mistaken?

From my deduced understanding, it must have had a order that was 2^m.

I read that non-primes only have co-factors, but Edwards have a co-factor and it is defined over Fp s.t. P = 2^255 -19 which is prime right?

A quick google search would have shown that this number ended in 6 and so is even.

Am I right in saying that P256 for example, has no co-factor because it is of prime order?

Co-factor is one.

How is the co-factor created, some have co-factor 4 and some have co-factor 8?

I explained this part above where they have an order of 2^m

I'm not quite clear on how to find a G s.t. it has a small subgroup and I am not sure how multiplying a point by the co-factor "puts it in the subgroup" . Will open another question for this.

Improve this answer
$\endgroup$
  • $\begingroup$ When I refer to subgroup; am I right in saying that it is a "part of the curve" while the initial field Fp describes the whole curve? $\endgroup$ – WeCanBeFriends Jan 12 '19 at 21:15
  • 1
    $\begingroup$ "We define curves over Fields which have size n"; that's misleading - we define a curve over a finite field that has $p^k$ elements (for a prime $p$ and an integer $k$); however that's not what we're talking about. What we are talking about is the number of points $n$ on the curve, and $n$ is typically not $p^k$ (although it is always "close") $\endgroup$ – poncho Feb 11 '19 at 22:50
  • $\begingroup$ @poncho So the field has size p^k, but not every point in the field will correspond to a point on the curve? Although it should be close. We don't care about how many points are in the field, namely p^k, we care about how many points are also points on the curve. Is this correct?.. So there is Fp; all possible points in field E(Fp) All possible points over Fp $\endgroup$ – WeCanBeFriends Feb 12 '19 at 15:13
  • $\begingroup$ Actually, a point on the curve corresponds to two field elements (conventionally $x, y$) that are a solution to a specific equation (general form for $p>3$: $y^2 \equiv x^3 + ax + b$ within the field, for some constants $a, b$). Oh, they's also a point called 'point at infinity' that doesn't actually correspond to a solution. $\endgroup$ – poncho Feb 12 '19 at 15:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.