Re: [CFRG] hash_to_field requires implementing a new 25519 field op

["Riad S. Wahby" <[e-mail]>]

Hello Loup,

Loup Vaillant-David <[e-mail]> wrote:
> Wait a minute, that reduction is not *nearly* as large as you make it
> out to be.  Let's take a look at Curve25519's ref10 implementation on
> SUPERCOP. You would think that because the result of the multiplication
> (before carry propagation) is stored in 10 64-bit signed integers, the
> number they represent easily exceeds 2^512, or even approaches 2^640.

Our messages crossed, but in general the product of two residues mod p
will be as large as p^2 - 2p + 1, which is roughly log2(p^2) bits as I
claimed. The code you link does some of that reduction implicitly, but
the same trick can be used on a 384-bit number. See my message from ~5
minutes ago to Filippo.

Or, as Rene points out in parallel, if we do not demand absolutely the
fastest reduction we can implement it using field operations directly,
which is what I did in the pairing-plus crate, for example:
    https://github.com/algorand/pairing-plus/blob/master/src/bls12_381/fq.rs#L471

Cheers,

-=rsw