93 lines
2.1 KiB
C++
93 lines
2.1 KiB
C++
#include <cmath>
|
|
#include <iostream>
|
|
|
|
// Konstanten aus der Angabe
|
|
#define n 12
|
|
#define k 6
|
|
#define L 15
|
|
|
|
// Liste der Primzahlen. Durch die oben angeführten Konstanten ist
|
|
// sichergestellt dass diese eindeutig sind
|
|
uint16_t listofPrimes[L];
|
|
|
|
// Random n-bits Zahl generieren. MSB ist immer 1
|
|
uint16_t createRandomNumber(uint8_t bits) {
|
|
|
|
// äquivalent zu:
|
|
// return rand() % pow(2,bits-1) + pow(2,bits-1);
|
|
|
|
uint16_t result = 1;
|
|
for (uint8_t i = 0; i < bits - 1; i++) {
|
|
result <<= 1;
|
|
result |= rand() % 2;
|
|
}
|
|
return result;
|
|
}
|
|
|
|
// Check ob eine Zahl Prim ist
|
|
bool checkPrime(int number) {
|
|
for (int i = 2; i < sqrt(number); i++) {
|
|
if (number % i == 0) {
|
|
|
|
return false;
|
|
}
|
|
}
|
|
return true;
|
|
}
|
|
|
|
// Schreibe "length" primzahlen größer als "start" in "array"
|
|
void findPrimesBiggerThan(uint16_t *array, int length, int start) {
|
|
for (int i = 0; i < length; i++) {
|
|
while (!checkPrime(start)) {
|
|
start++;
|
|
}
|
|
array[i] = start;
|
|
start++;
|
|
}
|
|
}
|
|
|
|
// die zwei Zahlen die Alice und Bob aussuchen werden
|
|
int xAlice;
|
|
int xBob;
|
|
|
|
// Daten die an Bob übermittelt werden. j = x_A mod p_i. Bob antwortet mit Bool
|
|
bool transmitToBob(int i, int j) {
|
|
|
|
if (j != (xBob % listofPrimes[i])) {
|
|
return false;
|
|
}
|
|
return true;
|
|
}
|
|
|
|
int main() {
|
|
// rand() mit timestamp seeden
|
|
srand(time(NULL));
|
|
|
|
// Primzahlen für Alice und Bob initialisieren
|
|
findPrimesBiggerThan(listofPrimes, L, pow(2, k));
|
|
|
|
// Alice sucht ein i zw. 1 und L aus
|
|
int iAlice = rand() % (L - 1) + 1;
|
|
|
|
// Counter für false positives
|
|
int falseCounter = 0;
|
|
|
|
long long iterations = 1000000;
|
|
for (int i = 0; i < iterations; i++) {
|
|
// Alice und Bob suchen 2 Zahlen aus
|
|
xAlice = createRandomNumber(n);
|
|
xBob = createRandomNumber(n);
|
|
|
|
// false positive, wenn Bob behauptet die Zahlen wären gleich, sie es aber
|
|
// nicht sind
|
|
if (transmitToBob(iAlice, xAlice % listofPrimes[iAlice]) &&
|
|
xAlice != xBob) {
|
|
falseCounter++;
|
|
}
|
|
}
|
|
|
|
// false-positive rate in Prozent. Empirisch: ca. 1%
|
|
std::cout << "False positivity rate: "
|
|
<< 100 * (float)(falseCounter) / iterations << "%" << std::endl;
|
|
}
|