I've just been experimenting with Prime generation using the Bignumbers library and I am puzzled by the results from generating probable primes. [I've changed the sample code to illustrate the issue more clearly]

The strange thing is that with bit length 1024 the probable primes generated by this method all seem to start with '11' Binary i.e. they are greater than 2^1023 + 2^1022.

I can understand that the first bit MUST be a 1 (in order for it to have 1023 significant bits) but why the 2nd one as well?

Here's a sample log:

NB The above code gives quite different than using this code to generate probable primes:

which gives this typical set of results:

As you can see in the 2nd case the probable primes can start with '10' B which is what you would expect.

At the very least this means that the documentation for ProbablePrime is somewhat misleading since it implies that the lower bound for probable primes is 0 when it is

2^(p-1)+2^(p-2) for useful values of p.

B4X:

```
Dim k As BigInteger, b As String, j As Int
k.Initialize("0")
For j=1 To 50
k.ProbablePrime(1024) 'Generate 1024 bit probable prime
b=k.ToStringBase(2) 'Convert to binary string
'List 1st 16 bits
Log("ProbablePrime " & j & " (Length = " & b.Length & " bits) First 16 bits " & b.SubString2(0,15) )
Next
```

The strange thing is that with bit length 1024 the probable primes generated by this method all seem to start with '11' Binary i.e. they are greater than 2^1023 + 2^1022.

I can understand that the first bit MUST be a 1 (in order for it to have 1023 significant bits) but why the 2nd one as well?

Here's a sample log:

ProbablePrime 1 (Length = 1024 bits) First 16 bits 111111111100111

ProbablePrime 2 (Length = 1024 bits) First 16 bits 111001100101100

ProbablePrime 3 (Length = 1024 bits) First 16 bits 110111110010111

ProbablePrime 4 (Length = 1024 bits) First 16 bits 110010010110010

ProbablePrime 5 (Length = 1024 bits) First 16 bits 111111111011100

ProbablePrime 6 (Length = 1024 bits) First 16 bits 111010001010100

ProbablePrime 7 (Length = 1024 bits) First 16 bits 110011000111111

ProbablePrime 8 (Length = 1024 bits) First 16 bits 110000001010000

ProbablePrime 9 (Length = 1024 bits) First 16 bits 110010011011100

ProbablePrime 10 (Length = 1024 bits) First 16 bits 111011101110000

ProbablePrime 11 (Length = 1024 bits) First 16 bits 111010001010000

ProbablePrime 12 (Length = 1024 bits) First 16 bits 111110101011000

ProbablePrime 13 (Length = 1024 bits) First 16 bits 110011000010011

ProbablePrime 14 (Length = 1024 bits) First 16 bits 111111110110000

ProbablePrime 15 (Length = 1024 bits) First 16 bits 110000010000001

ProbablePrime 16 (Length = 1024 bits) First 16 bits 111001110101111

ProbablePrime 17 (Length = 1024 bits) First 16 bits 111000000011010

ProbablePrime 18 (Length = 1024 bits) First 16 bits 110101100101110

ProbablePrime 19 (Length = 1024 bits) First 16 bits 111111100110101

ProbablePrime 20 (Length = 1024 bits) First 16 bits 110000110010000

ProbablePrime 21 (Length = 1024 bits) First 16 bits 110101110110001

ProbablePrime 22 (Length = 1024 bits) First 16 bits 111001001011011

ProbablePrime 23 (Length = 1024 bits) First 16 bits 111001011010110

ProbablePrime 24 (Length = 1024 bits) First 16 bits 110101000110100

ProbablePrime 25 (Length = 1024 bits) First 16 bits 110110011011101

ProbablePrime 26 (Length = 1024 bits) First 16 bits 110111110001011

ProbablePrime 27 (Length = 1024 bits) First 16 bits 110111110101110

ProbablePrime 28 (Length = 1024 bits) First 16 bits 110101111110110

ProbablePrime 29 (Length = 1024 bits) First 16 bits 110011101100001

ProbablePrime 30 (Length = 1024 bits) First 16 bits 111111011001010

ProbablePrime 31 (Length = 1024 bits) First 16 bits 111101100111110

ProbablePrime 32 (Length = 1024 bits) First 16 bits 110010100001011

ProbablePrime 33 (Length = 1024 bits) First 16 bits 110011101110111

ProbablePrime 34 (Length = 1024 bits) First 16 bits 110001010101001

ProbablePrime 35 (Length = 1024 bits) First 16 bits 111001101110001

ProbablePrime 36 (Length = 1024 bits) First 16 bits 111110011111011

ProbablePrime 37 (Length = 1024 bits) First 16 bits 111110011010011

ProbablePrime 38 (Length = 1024 bits) First 16 bits 111100111111100

ProbablePrime 39 (Length = 1024 bits) First 16 bits 110001001100010

ProbablePrime 40 (Length = 1024 bits) First 16 bits 110001111011111

ProbablePrime 41 (Length = 1024 bits) First 16 bits 110000111111110

ProbablePrime 42 (Length = 1024 bits) First 16 bits 110011011001010

ProbablePrime 43 (Length = 1024 bits) First 16 bits 110000100111000

ProbablePrime 44 (Length = 1024 bits) First 16 bits 110010000101000

ProbablePrime 45 (Length = 1024 bits) First 16 bits 110100000110010

ProbablePrime 46 (Length = 1024 bits) First 16 bits 111101010110100

ProbablePrime 47 (Length = 1024 bits) First 16 bits 110000100000000

ProbablePrime 48 (Length = 1024 bits) First 16 bits 110111001011011

