Android Question Bignumbers Library - Bias in Probable Prime results

[Derek Johnson]

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]

        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:

        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.

 

[Troberg]

Now, I don't get the code, especially some of the constant numbers in it (and the math behind probable primes), but isn't this just a result of where you start looking? The two bits you are looking at are not the least significant bits, they are the most significant bits. Look at the right end of the number, and you'll see a more reasonable variation.

Isn't it simply a result of which vicinity you are looking in (ie, how large the numbers will be)?

Or is it just me who has misunderstood everything (which is quite possible).

 

[Derek Johnson]

I am sure that there are very many primes that start with binary '10' in the ranges specified. With just a few samples, then it is understandable that the algorithm could generate a set of samples that all start with binary '11', but it is not just a coincidence when hundreds of probable prime numbers generated by this algorithm start with '11'. I was looking for an explanation based on the code of the ProbablePrime function. The B4A function uses a hidden random number generator, perhaps this is programmed with the wrong range in which to search for probable primes. I don't know - just asking the question.

 

[Derek Johnson]

Just checked out the equivalent Java code. This generates binary values starting with '11' and '10' as expected.

import java.math.*;
import java.util.*;
public class Test{

    public static void main(String []args){
    System.out.println("================================");
 
    // create a BigInteger object
    BigInteger k;
    int j;
    String s1;
 
    for (j=1;j<50;j++){
        Random rnd = new Random();
        k = BigInteger.probablePrime(1024, rnd);
        s1=k.toString(2).substring(0, 15);
        String str = "ProbablePrime " + j + " (Length " + k.bitLength() + " bits) First 16 bits " +s1;
        System.out.println( str );

    }
  }
}

Results:

ProbablePrime 1 (Length 1024 bits) First 16 bits 111000010101011
ProbablePrime 2 (Length 1024 bits) First 16 bits 111010010101000
ProbablePrime 3 (Length 1024 bits) First 16 bits 111010011100111
ProbablePrime 4 (Length 1024 bits) First 16 bits 101001000001010
ProbablePrime 5 (Length 1024 bits) First 16 bits 101111010100111
ProbablePrime 6 (Length 1024 bits) First 16 bits 111001110100100
ProbablePrime 7 (Length 1024 bits) First 16 bits 111100001010010
ProbablePrime 8 (Length 1024 bits) First 16 bits 100000010110000
ProbablePrime 9 (Length 1024 bits) First 16 bits 100000011100100
ProbablePrime 10 (Length 1024 bits) First 16 bits 100101101111011
ProbablePrime 11 (Length 1024 bits) First 16 bits 100010000111101
ProbablePrime 12 (Length 1024 bits) First 16 bits 110111111110111
ProbablePrime 13 (Length 1024 bits) First 16 bits 110111111001100
ProbablePrime 14 (Length 1024 bits) First 16 bits 101110001000110
ProbablePrime 15 (Length 1024 bits) First 16 bits 100101101010011
ProbablePrime 16 (Length 1024 bits) First 16 bits 111011110011111
ProbablePrime 17 (Length 1024 bits) First 16 bits 111100010101001
ProbablePrime 18 (Length 1024 bits) First 16 bits 111100000110110
ProbablePrime 19 (Length 1024 bits) First 16 bits 111011101000111
ProbablePrime 20 (Length 1024 bits) First 16 bits 101001100000111
ProbablePrime 21 (Length 1024 bits) First 16 bits 111000110011101
ProbablePrime 22 (Length 1024 bits) First 16 bits 101100010001011
ProbablePrime 23 (Length 1024 bits) First 16 bits 100010110001000
ProbablePrime 24 (Length 1024 bits) First 16 bits 101100001010111
ProbablePrime 25 (Length 1024 bits) First 16 bits 110111011001000
ProbablePrime 26 (Length 1024 bits) First 16 bits 100011101100010
ProbablePrime 27 (Length 1024 bits) First 16 bits 101011010011100
ProbablePrime 28 (Length 1024 bits) First 16 bits 111001100001100
ProbablePrime 29 (Length 1024 bits) First 16 bits 110110001000110
ProbablePrime 30 (Length 1024 bits) First 16 bits 110001111000101
ProbablePrime 31 (Length 1024 bits) First 16 bits 110111100011011
ProbablePrime 32 (Length 1024 bits) First 16 bits 110110101101101
ProbablePrime 33 (Length 1024 bits) First 16 bits 111010000110111
ProbablePrime 34 (Length 1024 bits) First 16 bits 111100110111100
ProbablePrime 35 (Length 1024 bits) First 16 bits 110010010101001
ProbablePrime 36 (Length 1024 bits) First 16 bits 101100100010101
ProbablePrime 37 (Length 1024 bits) First 16 bits 111100011011001
ProbablePrime 38 (Length 1024 bits) First 16 bits 110101100111001
ProbablePrime 39 (Length 1024 bits) First 16 bits 101000111010011
ProbablePrime 40 (Length 1024 bits) First 16 bits 110111111001111
ProbablePrime 41 (Length 1024 bits) First 16 bits 111100111010110
ProbablePrime 42 (Length 1024 bits) First 16 bits 111100101010111
ProbablePrime 43 (Length 1024 bits) First 16 bits 100001110000000
ProbablePrime 44 (Length 1024 bits) First 16 bits 110001011101000
ProbablePrime 45 (Length 1024 bits) First 16 bits 111111000110011
ProbablePrime 46 (Length 1024 bits) First 16 bits 101000111010010
ProbablePrime 47 (Length 1024 bits) First 16 bits 101000011000110
ProbablePrime 48 (Length 1024 bits) First 16 bits 111000000100111
ProbablePrime 49 (Length 1024 bits) First 16 bits 111110010010111

