# C++ Program to Implement Naor-Reingold Pseudo Random Function

«
»
This is a C++ Program to genrate random numbers using Naor-Reingold random function. Moni Naor and Omer Reingold described efficient constructions for various cryptographic primitives in private key as well as public-key cryptography. Their result is the construction of an efficient pseudorandom function. Let p and l be prime numbers with l |p-1. Select an element g ? {\mathbb F_p}^* of multiplicative order l. Then for each n-dimensional vector a = (a1, …, an)? (\mathbb F_{l})^{n} they define the function

f_{a}(x) = g^{a_{1}^{x_{1}} a_{2}^{x_{2}}…a_{n}^{x_{n}}} \in \mathbb F_p

where x = x1 … xn is the bit representation of integer x, 0 = x = 2^n-1, with some extra leading zeros if necessary.

Here is source code of the C++ Program to Implement Naor-Reingold Pseudo Random Function. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

1. #include <iostream>
2. #include <math.h>
3. #include <stdlib.h>
4. 
5. using namespace std;
6. 
7. int main(int argc, char **argv)
8. {
9.     int p = 7, l = 3, g = 2, n = 4, x;
10.     int a[] = { 1, 2, 2, 1 };
11.     int bin[4];
12.     cout << "The Random numbers are: ";
13.     for (int i = 0; i < 10; i++)
14.     {
15.         x = rand() % 16;
16.         for (int j = 3; j >= 0; j--)
17.         {
18.             bin[j] = x % 2;
19.             x /= 2;
20.         }
21.         int mul = 1;
22.         for (int k = 0; k < 4; k++)
23.             mul *= pow(a[k], bin[k]);
24.         cout << pow(g, mul)<<" ";
25.     }
26. }

Output:

$g++ Naor-Reingold.cpp$ a.out

The Random numbers are:
2 4 16 4 2 4 16 16 4 2

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

Here’s the list of Best Books in C++ Programming, Data Structures and Algorithms.