<p>I was wondering if there was a quick way to check that the group underlying the elliptic curve secp256k1 was indeed cyclic with the usual point <code>G</code> a generator. I am given the prime number underlying the field <code>Fp</code>, I am given the point <code>G</code>, I am given the integer <code>order</code>which is presented as the order of the curve. I can check that the scalar multiplication <code>order.G</code> yields the <code>infinity</code> point. So I know that the order of <code>G</code> (i.e. the cardinal of its generated subgroup) divides <code>order</code>. I can check that <code>order</code> is a probable prime. So I reach the conclusion that the order of <code>G</code> is indeed <code>order</code>. But how do I know its generated subgroup is the whole elliptic curve?</p>

<pre><code>import java.math.BigInteger;
import org.bitcoinj.core.ECKey;
import org.spongycastle.math.ec.ECCurve;
import org.spongycastle.math.ec.ECPoint;


public class Test {
  public static void main(String[] args){

  // secp256k1 elliptic curve
  ECCurve curve = ECKey.CURVE.getCurve();

  // the order of the curve
  BigInteger order = curve.getOrder();

  // fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
  System.out.println(order.toString(16));

  // The generator of the curve
  ECPoint G = ECKey.CURVE.getG();
  BigInteger X = G.getAffineXCoord().toBigInteger();
  BigInteger Y = G.getAffineYCoord().toBigInteger();

  // 79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
  System.out.println(X.toString(16));

  // 483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
  System.out.println(Y.toString(16));


  // Computing scalar multiplication order.G
  ECPoint test = G.multiply(order);

  System.out.println(test.isInfinity());  // true

  // so we know the order of G (i.e. the cardinal of its
  // generated subgroup) divides 'order'. However:

  System.out.println(order.isProbablePrime(128)); // true

  // and G is not infinity. So the order of G is precisely order.
  // How do I check that the subgroup generated by G is actually 
  // the whole elliptic curve group, i.e. that the cofactor is 1?
  }
}
</code></pre>

CC BY-SA 3.0
2016-08-25T20:01:48.093Z
The generated subgroup is a set of size `order`, contained in the curve group which is also of size `order`.  So they must be equal. ...?
Nate Eldredge
CC BY-SA 3.0
2016-08-25T20:04:31.237Z
I was trying to justify the fact the curve group was of the same size (i.e. not bigger)
Sven Williamson
CC BY-SA 3.0
2016-08-25T20:06:32.007Z
Wasn't `order` *defined* to be the size of the curve group?
Nate Eldredge
CC BY-SA 3.0
2016-08-25T20:10:05.637Z
The library says it is. It is spitting out a number and a point `G`. I can check that this number is indeed the order of `G`. But I wanted also to check that it had to be the size of the whole curve.
Sven Williamson
CC BY-SA 3.0
2016-08-25T20:36:35.927Z
Given that the curve order is prime, the only possibilities for the cofactor (which must be a divisor of the curve order) are 1 and the order itself.
Pieter Wuille
CC BY-SA 3.0
2016-08-25T21:15:01.723Z
The curve is a subset of the cartesian product `FpxFp` (to which has been added the infinity point). I know that `p` is prime, I know that if a non-zero element of `Fp` has a square-root, then it has 2 square-roots. But I don't know why the curve order should be prime. Do I need to go through lectures notes on EC theory, or is there a simple argument?
Sven Williamson
CC BY-SA 4.0
2020-10-25T20:49:31.390Z
As said by Pieter, the secp256k1 curve has prime order, thus by applying [Lagrange's theorem](https://en.wikipedia.org/wiki/Lagrange%27s_theorem_(group_theory)), you deduce that there are no subgroups. As a consequence, all group elements (except the infinity point) are primitive.
Jean Monet
<bitcoinj><secp256k1>
Can I quickly check the cofactor of secp256k1 is 1
Sven Williamson
# Can I quickly check the cofactor of secp256k1 is 1

(Asked by: username_0 on 2016-08-25)

I was wondering if there was a quick way to check that the group underlying the elliptic curve secp256k1 was indeed cyclic with the usual point G a generator. I am given the prime number underlying the field Fp, I am given the point G, I am given the integer orderwhich is presented as the order of the curve. I can check that the scalar multiplication order.G yields the infinity point. So I know that the order of G (i.e. the cardinal of its generated subgroup) divides order. I can check that order is a probable prime. So I reach the conclusion that the order of G is indeed order. But how do I know its generated subgroup is the whole elliptic curve?
import java.math.BigInteger;
import org.bitcoinj.core.ECKey;
import org.spongycastle.math.ec.ECCurve;
import org.spongycastle.math.ec.ECPoint;


public class Test {
  public static void main(String[] args){

  // secp256k1 elliptic curve
  ECCurve curve = ECKey.CURVE.getCurve();

  // the order of the curve
  BigInteger order = curve.getOrder();

  // fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
  System.out.println(order.toString(16));

  // The generator of the curve
  ECPoint G = ECKey.CURVE.getG();
  BigInteger X = G.getAffineXCoord().toBigInteger();
  BigInteger Y = G.getAffineYCoord().toBigInteger();

  // 79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
  System.out.println(X.toString(16));

  // 483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
  System.out.println(Y.toString(16));


  // Computing scalar multiplication order.G
  ECPoint test = G.multiply(order);

  System.out.println(test.isInfinity());  // true

  // so we know the order of G (i.e. the cardinal of its
  // generated subgroup) divides 'order'. However:

  System.out.println(order.isProbablePrime(128)); // true

  // and G is not infinity. So the order of G is precisely order.
  // How do I check that the subgroup generated by G is actually 
  // the whole elliptic curve group, i.e. that the cofactor is 1?
  }
}

**Tags:** bitcoinj, secp256k1

> **Comments:**
> **username_1**: The generated subgroup is a set of size `order`, contained in the curve group which is also of size `order`.  So they must be equal. ...?  
> **username_0**: I was trying to justify the fact the curve group was of the same size (i.e. not bigger)  
> **username_1**: Wasn't `order` *defined* to be the size of the curve group?  
> **username_0**: The library says it is. It is spitting out a number and a point `G`. I can check that this number is indeed the order of `G`. But I wanted also to check that it had to be the size of the whole curve.  
> **username_2**: Given that the curve order is prime, the only possibilities for the cofactor (which must be a divisor of the curve order) are 1 and the order itself.  
> **username_0**: The curve is a subset of the cartesian product `FpxFp` (to which has been added the infinity point). I know that `p` is prime, I know that if a non-zero element of `Fp` has a square-root, then it has 2 square-roots. But I don't know why the curve order should be prime. Do I need to go through lectures notes on EC theory, or is there a simple argument?  
> **username_3**: As said by Pieter, the secp256k1 curve has prime order, thus by applying [Lagrange's theorem](https://en.wikipedia.org/wiki/Lagrange%27s_theorem_(group_theory)), you deduce that there are no subgroups. As a consequence, all group elements (except the infinity point) are primitive.  

---

## 0 answers

