  Android Question Bignumbers Library - Bias in Probable Prime results

Discussion in 'Android Questions' started by Derek Johnson, Feb 26, 2015.

1. 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]

Code:
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:

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

Code:
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 )

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:

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: Mar 1, 2015
JordiCP likes this.
2. TrobergWell-Known MemberLicensed User

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

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

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

Code:
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(1024rnd);
s1=k.toString(
2).substring(015);

String str = "ProbablePrime " + j + " (Length " + k.bitLength() + " bits) First 16 bits " +s1;
System.out.println( str );

}
}
}
Results:

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

5. 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 likes this.
6. 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.

Code:
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

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 likes this.
7. JordiCP likes this.
8. 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 .

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