[QUESTION] How would one go about implementing a << or >> bitwise operator for mclBnFr instances?

[mxaddict]

How would one go about implementing a << or >> bitwise operator for mclBnFr instances?

Say for example, I would like to

mclBnFr fr;
mclBnFr_setInt(&fr, 4);
mclBnFr newFr = fr << 1; // And get this working and have the value of mclBnFr_setInt(&fr, 8);
mclBnFr newFr = fr >> 1; // And get this working and have the value of mclBnFr_setInt(&fr, 4);

[herumi]

Do you expect that fr << 1 is faster than fr += fr? If so, it may be not true. Because an element of Fr is in a range [0, r) so if the result of the bit operation << is larger than r, then it must be taken modulo. It means Fr_add(x, x, x).

Does x >> 1 mean floor(x / 2) or x / 2? Fr is a finite field, then x / 2 = x * (1/2) = x * ((r+1)/2).

[mxaddict]

Thanks for the response herumi, will have to run a test (benchmark) to see if it's faster either way.

The current implementation that we ended up with is this:

Scalar Scalar::operator<<(unsigned int shift) const
{
    Scalar temp;

    std::vector<uint8_t> vch = GetVch();
    std::vector<uint8_t> finalVch (WIDTH);

    for (int i = 0; i < WIDTH; i++)
        finalVch[i] = 0;
    int k = shift / 8;
    shift = shift % 8;
    for (int i = 0; i < WIDTH; i++) {
        if (i + k + 1 < WIDTH && shift != 0)
            finalVch[i + k + 1] |= (vch[i] >> (8 - shift));
        if (i + k < WIDTH)
            finalVch[i + k] |= (vch[i] << shift);
    }

    temp.SetVch(finalVch);

    return temp;
}

[herumi]

The internal representation of an element of Fr is Montgomery reduction, so we can't apply standard bit shift operation. I selected Montgomery reduction because multiplication is faster. What do you want to use bit shift operations for? It may require the other class.

#include <mcl/bls12_381.hpp>
#include <cybozu/xorshift.hpp>

using namespace mcl::bn;

int main()
{
    initPairing(mcl::BLS12_381);
    Fr x = 4;
    std::cout << "x=" << x << std::endl;
    x.dump();
    x = 8;
    std::cout << "x=" << x << std::endl;
    x.dump();
}

x=4
6092c566b31415be66313fbfb2f13fd56212dfe8000d200800000007fffffff8
x=8
4d37e37a3c8aae349928a7775c40a7a570681bcd001be41100000010ffffffef

[mxaddict]

For a little bit of context the GetVch() func used just runs mclBnFr_serialize() in ETH mode,

So for example fr that is set to Int 4 would have a value of std::vector [...,0,0,0,4] After a shift, it would then be either [...,0,0,0,2] or [...,0,0,0,8], then we use this value to deserialize back the result to fr.

[herumi]

I see. As you wrote in https://github.com/herumi/mcl/issues/144#issuecomment-1103606448, it is best way to fill uint8_t data[32]; from GetVch() and use mclBnFr_deserialize() because it minimize conversion.