So I would say that there is a definite bug in the BigNumbers Library for ProbablePrime.

 

[JordiCP]

It's strange because I have compared the results with Basic and Inline Java, and both of them start always with "11" when number of bits is >=16

Haven't tested it in a standalone Eclipse project.

 

[Derek Johnson]

I tried my Java example at http://www.tutorialspoint.com/compile_java_online.php and later at http://www.browxy.com/ and got results showing numbers starting with 10 and 11B.

Could you say how you (JordiCP) tried your Basic (B4A?) and Inline Java tests please?

 

[JordiCP]

Hi Derek,

This is the code. Both approaches give the same result as you will see in the logs.
Also tried initialiting the random generator with current time ticks, just to try (now removed) but result was the same.

I think that with >=16 bits always gives "bad" result ("11..") and it is not due to the BigNumbers B4A wrapper library, since with inline Java this also happens. But have no idea of what can it be.

Sub Process_Globals
    'These global variables will be declared once when the application starts.
    'These variables can be accessed from all modules.
    Private NativeMe As JavaObject
End Sub

Sub Globals
End Sub

Sub Activity_Create(firsttime As Boolean)
   
    NativeMe.InitializeContext

    Run_Test(False,100)    'B4A code
    Run_Test(True,100)    'Inline Java call
   
End Sub

Sub Activity_Resume
End Sub

Sub Activity_Pause (UserClosed As Boolean)
End Sub


Sub Run_Test( inline As Boolean, num_times As Int)

    Dim bitlen As Int = 16        'Dim bitlen As Int =1022
   
    Dim k As BigInteger, b As String, j As Int

    k.Initialize("0")
    For j=1 To num_times

        If inline=False Then
            k.ProbablePrime(bitlen) 'Generate 1024 bit probable prime
              b=k.ToStringBase(2)   'Convert to binary string
        Else
            b=NativeMe.RunMethod("NewBigInt",Array(bitlen))
        End If
        'List leading bits.
        Log("ProbablePrime " & j & " (Length = " & b.Length & " bits)  First 8 bits " & b.SubString2(0,8) )           
    Next   
       
End Sub


#If java

import android.util.Log;
import java.math.BigInteger;
import java.util.Random;

    public String NewBigInt( int num_bits){
   
        BigInteger bg ;
        String s;
       
        Random rnd = new java.util.Random();
        bg = BigInteger.probablePrime(num_bits,rnd);
        s=bg.toString(2);
        return s;
    }

#End If

 

[Derek Johnson]

I've now reported this as an Android bug here:

https://code.google.com/p/android/issues/detail?id=158185

 

[JordiCP]

Hi Derek

To be more precise, I would change the sentence "Should only have the top bit set" for "should also give results with only the top bit set and not the second" or something similar

Anyway, I still don't understand why it gives the expected results with pure java code .

 

[Derek Johnson]

Hi Derek

To be more precise, I would change the sentence "Should only have the top bit set" for "should also give results with only the top bit set and not the second" or something similar

Anyway, I still don't understand why it gives the expected results with pure java code .

Good point. I've added a note.

I think this is a bug in the Dalvik/Art versions of Java. I'm surprised that no one has spotted it before. If I was using this for a serious bit of cryptography I'd be a bit p****d off.