Android Question Bignumbers Library - Bias in Probable Prime results

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

  1. Derek Johnson

    Derek Johnson Active Member Licensed User

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

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

    Troberg Well-Known Member Licensed 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. Derek Johnson

    Derek Johnson Active Member Licensed User

    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. Derek Johnson

    Derek Johnson Active Member Licensed User

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

    JordiCP Well-Known Member Licensed User

    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. Derek Johnson

    Derek Johnson Active Member Licensed User

  7. JordiCP

    JordiCP Well-Known Member Licensed User

    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
            
    '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 likes this.
  8. Derek Johnson

    Derek Johnson Active Member Licensed User

    JordiCP likes this.
  9. JordiCP

    JordiCP Well-Known Member Licensed User

    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 :confused:.
     
  10. Derek Johnson

    Derek Johnson Active Member Licensed User

    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.
     
Loading...
  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice