Generate random bigNumber

Hi guys,

I’m using bigNumber library in order to implement a DH (diffie-hellman) exchange between arduino and iPhone.

Currently, the iPhone implementation is done.

I’m having troubles in generating a random bigNumber, since there’s no function in the library that does that.

I have to generate a random number which is smaller than a bigNumber p, with p very large (eg: 256bit number, or even more).

Could you give me any advice on how to achieve that?

Thanks in advance!

PS: Here’s the library of BigNumber I’m using: http://forum.arduino.cc/index.php?topic=85692.0

How about just concatenating the ascii representation of a random numbers of random numbers in a charBuffer and use the result to construct a BigNumber?

Thank you for the reply.

It's a good idea, but how do I manage to be sure that the random number is less than a given one (eg: p)?

Bye :slight_smile:

If less than p is all that is needed (I suppose p will be bigger than 10),
just generate 1 digit less than the ascii-representation of p has.

Whandall:
If less than p is all that is needed (I suppose p will be bigger than 10),
just generate 1 digit less than the ascii-representation of p has.

I would think also of this solution but it would exclude a (big) range of possible numbers.
so (think think think ....)

To get all numbers possible one should generate a random string that has the same length as the max number.
For every position one should check what range the digit may have.

an example with a smaller number

MAX = 65535

first digit may be 0..6

second digit may be 0..9 unless first is '6' then 0..5

third digit may be 0..9 unless first 2 digits is '65'

fourth digit may be 0..9 unless first 3 digits are '655'

