1/BigInteger in c#

问题:

I want to make

BigInteger.ModPow(1/BigInteger, 2,5);

but 1/BigInteger always return 0, which causes, that the result is 0 too. I tried to look for some BigDecimal class for c# but I have found nothing. Is there any way how to count this even if there is no BigDecimal?

回答1:

1/a is 0 for |a|>1, since BigIntegers use integer division where the fractional part of a division is ignored. I'm not sure what result you're expecting for this.

I assume you want to modular multiplicative inverse of a modulo m, and not a fractional number. This inverse exists iff a and m are co-prime, i.e. gcd(a, m) = 1.

The linked wikipedia page lists the two standard algorithms for calculating the modular multiplicative inverse:

• Extended Euclidean algorithm, which works for arbitrary moduli
  It's fast, but has input dependent runtime.

  I don't have C# code at hand, but porting the pseudo code from wikipedia should be straight forward.

• Using Euler's theorem:
  
  This requires knowledge of φ(m) i.e. you need to know the prime factors of m. It's a popular choice when m is a prime and thus φ(m) = m-1 when it simply becomes . If you need constant runtime and you know φ(m), this is the way to go.

  In C# this becomes BigInteger.ModPow(a, phiOfM-1, m)

回答2:

The overload of the / operator chosen, is the following:

public static BigInteger operator /(
        BigInteger dividend,
        BigInteger divisor
)

See BigInteger.Division Operator. If the result is between 0 and 1 (which is likely when dividend is 1 as in your case), because the return value is an integer, 0 is returned, as you see.

What are you trying to do with the ModPow method? Do you realize that 2,5 are two arguments, two and five, not "two-point-five"? Is your intention "take square modulo 5"?

If you want floating-point division, you can use:

1.0 / (double)yourBigInt

Note the cast to double. This may lose precision and even "underflow" to zero if yourBigInt is too huge.

回答3:

For example you need to get d in the next:
3*d = 1 (mod 9167368)

this is equally:
3*d = 1 + k * 9167368, where k = 1, 2, 3, ...

rewrite it:
d = (1 + k * 9167368)/3

Your d must be the integer with the lowest k.
Let's write the formula:
d = (1 + k * fi)/e

public static int MultiplicativeInverse(int e, int fi)
        {
            double result;
            int k = 1;
            while (true)
            {
                result = (1 + (k * fi)) / (double) e;
                if ((Math.Round(result, 5) % 1) == 0) //integer
                {
                    return (int)result;
                }
                else
                {
                    k++;
                }
            }
        } 

let's test this code:

Assert.AreEqual(Helper.MultiplicativeInverse(3, 9167368), 6111579); // passed