Targeted finite fields

[dlesnoff]

I am doing a state-of-the-art of the existing libraries on GPU, and I stumbled upon your project. What exactly finite fields are supported ? Only fields of characteristic 2 ? Extension or only prime fields ? Single or multi-word fields ? Are there optimisations for some of them. In the FFT, the parameter is often a power of two. Do you only tackle these ? The description looks very vague to me.e Do you have benchmark plots with comparison NVIDIA vs AMD ?

[vmx]

What exactly finite fields are supported ? Only fields of characteristic 2 ?

It has been tested with the fields used in BLS12-381 and Pasta curves.

Extension or only prime fields ?

BLS12-381 G2 is using an extension field so I guess the answer is "both".

Single or multi-word fields ?

What are single and multi-word fields?

Are there optimisations for some of them.

Optimizations for what?

In the FFT, the parameter is often a power of two. Do you only tackle these ?

Yes, one paramters is log_n of the size, hence it's power of two.

Do you have benchmark plots with comparison NVIDIA vs AMD ?

It highly depends on the graphics cards you use. I propose benchmarking it yourself.

[dlesnoff]

You have answered my questions, but you have not updated the README.md or the description. You say arbitrary prime fields which are not the same as finite fields.

What are single and multi-word fields?

For fields with a characteristic sufficiently large, you can not represent all their elements on a machine word. You must then use multi-word algorithms or arbitrary precision libraries such as GMP.

You should maybe precise integer native types, as it is also possible to do the computation on floating-point types.

Optimizations for what?

The arithmetic in extension fields with a characteristic of two is completely different from other characteristics. You can use binary operations in those fields while you can not in arbitrary fields. There are other family of finite fields whose arithmetic is completely different.

It has been tested with the fields used in BLS12-381 and Pasta curves.

Would the tests (not the implementation itself) extend to arbitrary prime fields?

[vmx]

You have answered my questions, but you have not updated the README.md or the description.

If you provide a PR with a more precise README.md, I'm happy to review it.

You should maybe precise integer native types, as it is also possible to do the computation on floating-point types.

This is described in the README as:

Limbs are 32/64-bit long, by your choice (on CUDA only 32-bit limbs are supported)

It's 32/64-bit integer multiword fields.

[DrPeterVanNostrand]

Hi @dlesnoff,

You say arbitrary prime fields which are not the same as finite fields.

The trait ec_gpu::GpuField (link) can be implemented for either a prime field F_p or quadratic extension field F_p^2.

Because GpuField can be implemented for either/both prime and quadratic extension fields, GPU code for field arithmetic (addition, multiplication) can be generated for both field types.

I believe that the generated GPU FFT code is valid for only prime fields (but it's possible that the algorithm is also valid for extension fields, I'm not 100% sure on this point).

I believe that the elliptic curve groups used in the GPU multiscalar multiplication must be prime order, however those curve groups can be constructed over a base field that is either prime order or a quadratic extension.

Would the tests (not the implementation itself) extend to arbitrary prime fields?

The FFT GPU tests (link) should be valid for any prime field.

Likewise, the EC multiscalar multiplication GPU tests (link) should be valid for any prime order EC group whose base field is either a prime or quadratic extension field.