test_angrepp.c (4708B)
1 #include <assert.h> 2 #include <flint.h> 3 #include <fmpz.h> 4 #include <fmpz_vec.h> 5 #include <stdio.h> 6 #include <stdlib.h> 7 8 #include "cyclefind.h" 9 #include "pierre.h" 10 #include "prodtree.h" 11 #include "smallfactor.h" 12 #include "wiener.h" 13 #include "hnp.h" 14 #include "context.h" 15 #include "bloom.h" 16 17 static uint64_t 18 test_f(uint64_t x) 19 { 20 return (3 * x + 7) % 18; 21 } 22 23 static void 24 test_cyclefind_floyd(void) 25 { 26 uint64_t lambda, mu; 27 lambda = cyclefind_floyd(&mu, 4, &test_f); 28 29 assert(lambda == 2); 30 assert(mu == 1); 31 } 32 33 static void 34 test_cyclefind_brent(void) 35 { 36 uint64_t lambda, mu; 37 lambda = cyclefind_brent(&mu, 4, &test_f); 38 39 assert(lambda == 2); 40 assert(mu == 1); 41 } 42 43 static void 44 test_pierre_factor(void) 45 { 46 fmpz_t n, r; 47 ctx_t ctx; 48 49 ctx_init(&ctx); 50 fmpz_init(n); 51 fmpz_init(r); 52 53 fmpz_set_str(n, "13957163057215389251", 10); 54 55 fermat_factor(&ctx, r, n, 200); 56 57 assert(fmpz_divisible(n, r)); 58 assert(fmpz_cmp_ui(r, 1) > 0); 59 60 ctx_clear(&ctx); 61 fmpz_clear(n); 62 fmpz_clear(r); 63 } 64 65 static void 66 test_wiener_factor_small_d(void) 67 { 68 fmpz_t N, e, res; 69 ctx_t ctx; 70 int ret; 71 72 fmpz_init(N); 73 fmpz_init(e); 74 fmpz_init(res); 75 76 ctx_init(&ctx); 77 ctx_require(&ctx, 10, 5); 78 79 fmpz_set_str(N, "32193226917433121", 10); 80 fmpz_set_str(e, "8403467516040173", 10); 81 82 ret = wiener_factor_small_d(&ctx, res, e, N); 83 84 assert(ret == 1); 85 assert(fmpz_divisible(N, res)); 86 assert(fmpz_cmp_ui(res, 1) > 0); 87 88 fmpz_clear(N); 89 fmpz_clear(e); 90 fmpz_clear(res); 91 92 ctx_clear(&ctx); 93 } 94 95 static void 96 test_smallfactor_euclidean(void) 97 { 98 fmpz_t N, res; 99 ctx_t ctx; 100 101 int ret; 102 fmpz_init(N); 103 fmpz_init(res); 104 105 ctx_init(&ctx); 106 ctx_set_precomputed_primorial(&ctx); 107 ctx_set_precomputed_smallprimes(&ctx); 108 109 // N = 61363 * 1278934673 110 fmpz_set_str(N, "78607161806599", 10); 111 112 ret = smallfactor_euclidean(&ctx, res, N); 113 114 assert(ret == SMALLFACTOR_FOUND); 115 assert(fmpz_divisible(N, res)); 116 assert(fmpz_cmp_ui(res, 1) > 0); 117 assert(fmpz_cmp(res, N) < 0); 118 119 ctx_clear(&ctx); 120 fmpz_clear(N); 121 fmpz_clear(res); 122 } 123 124 static void 125 test_prodtree(void) 126 { 127 fmpz_t tre, fem, sju; 128 fmpz_init_set_ui(tre, 3); 129 fmpz_init_set_ui(fem, 5); 130 fmpz_init_set_ui(sju, 7); 131 132 fmpz v[3] = {tre[0], fem[0], sju[0]}; 133 fmpz *res; 134 slong lres = prodtree_compute(&res, v, 3); 135 136 assert(lres == 7); 137 138 assert(fmpz_cmp_ui(&res[0], 3) == 0); 139 assert(fmpz_cmp_ui(&res[1], 5) == 0); 140 assert(fmpz_cmp_ui(&res[2], 7) == 0); 141 assert(fmpz_cmp_ui(&res[3], 1) == 0); 142 assert(fmpz_cmp_ui(&res[4], 15) == 0); 143 assert(fmpz_cmp_ui(&res[5], 7) == 0); 144 assert(fmpz_cmp_ui(&res[6], 105) == 0); 145 146 _fmpz_vec_clear(res, lres); 147 148 fmpz_clear(tre); 149 fmpz_clear(fem); 150 fmpz_clear(sju); 151 } 152 153 static void 154 test_hidden_number_problem(void) 155 { 156 fmpz *r, *t, *a; 157 fmpz_t n, B; 158 159 fmpz_init_set_ui(n, 131101); 160 fmpz_init_set_ui(B, 11); 161 162 r = _fmpz_vec_init(4); 163 t = _fmpz_vec_init(3); 164 a = _fmpz_vec_init(3); 165 166 fmpz_set_ui(&t[0], 46396); 167 fmpz_set_ui(&t[1], 3185); 168 fmpz_set_ui(&t[2], 30618); 169 170 fmpz_set_ui(&a[0], 65911); 171 fmpz_set_ui(&a[1], 5049); 172 fmpz_set_ui(&a[2], 56983); 173 174 int ret = hidden_number_problem(r, 4, t, a, 3, n, B); 175 176 assert(ret == 0); 177 assert(fmpz_cmp_si(&r[0], -4) == 0); 178 assert(fmpz_cmp_si(&r[1], -10) == 0); 179 assert(fmpz_cmp_si(&r[2], -6) == 0); 180 assert(fmpz_cmp_si(&r[3], -42028) == 0); 181 182 _fmpz_vec_clear(r, 4); 183 _fmpz_vec_clear(t, 3); 184 _fmpz_vec_clear(a, 3); 185 186 fmpz_clear(n); 187 fmpz_clear(B); 188 } 189 190 static void 191 test_bloom(void) 192 { 193 const uint64_t k = 10; 194 const uint64_t m = 1000000; 195 const uint64_t n = 800; 196 size_t i; 197 bloom_t bloom; 198 199 bloom_init(&bloom, k, m); 200 201 flint_rand_t state; 202 flint_randinit(state); 203 204 fmpz *v = _fmpz_vec_init(n); 205 for (i = 0; i < n; i++) { 206 fmpz_randtest_unsigned(&v[i], state, 4096); 207 } 208 209 for (i = 0; i < n; i++) { 210 bloom_insert(&bloom, &v[i]); 211 } 212 213 for (i = 0; i < n; i++) { 214 assert(bloom_prob_contains(&bloom, &v[i])); 215 } 216 217 fmpz_t t; 218 fmpz_init(t); 219 220 size_t loops = 0; 221 int inlist; 222 while (loops < 10000) { 223 fmpz_randtest_unsigned(t, state, 4096); 224 inlist = 0; 225 for (i = 0; i < n; i++) { 226 if (fmpz_cmp(t, &v[i]) == 0) { 227 inlist = 1; 228 break; 229 } 230 } 231 232 if (inlist) { 233 continue; 234 } 235 236 if (bloom_prob_contains(&bloom, t)) { 237 fprintf(stderr, "An 1.0694557203850693e-29 per cent likely event occured, you must be very unlucky.\n"); 238 } 239 240 loops++; 241 } 242 243 fmpz_clear(t); 244 flint_randclear(state); 245 246 bloom_clear(&bloom); 247 _fmpz_vec_clear(v, n); 248 } 249 250 int 251 main(void) 252 { 253 test_cyclefind_floyd(); 254 test_cyclefind_brent(); 255 test_pierre_factor(); 256 test_wiener_factor_small_d(); 257 test_smallfactor_euclidean(); 258 test_prodtree(); 259 test_hidden_number_problem(); 260 test_bloom(); 261 262 printf("test ok\n"); 263 }