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:

advertisement
advertisement
$ 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.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.