function permuteQPR() lacks with: prime=19448089 , x1=3721041 , x2=15256836 #3
Description
#include <stdio.h>
static const unsigned int prime = 19448089;
unsigned int permuteQPR(unsigned int x)
{
if (x >= prime)
return x; // The 5 integers out of range are mapped to themselves.
unsigned int residue = ((unsigned long long) x * x) % prime;
return (x <= prime / 2) ? residue : prime - residue;
}
#define CALC(x) { \
printf("value: %u permute: %u\n",x,permuteQPR(x)); \
}while(0)
void main(void) {
CALC(0);
CALC(3721041);
CALC(15256836);
CALC(prime);
CALC(0xFFFFFFFF);
}
output is:
value: 0 permute: 0
value: 3721041 permute: 1367775
value: 15256836 permute: 1367775
value: 19448089 permute: 19448089
value: 4294967295 permute: 4294967295
same number 1367775 !