I have found that the BigInteger.ModPow function in C# is very slow compared to the BigInteger.modPow function in Java. This makes me reluctant to use C# to implement functions that perform modular exponentiation.

I have written a test program to prove it.

C#

static void Main(string[] args)
{
    BigInteger num = BigInteger.Parse("444266014606582911577255360081280172978907874637194279031281180366057");
    BigInteger m = 2;
    Console.WriteLine("Start multiply.");
    Stopwatch stopwatch = Stopwatch.StartNew();
    for (int i = 3; i <= 200000; i  )
        m *= i;
    stopwatch.Stop();
    Console.WriteLine(stopwatch.ElapsedMilliseconds);
    stopwatch.Reset();
    Console.WriteLine("Start mod pow.");
    stopwatch.Start();
    for (int i = 0; i < 10; i  )
        BigInteger.ModPow(3, m, num);
    stopwatch.Stop();
    Console.WriteLine(stopwatch.ElapsedMilliseconds);
}

An equivalent program in Java

public static void main(String[] args) {
    BigInteger num = new BigInteger("444266014606582911577255360081280172978907874637194279031281180366057");
    BigInteger m = BigInteger.TWO;
    System.out.println("Start multiply.");
    long startTime = System.currentTimeMillis();
    for (int i = 3; i <= 200000; i  )
        m = m.multiply(BigInteger.valueOf(i));
    System.out.println(System.currentTimeMillis() - startTime);
    System.out.println("Start mod pow.");
    startTime = System.currentTimeMillis();
    for (int i = 0; i < 10; i  )
        BigInteger.valueOf(3).modPow(m, num);
    System.out.println(System.currentTimeMillis() - startTime);
}

The program consists of 2 parts:

1. Calculate 200000! to produce a very large number m.
2. Calculate 3 ^ m mod num 10 times.

You may change the numbers or the loop count to try finding different results.

Here is an execution result on my computer.

Specifications

• CPU: Intel(R) Core(TM) i3-8100 CPU @ 3.60GHz
• .Net Version: .NET 6.0.102
• Java Version: 17.0.1

C#

Start multiply.
19443
Start mod pow.
35292

Java

Start multiply.
14668
Start mod pow.
3462

It shows that the BigInteger.ModPow function in C# is about 10 times slower than that in Java. Does anyone know the reason? Is that a bug?

CodePudding user response：

You can take a look at the .Net implémentation here and the java ones here.
It appears that the java ones was more heavily studied.