fifth digit .... (ok you get it :wink:

wrote a small sketch to show how it can be done

//
//    FILE: randomCharArray.ino
//  AUTHOR: Rob Tillaart
// VERSION: 0.1.00
// PURPOSE: demo for bigNumber
//    DATE: 2015-10-24
//     URL: http://forum.arduino.cc/index.php?topic=355182
//
// Released to the public domain
//

char s[] = "123456789655357638576349875347563987659283476528374597357353734";
char r[100] = "";

uint32_t start;
uint32_t stop;

void setup()
{
  Serial.begin(115200);
  Serial.print("Start ");
  Serial.println(__FILE__);

  randomSeed(analogRead(A0));

  start = micros();
  randomCharArray(s, r);
  stop = micros();
  Serial.print("LENGTH:\t");
  Serial.println(strlen(s));
  Serial.print("TIME:\t");
  Serial.println(stop - start);
  Serial.print("T/CHAR:\t");
  Serial.println(1.0 * (stop - start) / strlen(s));
  delay(2000);
}

void loop()
{
  randomCharArray(s, r);
  Serial.println(s);
  Serial.println(r);
  Serial.println();
  delay(500);
}

int randomCharArray(char *s, char *r)
{
  bool critical = true;
  for (int i = 0; i < strlen(s); i++)
  {
    int lm = s[i] - '0';
    if (critical)
    {
      r[i] = random(lm + 1) + '0';
      critical = (r[i] == s[i]);
    }
    else
    {
      r[i] = random(10) + '0';
    }
  }
  r[strlen(s)] = '\0';
}

The MAX string s starts with 123456789 to show that the generated random number will not exceed it.

generates 1 digit per 120 usec approx

traded speed for space

//
//    FILE: randomCharArray.ino
//  AUTHOR: Rob Tillaart
// VERSION: 0.1.01
// PURPOSE: demo for bigNumber
//    DATE: 2015-10-24
//     URL: http://forum.arduino.cc/index.php?topic=355182
//
// Released to the public domain
//

char s[] = "123456789655357638576349875347563987659283476528374597357353734";
char r[100] = "";

uint32_t start;
uint32_t stop;

void setup()
{
  Serial.begin(115200);
  Serial.print("Start ");
  Serial.println(__FILE__);

  randomSeed(analogRead(A0));

  start = micros();
  randomCharArray(s, r);
  stop = micros();
  Serial.print("LENGTH:\t");
  Serial.println(strlen(s));
  Serial.print("TIME:\t");
  Serial.println(stop - start);
  Serial.print("T/CHAR:\t");
  Serial.println(1.0 * (stop - start) / strlen(s));
  delay(2000);
}

void loop()
{
  randomCharArray(s, r);
  Serial.println(s);
  Serial.println(r);
  Serial.println();
  delay(500);
}

int randomCharArray(char *s, char *r)
{
  bool critical = true;
  byte i = 0;
  byte len = strlen(s);
  while (critical && i < len)
  {
    byte lm = s[i] - '0';
    r[i] = random(lm + 1) + '0';
    critical = (r[i] == s[i]);
    i++;
  }
  while (i < len - 4)
  {
    int rv = random(10000);
    byte t = rv / 1000;
    r[i++] = t + '0';
    rv -= t * 1000;
    t = rv / 100;
    r[i++] = t + '0';
    rv -= t * 100;
    r[i++] = rv / 10 + '0';
    r[i++] = rv % 10 + '0';
  }
  while (i < len)
  {
    r[i++] = random(10) + '0';
  }
  r[len] = '\0';
}


int randomCharArray0100(char *s, char *r)
{
  bool critical = true;
  for (int i = 0; i < strlen(s); i++)
  {
    int lm = s[i] - '0';
    if (critical)
    {
      r[i] = random(lm + 1) + '0';
      critical = (r[i] == s[i]);
    }
    else
    {
      r[i] = random(10) + '0';
    }
  }
  r[strlen(s)] = '\0';
}

Start randomCharArray.ino
LENGTH: 63
TIME: 2584
T/CHAR: 41.02

generates 1 digit per 41 usec approx

(size demo sketch = 5462 opposed to 5228 above)

Thank you robtillaart.

You're solution is very clever! You made my day!

I'll go with your solution :slight_smile:

Have a great day!

Squeezed some bytes and a few clock cycles.

//
//    FILE: randomCharArray.ino
//  AUTHOR: Rob Tillaart
// VERSION: 0.1.02
// PURPOSE: demo for bigNumber
//    DATE: 2015-10-24
//     URL: http://forum.arduino.cc/index.php?topic=355182
//
// Released to the public domain
//

char s[] = "123456789655357638576349875347563987659283476528374597357353734";
char r[100] = "";

uint32_t start;
uint32_t stop;

void setup()
{
  Serial.begin(115200);
  Serial.print("Start ");
  Serial.println(__FILE__);

  randomSeed(analogRead(A0));

  start = micros();
  randomCharArray(s, r);
  stop = micros();
  Serial.print("LENGTH:\t");
  Serial.println(strlen(s));
  Serial.print("TIME:\t");
  Serial.println(stop - start);
  Serial.print("T/CHAR:\t");
  Serial.println(1.0 * (stop - start) / strlen(s));
  delay(2000);
}

void loop()
{
  randomCharArray(s, r);
  Serial.println(s);
  Serial.println(r);
  Serial.println();
  delay(500);
}

int randomCharArray(char *s, char *r)
{
  bool critical = true;
  byte i = 0;
  byte len = strlen(s);
  while (critical && i < len)
  {
    byte lm = s[i] - '0';
    r[i] = random(lm + 1) + '0';
    critical = (r[i] == s[i]);
    i++;
  }
  while (i < len - 4)
  {
    int rv = random(10000);
    r[i++] = rv % 10 + '0';
    rv /= 10;
    r[i++] = rv % 10 + '0';
    rv /= 10;
    r[i++] = rv % 10 + '0';
    r[i++] = rv / 10 + '0';
  }
  while (i < len)
  {
    r[i++] = random(10) + '0';
  }
  r[len] = '\0';
}

Start randomCharArray.ino
LENGTH: 63
TIME: 2544
T/CHAR: 40.38

(size sketch = 5346)

For the bigNumber library you could make it more memory efficient as the result string (r) is not needed.

Just shift the digits directly into a bigNumber.

in pseudo code

BN = 0;
while (i< strlen(s))
{
BN * 10;
BN += generateNextDigit(s, i);
}

Played a bit with recursive generating big random number string,
in essence counting the # loops of this code

x = big;
while (x != 0) { x = random(x); count++ }

It has no use except as an statistical exercise as far as I can see

//
//    FILE: RandomBigNumberToZero.ino
//  AUTHOR: Rob Tillaart
// VERSION: 0.1.00
// PURPOSE: demo for bigNumber
//    DATE: 2015-10-25
//     URL: http://forum.arduino.cc/index.php?topic=355182
//
// Released to the public domain
//

char s[] = "12345678965535763857634987534756398765928347652837459735735373723065723757632075437804943236344";
char r[100] = "";

uint32_t start;
uint32_t stop;

uint16_t  count = 0;
void setup()
{
  Serial.begin(115200);
  Serial.print("Start ");
  Serial.println(__FILE__);

  randomSeed(analogRead(A0));

  start = micros();
  randomCharArray(s, r);
  stop = micros();
  Serial.print("LENGTH:\t");
  Serial.println(strlen(s));
  Serial.print("TIME:\t");
  Serial.println(stop - start);
  Serial.print("T/CHAR:\t");
  Serial.println(1.0 * (stop - start) / strlen(s));
  delay(2000);
}

void loop()
{
  Serial.print(count++);
  Serial.print('\t');
  Serial.println(s);
  randomCharArray(s, r);
  delay(200);
  Serial.print(count++);
  Serial.print('\t');
  Serial.println(r);
  randomCharArray(r, s);
  delay(200);

  if (isZero(s)) while (1);
}

int randomCharArray(char *s, char *r)
{
  bool critical = true;
  byte i = 0;
  byte len = strlen(s);
  while (critical && i < len)
  {
    byte lm = s[i] - '0';
    r[i] = random(lm + 1) + '0';
    critical = (r[i] == s[i]);
    i++;
  }
  while (i < len - 4)
  {
    int rv = random(10000);
    r[i++] = rv % 10 + '0';
    rv /= 10;
    r[i++] = rv % 10 + '0';
    rv /= 10;
    r[i++] = rv % 10 + '0';
    r[i++] = rv / 10 + '0';
  }
  while (i < len)
  {
    r[i++] = random(10) + '0';
  }
  r[len] = '\0';
}

bool isZero(char *s)
{
  for (int i = 0; i < strlen(s); i++)
  {
    if (s[i] != '0') return false;
  }
  return true;
}

// REFERENCE IMPLEMENTATION SMALL
int randomCharArray0100(char *s, char *r)
{
  bool critical = true;
  for (int i = 0; i < strlen(s); i++)
  {
    if (critical)
    {
      int lm = s[i] - '0';
      r[i] = random(lm + 1) + '0';
      critical = (r[i] == s[i]);
    }
    else
    {
      r[i] = random(10) + '0';
    }
  }
  r[strlen(s)] = '\0';
}

I refactored the code to perform much faster. Note there is a chance for starvation when no digit is generated. I can avoid that, but need some experiments to confirm.

//
//    FILE: randomCharArray.ino
//  AUTHOR: Rob Tillaart
// VERSION: 0.1.03
// PURPOSE: demo for bigNumber
//    DATE: 2015-10-24
//     URL: http://forum.arduino.cc/index.php?topic=355182
//
// Released to the public domain
//

char s[] = "123456789655357638576349875347563987659283476528374597357353734";
char r[100] = "";

uint32_t start;
uint32_t stop;

void setup()
{
  Serial.begin(115200);
  Serial.print("Start ");
  Serial.println(__FILE__);

  randomSeed(analogRead(A0));

  start = micros();
  randomCharArray(s, r);
  stop = micros();
  Serial.print("LENGTH:\t");
  Serial.println(strlen(s));
  Serial.print("TIME:\t");
  Serial.println(stop - start);
  Serial.print("T/CHAR:\t");
  Serial.println(1.0 * (stop - start) / strlen(s));
  delay(2000);
}

void loop()
{
  randomCharArray(s, r);
  Serial.println(s);
  Serial.println(r);
  Serial.println();
  delay(500);
}

// PERFORMANT IMPLEMENATION
int randomCharArray(char *s, char *r)
{
  bool critical = true;
  byte i = 0;
  byte len = strlen(s);
  while (critical && i < len)
  {
    byte lm = s[i] - '0';
    r[i] = random(lm + 1) + '0';
    critical = (r[i] == s[i]);
    i++;
  }
  
  while (i < len)
  {
    uint32_t rv = random();       // 4 bytes = 8 nybbles
    for (byte b = 0; b < 8; b++)
    {
      byte v = rv & 0x0F;
      rv >>= 4;
      if (v > 9) continue;
      r[i++] = v + '0';
      if (i == len) break;
    }
  }
  r[len] = '\0';
}

// REFERENCE IMPLEMENTATION SMALL
int randomCharArray0100(char *s, char *r)
{
  bool critical = true;
  for (int i = 0; i < strlen(s); i++)
  {
    if (critical)
    {
      int lm = s[i] - '0';
      r[i] = random(lm + 1) + '0';
      critical = (r[i] == s[i]);
    }
    else
    {
      r[i] = random(10) + '0';
    }
  }
  r[strlen(s)] = '\0';
}

output:

Start randomCharArray.ino
LENGTH: 63
TIME: 1080
T/CHAR: 17.14

that’s 23 uSec off previous time (per digit) - see post #8

(sketch size 5,242 bytes)

A starvation patch in place,

//
//    FILE: randomCharArray.ino
//  AUTHOR: Rob Tillaart
// VERSION: 0.1.03
// PURPOSE: demo for bigNumber
//    DATE: 2015-10-24
//     URL: http://forum.arduino.cc/index.php?topic=355182
//
// Released to the public domain
//

char s[] = "123456789655357638576349875347563987659283476528374597357353734";
char r[100] = "";

uint32_t start;
uint32_t stop;

void setup()
{
  Serial.begin(115200);
  Serial.print("Start ");
  Serial.println(__FILE__);

  randomSeed(analogRead(A0));

  start = micros();
  randomCharArray(s, r);
  stop = micros();
  Serial.print("LENGTH:\t");
  Serial.println(strlen(s));
  Serial.print("TIME:\t");
  Serial.println(stop - start);
  Serial.print("T/CHAR:\t");
  Serial.println(1.0 * (stop - start) / strlen(s));
  delay(2000);
}

void loop()
{
  randomCharArray(s, r);
  Serial.println(s);
  Serial.println(r);
  Serial.println();
  delay(500);
}

// PERFORMANT IMPLEMENATION
int randomCharArray(char *s, char *r)
{
  bool critical = true;
  byte i = 0;
  byte len = strlen(s);
  while (critical && i < len)
  {
    byte lm = s[i] - '0';
    r[i] = random(lm + 1) + '0';
    critical = (r[i] == s[i]);
    i++;
  }

  while (i < len)
  {
    uint32_t rv = random();       // 4 bytes = 8 nybbles 0..15
    byte sum = 0;
    for (byte b = 0; b < 8; b++)
    {
      // get nybble
      byte v = rv & 0x0F;
      // prepare for next nybble
      rv >>= 4;
      // not in 0..9 ==> skip nybble but use its value.
      if (v > 9) 
      {
        sum += v;
        continue;
      }
      r[i++] = v + '0';
      if (i == len) break;
    }
    // if all nybbles are skipped, sum is at least 80
    // so we can use sum to generate at least one digit per iteration.
    if (i < len && sum >= 80)   
    {
      r[i++] = sum % 10 + '0';  
    }
  }
  r[len] = '\0';
}

// REFERENCE IMPLEMENTATION SMALL
int randomCharArray0100(char *s, char *r)
{
  bool critical = true;
  for (int i = 0; i < strlen(s); i++)
  {
    if (critical)
    {
      int lm = s[i] - '0';
      r[i] = random(lm + 1) + '0';
      critical = (r[i] == s[i]);
    }
    else
    {
      r[i] = random(10) + '0';
    }
  }
  r[strlen(s)] = '\0';
}

Performance is ~0.5uSEc per char worse, so not to bad.
(sketch size 5,312)

To investigate/improve the evenly distribution of the additional digit.