[SOLVED] Why is the BigInteger.ModPow function in C# much slower than that in Java?

Table of Contents

Issue

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?

Solution

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.

Answered By – Orace

Answer Checked By – Clifford M. (BugsFixing Volunteer)

Leave a Reply

Your email address will not be published. Required fields are marked *