# (How not to) Generate a Large Prime

## Confidently Incorrect

I asked Bard and ChatGPT to generate large primes. I wasn't expecting magic, I thought they would give a wrong answer.

I was rooting for them and hoped they might understand that large means really large in this context.

What surprised me was how confidently they asserted that the composite number they provided me with was a prime number.

They carefully explained it was only divisible by 1 and itself. They carefully explained there is the Miller-Rabin primality test.

Even after asking the forward multiplication, they still asserted their number was prime.

Chat GPT would when told outright concede that it was not prime.

## Code Generation

I tried another approach, asking for an actually large prime (1024 bit), they helpfully generated code to generate a prime.

This was in their wheelhouse. Yet their answers gave me code that had naive primality tests while asserting they were using probabilistic tests.

Now this code looks much better. It seems more sophisticated than the earlier tests and could to the untrained eye plausibly be a working implementation of Miller-Rabin.

Let's try it out and run it!

``` 65537 is composite. ```

Oh dear.

p.s. I have no idea if the "example output" is prime or not, but this is it:

```            1112140441391186194588486931517539482960
5765412782916691490620973532491637189649
1119563828345538092899249564707256262387
0884694318420377312468566023100335157447
0465874159363098002524883751823814837828
2212738504052001926740531138951106678803
5808920314062259620876628714801358581422
45523789325317276927004039427```

## Appendix

### Code Example 1 (Python)

```    import random
import math

def generate_prime_number(num_bits):
while True:
n = random.getrandbits(num_bits)
if n % 2 == 0:
n += 1
if is_prime(n):
return n

def is_prime(n):
if n <= 3:
return n > 1
elif n % 2 == 0 or n % 3 == 0:
return False
else:
i = 5
while i * i <= n:
if n % i == 0 or n % (i + 2) == 0:
return False
i += 6
return True

prime_number = generate_prime_number(1024)
print(prime_number)

```

### Code example 2 (C#)

```        using System;

class MillerRabin
{
static Random rand = new Random();

static bool IsPrime(int n, int k)
{
if (n == 2 || n == 3)
return true;

if (n < 2 || n % 2 == 0)
return false;

int s = 0, d = n - 1;
while (d % 2 == 0)
{
d /= 2;
s++;
}

for (int i = 0; i < k; i++)
{
int a = rand.Next(2, n - 1);
int x = ModPow(a, d, n);

if (x == 1 || x == n - 1)
continue;

for (int j = 0; j < s - 1; j++)
{
x = ModPow(x, 2, n);
if (x == n - 1)
break;
}

if (x != n - 1)
return false;
}

return true;
}

static int ModPow(int a, int b, int n)
{
int res = 1;
while (b > 0)
{
if (b % 2 == 1)
res = (res * a) % n;
a = (a * a) % n;
b /= 2;
}
return res;
}

static void Main()
{
int n = 65537;
int k = 10;

if (IsPrime(n, k))
Console.WriteLine(n + " is probably prime.");
else
Console.WriteLine(n + " is composite.");
}
}

```