# 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?

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?

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

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

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__);

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

``````//
//    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__);

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!

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__);

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__);

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__);

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__);

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.