Is there a way to do a right bit-shift on a BigInt in Rust?

Question

I get this error when attempting to do >> or >>= on a BigInt:

no implementation for `BigInt >> BigInt

using the num_bigint::BigInt library

Edit: More Context:

I am rewriting this program https://www.geeksforgeeks.org/how-to-generate-large-prime-numbers-for-rsa-algorithm/ from python/c++ into rust however I will focus on the python implementation as it is written to handle 1024 bit prime numbers which are extremely big.

Update: I have completed a rust implementation https://github.com/dzyphr/Rust_Repo/blob/master/big_prime/src/main.rs

In the code we run the Miller Rabin Primality test which includes shifting EC: (prime-candidate - 1) to the right by 1 if we find that EC % 2 == 0. As I mentioned in the python implementation EC can be an incredibly large integer.

It would be convenient to be able to use the same operator in rust, if that is not possible can someone suggest an alternative?

Acropolis

It would not make any sense, BigInt is a complex data structure used to represent any arbitrary number size. There is not bit to shift from a user point of view, it's a black box. – Limey

It seems that BigInt shifting has been implemented several times however if you assert that it makes no sense can you offer a replacement for it? BigInt Shift in Java: geeksforgeeks.org/biginteger-shiftright-method-in-java – Acropolis

@Limey It makes perfect sense to do bitwise operations on bigints, and the library in question does implement bitwise operations including right-shift, just not right-shift where the second operand is a bigint. – Bahamas

@Bahamas I don't get how it's useful but ok nevermind. – Limey

Answer 1

According to the documentation for the num-bigint crate, the BigInt struct does implement the Shr trait for the right-shift operator, just not when the shift amount is itself a BigInt. If you convert the shift amount to a standard integer type (e.g. i64) then it should work.

It is unlikely you would ever want to shift by an amount greater than i64::MAX, but if you do need this, then the correct result is going to be zero (because no computer has 2^60 bytes of memory), so you can write a simple implementation which checks for that case.

Bahamas

Thank you, I did notice that the crate implemented Shr but I had no clue how to use it. I was used to converting small integers to BigInt to make operations look seamless when doing operations across Big and Small integers however this makes sense as I was not planning to shift the BigInt by another BigInt. – Acropolis