ProbablePrime 49 (Length = 1024 bits) First 16 bits 111111110011001

ProbablePrime 50 (Length = 1024 bits) First 16 bits 111001000100101

NB The above code gives quite different than using this code to generate probable primes:

B4X:

```
Dim k As BigInteger, b As String, j As Int, pad As String
Blog("============= Using Random 1024 bit and NextProbablePrime =================")
k.Initialize("0")
For j=1 To 50
'Generate random number with 1024 bits
k.Initialize4(1024)
k.NextProbablePrime 'Get the next probable prime
b=k.ToStringBase(2) 'Convert to binary string
If b.Length<1024 Then
'Pad length to 1024 bits (needed if random number < 2^1023 )
pad="xxxxxxxxxxxxxxxx".substring2(0,1024-b.Length)
b=pad & b
End If
'List 1st 16 bits
Blog("ProbablePrime " & j & " (Length = " & b.Length & " bits) First 16 bits " & b.SubString2(0,15) )
Next
```

which gives this typical set of results:

============= Using Random 1024 bit and NextProbablePrime =================

ProbablePrime 1 (Length = 1024 bits) First 16 bits x11000101111110

ProbablePrime 2 (Length = 1024 bits) First 16 bits xxxx11101100010

ProbablePrime 3 (Length = 1024 bits) First 16 bits 111101101111101

ProbablePrime 4 (Length = 1024 bits) First 16 bits 101001001110101

ProbablePrime 5 (Length = 1024 bits) First 16 bits 110011000000000

ProbablePrime 6 (Length = 1024 bits) First 16 bits x11011000110011

ProbablePrime 7 (Length = 1024 bits) First 16 bits 111111011111000

ProbablePrime 8 (Length = 1024 bits) First 16 bits x11111111111001

ProbablePrime 9 (Length = 1024 bits) First 16 bits xx1111110100001

ProbablePrime 10 (Length = 1024 bits) First 16 bits 110011000110101

ProbablePrime 11 (Length = 1024 bits) First 16 bits x11011101111011

ProbablePrime 12 (Length = 1024 bits) First 16 bits xx1010011101010

ProbablePrime 13 (Length = 1024 bits) First 16 bits 111000111110110

ProbablePrime 14 (Length = 1024 bits) First 16 bits xxx111010100100

ProbablePrime 15 (Length = 1024 bits) First 16 bits x11010011010011

ProbablePrime 16 (Length = 1024 bits) First 16 bits xxx100010100000

ProbablePrime 17 (Length = 1024 bits) First 16 bits xx1111011010010

ProbablePrime 18 (Length = 1024 bits) First 16 bits 110000110100101

ProbablePrime 19 (Length = 1024 bits) First 16 bits xxx101110011110

ProbablePrime 20 (Length = 1024 bits) First 16 bits 101000011001111

ProbablePrime 21 (Length = 1024 bits) First 16 bits 111101011000010

ProbablePrime 22 (Length = 1024 bits) First 16 bits 110101101000101

ProbablePrime 23 (Length = 1024 bits) First 16 bits xx1011110011011

ProbablePrime 24 (Length = 1024 bits) First 16 bits 101011110110101

ProbablePrime 25 (Length = 1024 bits) First 16 bits 111011000000010

ProbablePrime 26 (Length = 1024 bits) First 16 bits x10101011011110

ProbablePrime 27 (Length = 1024 bits) First 16 bits 100010001000000

ProbablePrime 28 (Length = 1024 bits) First 16 bits xx1011110110000

ProbablePrime 29 (Length = 1024 bits) First 16 bits 110011011111001

ProbablePrime 30 (Length = 1024 bits) First 16 bits x11001011101000

ProbablePrime 31 (Length = 1024 bits) First 16 bits x11011111000110

ProbablePrime 32 (Length = 1024 bits) First 16 bits 110011000100000

ProbablePrime 33 (Length = 1024 bits) First 16 bits 111000011011100

ProbablePrime 34 (Length = 1024 bits) First 16 bits 111010100101100

ProbablePrime 35 (Length = 1024 bits) First 16 bits 110101110011001

ProbablePrime 36 (Length = 1024 bits) First 16 bits x11110011100101

ProbablePrime 37 (Length = 1024 bits) First 16 bits 111001111000101

ProbablePrime 38 (Length = 1024 bits) First 16 bits x11100111111011

ProbablePrime 39 (Length = 1024 bits) First 16 bits 110011110001110

ProbablePrime 40 (Length = 1024 bits) First 16 bits x10100110011111

ProbablePrime 41 (Length = 1024 bits) First 16 bits x11110001011110

ProbablePrime 42 (Length = 1024 bits) First 16 bits x10111011100011

ProbablePrime 43 (Length = 1024 bits) First 16 bits x11110001010110

ProbablePrime 44 (Length = 1024 bits) First 16 bits 110011000101000

ProbablePrime 45 (Length = 1024 bits) First 16 bits xx1011000000101

ProbablePrime 46 (Length = 1024 bits) First 16 bits x10110111001100

ProbablePrime 47 (Length = 1024 bits) First 16 bits x10101100010000

ProbablePrime 48 (Length = 1024 bits) First 16 bits x11011101010010

ProbablePrime 49 (Length = 1024 bits) First 16 bits xx1000111000000

ProbablePrime 50 (Length = 1024 bits) First 16 bits 110110000010100

As you can see in the 2nd case the probable primes can start with '10' B which is what you would expect.

At the very least this means that the documentation for ProbablePrime is somewhat misleading since it implies that the lower bound for probable primes is 0 when it is

2^(p-1)+2^(p-2) for useful values of p.

Last edited: