"""h5_verifier_B.py -- source of verifier B (C), compiled and run by h5_verify.py.""" SOURCE = r"""/* h5_verifier_B.c -- verifier B for the H_5 tuple, independent of verifier A (h5_verify.py). The tuple: x in [-A, B], x = +-1 (if pm1) or x = +-q with q prime, 10^7 < q, except the pairs +-p of class 0 and the removed elements. Checks: cardinality K; for EVERY prime p <= K an empty class (p <= 10^7: class 0, along all multiples of p; 10^7 < p: the class of the file, along the progression on both sides); counts the pairs further apart than D with two cursors. usage: ./vb cp.u32 residues.u32 removed|- pm1 A B D budget */ #include #include #include #include #define K 232465000LL typedef uint8_t u8; #define GB(a,x) ((a[(x)>>3]>>((x)&7))&1) #define SB(a,x) (a[(x)>>3]|=(u8)(1<<((x)&7))) #define CB(a,x) (a[(x)>>3]&=(u8)~(1<<((x)&7))) int main(int argc, char **argv){ if (argc < 9) { printf("usage\n"); return 2; } long long A = atoll(argv[5]), B = atoll(argv[6]), D = atoll(argv[7]), budget = atoll(argv[8]); int pm1 = atoi(argv[4]); long long M = (A > B ? A : B) + 1; /* sieve of Eratosthenes on [0, M], one bit per integer */ u8 *comp = calloc(M / 8 + 2, 1); SB(comp, 0); SB(comp, 1); for (long long i = 2; i * i <= M; i++) if (!GB(comp, i)) for (long long j = i * i; j <= M; j += i) SB(comp, j); FILE *f = fopen(argv[1], "rb"); fseek(f, 0, SEEK_END); long n = ftell(f) / 4; rewind(f); uint32_t *cp = malloc(4 * n), *res = malloc(4 * n); if (fread(cp, 4, n, f) != (size_t)n) return 3; fclose(f); f = fopen(argv[2], "rb"); if (fread(res, 4, n, f) != (size_t)n) return 3; fclose(f); /* membership: pos[x], neg[x] for x in [0, M] */ u8 *pos = calloc(M / 8 + 2, 1), *neg = calloc(M / 8 + 2, 1); for (long long x = 10000001; x <= M; x++) if (!GB(comp, x)) { if (x <= B) SB(pos, x); if (x <= A) SB(neg, x); } if (pm1) { SB(pos, 1); SB(neg, 1); } for (long i = 0; i < n; i++) if (res[i] == 0) { long long p = cp[i]; if (p <= M) { CB(pos, p); CB(neg, p); } } long nrm = 0; if (strcmp(argv[3], "-")) { f = fopen(argv[3], "r"); long long x; while (fscanf(f, "%lld", &x) == 1) { long long a = x > 0 ? x : -x; u8 *t = x > 0 ? pos : neg; if (a > M || !GB(t, a)) { if ((x > 0 && a <= B) || (x < 0 && a <= A)) { printf("removed element absent %lld\n", x); return 1; } continue; } CB(t, a); nrm++; } fclose(f); } free(comp); long long card = 0; for (long long x = 0; x <= M; x++) card += GB(pos, x) + GB(neg, x); printf("cardinality %lld (expected %lld), removed elements applied %ld\n", card, K, nrm); fflush(stdout); if (card != K) { printf("FAILURE cardinality\n"); return 1; } /* primes p <= K: own sieve up to K */ u8 *c2 = calloc(K + 1, 1); for (long long i = 2; i * i <= K; i++) if (!c2[i]) for (long long j = i * i; j <= K; j += i) c2[j] = 1; long long np = 0, bad = 0, idx = 0; for (long long p = 2; p <= K; p++) { if (c2[p]) continue; np++; long long r; if (p <= 10000000) r = 0; else { while (idx < n && cp[idx] < p) idx++; if (idx >= n || cp[idx] != p) { printf("prime %lld missing from the certificate\n", p); return 1; } r = res[idx]; } /* positive x = r (mod p); negative -x = r (mod p) <=> x = (p - r) mod p */ int hit = 0; for (long long x = r; x <= B && !hit; x += p) if (GB(pos, x)) hit = 1; for (long long x = (p - r) % p; x <= A && !hit; x += p) if (GB(neg, x)) hit = 1; if (hit) { bad++; if (bad < 10) printf("p = %lld: class %lld hit\n", p, r); } } printf("primes p <= K: %lld, failures: %lld\n", np, bad); fflush(stdout); /* long pairs: x_j - x_i > D; only (negative, positive) pairs can exceed D (A, B < D) */ if (A >= D || B >= D) { printf("D too small for this count\n"); return 1; } /* pour chaque negatif -a, nombre de positifs b > D - a ; cumul des positifs depuis le haut */ /* two cursors: a increasing, threshold t = D - a + 1 decreasing; cnt = number of positive entries >= t */ long long lp = 0, lp1 = 0, cnt = 0, cur = B + 1, cnt1 = 0, cur1 = B + 1; for (long long a = 0; a <= A; a++) if (GB(neg, a)) { long long t = D - a + 1, t1 = D - a; if (t < 0) t = 0; if (t1 < 0) t1 = 0; while (cur > t) { cur--; cnt += GB(pos, cur); } while (cur1 > t1) { cur1--; cnt1 += GB(pos, cur1); } lp += cnt; lp1 += cnt1; } printf("pairs further apart than %lld: %lld (budget %lld); further apart than %lld: %lld\n", D, lp, budget, D - 1, lp1); int ok = bad == 0 && lp <= budget; printf("verifier B: %s\n", ok ? "ADMISSIBLE, WITHIN THE BUDGET" : "FAILURE"); return !ok; } """