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:

- Calculate 200000! to produce a very large number
`m`

. - 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)