How could I get/set n-th bit of BigInt?

[kazunetakahashi]

Would you do me a favor? I need some help.

I'd like to get and set $n$-th bit of BigInt. How could I do it in a fast way?

For example, ramp has such methods; bit and set_bit.

I know that I can do it by bitwise operation such as (x >> bit) & BigInt::one() == BigInt::one() or so on. But I need faster way.

I would be grateful if you could give me advice.

[cuviper]

I can't think of a fast way to do it with the public API right now, but we could add methods like ramp's.

Can you offer the some example motivation of what you would use this for?

[kazunetakahashi]

Thank you for your comment.

Can you offer the some example motivation of what you would use this for?

I am trying making big prime numbers by a randomized algorithm now. This is needed for a cryptographic algorithm that I am researching on. In this method, one will try making a random integer and check if it is prime or not many times. To reduce useless attempts, set_bit is useful. For example, they set its 0-th bit as 1 to gain an odd number and 1023-th bit as 1 to gain such a big number for strangeness of cryptography. Similarly, get_bit is also good for checking prime numbers.

Other good big-integer libraries depends on C language, but yours is made of pure Rust. This is also a good point for my purpose.

[cuviper]

For BigUint, both getting and setting a bit should be straightforward to implement.

For BigInt, there's a design question of how to handle negative numbers. If we just use bits of the unsigned magnitude, it can simply forward to the BigUint methods. But if we want to expose bits as if it were a two's complement representation, as ramp does, then it will require some translation. We do implement the bitwise-ops (BitAnd etc.) as two's complement, so that's probably the right choice here as well.

(Do not copy ramp's implementation, because the licenses are different.)

[janmarthedal]

I am currently working on this, so a PR should be coming soon!

[mkaczanowski]

@janmarthedal how's the PR going? I also need this feature (the only reason why I use rug now is that function is missing)

[janmarthedal]

@mkaczanowski I have submitted a PR so I guess it is up to the project maintainers now.

[mkaczanowski]

Nice work! Thanks, @cuviper @janmarthedal

[kazunetakahashi]

@cuviper @janmarthedal Thank you so much. Today, I confirmed that my program got faster using your bit and set_bit. It helped me a lot.