find seed for modified rand()

[cursedbyfreud]

As you know,sourcode of rand() of c++ use three parameters, one is seed, one is a and other is c. a and c parameters have some defined integer value by c++. I have a 1000 random numbers given, so I am suppose to modify a and c values and find the seed value that will give these 1000 random numbers. This process seems easy, but the random numbers returned by c++ is:
return (seed >> 16) & 0x7fff;
so, each time, first 16 bits of seed value are taken and given as random. But I dont know how to find seed, a and c from this 1000 random numbers. Please,I can use any kind of information.

[helios]

See my last post here: http://www.cplusplus.com/forum/general/12029/

I've already brute-forced the formula N(i)=((N(i-1)*a+b)>>c)&0x7FFF for all possible values of a and b up to one million, and all possible values of c that make sense. I haven't found anything.
I can give you the source code for the brute-forcer, if you want, but it won't do you any good unless you have access to a supercomputer or a lot of time. I estimate a Core 2 Duo @ 1.86 GHz working continuously for a week could find a solution if it exists, which I doubt it. A Core 2 Quad at the same frequency could half that time.

[cursedbyfreud]

I know but the idea must be finding parameters from given random number results. Each ramdom result is the first 16 bit of the N(i). To find N(i), I took first random number that is first 16 bits of N(i), then I put the rest 16 bits 0, then I found N(i) value, and repeated it. However it doesnt make sense, because they can be 1s, or after the multiplication with a, the number can go beyond 32 bits. I really dont know what to do.

[helios]

The only method I can think of is brute force.

Let's suppose N(1) and N(0) are two known 32-bit integers, and have already been ANDed to 0x7FFF, which means that they only contains 15 meaningful bits, which I'll represent as m. Given that N(i)=((N(i-1)*a+b)>>16)&0x7FFF, N(0) almost equals ((N(1)<<16)-b)/a. I say almost, because once you've left-shifted the integer by sixteen, you have 17 bits with meaningless values:
Before:
???? ???? ?mmm mmm
After:
?mmm mmmm ???? ????
Before continuing with the calculation, those bits have to be assigned meaningful values. There are 2^17 possibilities.
After that, you still have two more independent variables: a and b. Each of which is a 32-bits long. That's another 2^64 possibilities.
All in all, you end up having to perform a check 2^81 times. I don't know of any way around this.

[cursedbyfreud]

 
#include <stdlib.h>
#include <stdio.h>
#include <time.h>

static unsigned int seed = 5400;

int randomer(int a, int c){
	seed = seed * a+c;
    return (seed >> 16) & 0x7fff;
}

int main( void )
{
   int i;int a; int c; int k;int m;int sayi;

srand( (unsigned int) seed);
	k=0;m=0;
   /* Display 10 numbers. */
   for(a=1;a<1000;a++){
	   for(c=1;c<99999;c++){
		   for( i = 1; i <4;i++ ){
			   sayi=randomer(a,c);
			   if (i==1&&sayi==17678)
					k=1;
			   if(i==2&&sayi==24994&&k==1)
					m=1;
			   if (i==3&&sayi==3327&&m==1){				   
						printf( "a=  %6d\n",a);
						printf("c=  %6d\n",c);}
	   }
   }
   }
}

I wrote this code. but when I try the result(printed) a and c numbers, they dont give the random numbers 17678,24994 or 3327. Where is the problem here? Did I write the code wrong?I am not sure about if statements, please any help?

[jsmith]

What about this idea?

The formula, to reiterate, is:

N(i) = ( a * N(i-1) + b ) >> 16

In a list of 1000 numbers, you have 999 pairs ( N(i), N(i-1) ). If you take the first pair
and substitute it in the above equation, you have an equation in two unknowns (a,b).
Compute all pairs (A',B') that satisfy the equation and store them in a data structure.

Next, take the second pair, substitute it in the above equation, then run through all
pairs (A',B'), eliminating the pairs that do not satisfy the equation.

Repeat with subsequent pairs until you are left with one pair (A',B') in the data
structure. This pair must be (a,b).


EDIT: Now obviously if a and b are 32 bits, you cannot brute force all combinations.
You have to be smarter: run a for() loop for all a and compute the b value required
to solve the equation.

[cursedbyfreud]

yeah, I wish it was that easy, but after 16 bit shiftin (>>16) also an AND operation done, and the rest of the bits are erased. also N(i) is not equal to ( a * N(i-1) + b ) >> 16. N(i) is the result of operation ( a * N(i-1) + b ) and the returned value is shifted and AND ed value of N(i), but the shifted and AND ed result is not equal to N(i). So your idea is not correct, I wish it was.

[jsmith]

Yes, I just realized that...

thinking... please wait...

[helios]

Damn. What a waste of time.
I just figured out the values for a and b. I'll just brute-force the last 2^17 possibilities and to hell with it.

EDIT: Well, I officially give up. I hit a brick wall.
I thought the values of a and b were the same as VC++'s, but I can only guess as far as as one position ahead. For example, going from N(0), I can guess the value of N(1), but after that, something is different in my formula and N(2) can't be guessed.
I think I'm in position of saying that this is not just a linear congruential generator.