Please provide an option for computing curves containning a specific order

[ytrezq]

Mixed with specific parameter like finding a supersingular curve, it can be challenging to find a curve with a given order.

Instead, please provide an option for finding a curve whose order s factor contains a specific Integer.

[J08nY]

This can be tricky. Combining the CM method with requesting other specific properties of the curves is not easy (or sometimes even possible).

Would this work for your use case: dcb4245? You can specify the curve order as a list of factors.

[ytrezq]

@J08nY what I m looking about is to compute an anomalous or supersingular curve with a given order.

I can also accept the order to have a specific prime factor. With the other prime factor allowed to be random.

[ytrezq]

https://www.worldscientific.com/doi/pdf/10.1142/S1793042117500099

[J08nY]

I just found out that you can generate a supersingular curve for a given prime (and thus by definition a given order).
Simply run:

ecgen --supersingular --fp <bitsize>
[
p: <enter the prime, in base 10 or base 16 as 0x...>

Then, when you get prompted for the prime p you simply enter it and get the curve.
This is because the method used is from CONSTRUCTING SUPERSINGULAR ELLIPTIC CURVES from Broker which allows for such flexibility.

For the anomalous case I am not sure there is a viable algorithm (at least I haven't seen it published). If you have $4n - 1$ with a very small squarefree part you would be able to do it with the CM method.

[ytrezq]

A bitsize isn’t the same thing as a specific given prime. And even then, the problem is if you generate a degree 12 curve for large characteristics, then the resulting curve is secure against the DLP whereas I want to attack ECDLP. Or can you provide a way to generate curves embedding degrees equal to 3 or 6 please ?

[J08nY]

You can enter the specific given prime. Just not as a command-line argument but interactively once ecgen starts executing. Try it out. Something like this also works

echo -n "11" | ./ecgen --fp --supersingular 32

generates a 32 bit supersingular curve with prime = 11 (and order = 12), which is not really 32 bits, that is just the upper bound in this case. So just pick a larger prime and generate away :)

Or can you provide a way to generate curves embedding degrees equal to 3 or 6 please ?

Hmm, for this I would go the way of known curve families, like BN, BLS, MNT or KSS. You can find more about them (and generating Python code) here: https://neuromancer.sk/std/methods/bn/

[ytrezq]

Hmm, for this I would go the way of known curve families, like BN, BLS, MNT or KSS. You can find more about them (and generating Python code) here: https://neuromancer.sk/std/methods/bn/

But then the prime curve doesn t contains the order I want. I m thinking about both having a specific order and a lower embedding degree than 12.
Also, how to compute the prime from the would be order? Doesn t thid means finding a divisor of p¹²-1?

[J08nY]

But then the prime curve doesn t contains the order I want. I m thinking about both having a specific order and a lower embedding degree than 12.

I know of no method that would get you that, sorry.

Also, how to compute the prime from the would be order? Doesn t thid means finding a divisor of p12-1?

For curves from the mentioned families you go the other way, pick an integer $z$ (usually randomly) until both the values $p(z)$ and $r(z)$ are prime (as defined in the link) and then either construct using CM or by picking random coefficient $b$ until you reach the target curve. So you do not have full control over the order (or prime). I mean if you have some freedom in choosing the order you can iterate over its possibilities and check whether $r(z) - order$ has an integer root. If it has, you can use it in place of $z$ and continue as described.

[J08nY]

I just discovered this repo: https://github.com/scipr-lab/ecfactory that seems like it implements a bunch of stuff you are interested in.

[ytrezq]

@J08nY I’m only interested in specific things. I don’t see it implement anything that I asked for here.

[J08nY]

I'm sorry then, you can implement it yourself.

[ytrezq]

I lack the knowlwedge to understand most mathematical notations. So I can’t