Simple AES chat program
Vous ne pouvez pas sélectionner plus de 25 sujets Les noms de sujets doivent commencer par une lettre ou un nombre, peuvent contenir des tirets ('-') et peuvent comporter jusqu'à 35 caractères.

sgprime.c 13KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577
  1. // This value is tuned for generating large keys, or small keys many times. Higher values see
  2. // diminishing returns in efficiency (and though I cannot prove it, I believe that there is no
  3. // upper bound on the efficiency attainable by setting it higher, but it just isn't worth it.)
  4. // The larger this number, the longer build_sieve() will take (and thus make_difflist()). Also,
  5. // larger values of this number will use more memory. I wouldn't recommend setting it any higher,
  6. // but for generating small numbers of small keys, setting it lower is a good idea.
  7. // Another thing I forgot: Larger values will tend to make multithreaded searches where the
  8. // number of threads is not a multiple of many small primes whose primorial is less then this
  9. // number take much longer and use more memory.
  10. #define PRIMORIAL_CAP_CAP 1000000
  11. #include <stdlib.h>
  12. #include <stdio.h>
  13. #include <pthread.h>
  14. #include <errno.h>
  15. #include <gmp.h>
  16. struct mpz_list
  17. {
  18. unsigned long int numel;
  19. unsigned long int capacity;
  20. mpz_t *data;
  21. };
  22. void mpz_list_init(struct mpz_list *list, unsigned long int capacity)
  23. {
  24. list->numel = 0;
  25. list->capacity = capacity;
  26. list->data = malloc(capacity * sizeof(mpz_t));
  27. }
  28. // Push an element to the list
  29. mpz_t *mpz_list_push(struct mpz_list *list)
  30. {
  31. if (list->numel == list->capacity)
  32. {
  33. list->capacity <<= 1;
  34. list->data = realloc(list->data, list->capacity * sizeof(mpz_t));
  35. }
  36. mpz_init(list->data[list->numel]);
  37. list->numel++;
  38. return &(list->data[list->numel - 1]);
  39. }
  40. // Free the memory in a list
  41. void destroy_mpz_list(struct mpz_list *list)
  42. {
  43. int ii;
  44. for (ii = 0; ii < list->numel; ii++)
  45. mpz_clear(list->data[ii]);
  46. free(list->data);
  47. }
  48. struct ui_list
  49. {
  50. unsigned long int numel;
  51. unsigned long int capacity;
  52. unsigned long int *data;
  53. };
  54. void ui_list_init(struct ui_list *list, unsigned long int capacity)
  55. {
  56. list->numel = 0;
  57. list->capacity = capacity;
  58. list->data = malloc(capacity * sizeof(unsigned long int));
  59. }
  60. // Push an element to the list
  61. unsigned long int *ui_list_push(struct ui_list *list)
  62. {
  63. if (list->numel == list->capacity)
  64. {
  65. list->capacity <<= 1;
  66. list->data = realloc(list->data, list->capacity * sizeof(unsigned long int));
  67. }
  68. list->numel++;
  69. return &(list->data[list->numel - 1]);
  70. }
  71. // Free the memory in a list
  72. void destroy_ui_list(struct ui_list *list)
  73. {
  74. free(list->data);
  75. }
  76. // Reuse all the variables to prevent from having to allocate memory
  77. struct sieve_state
  78. {
  79. mpz_t root;
  80. };
  81. // Use a sieve to test primality of n
  82. int test_with_sieve(struct mpz_list *sieve, struct sieve_state state, mpz_t n)
  83. {
  84. int ii;
  85. mpz_sqrt(state.root, n);
  86. int iters = mpz_get_ui(state.root);
  87. if (sieve->numel < iters)
  88. iters = sieve->numel;
  89. for (ii = 0; ii < iters; ii++)
  90. {
  91. if (mpz_divisible_p(n, sieve->data[ii]))
  92. return 0;
  93. }
  94. return 1;
  95. }
  96. // Build a sieve until the primorial of the value being tested is above a certain value
  97. unsigned long int build_sieve(unsigned long int max_primorial, struct mpz_list **sieve_out)
  98. {
  99. struct mpz_list *sieve = malloc(sizeof(struct mpz_list));
  100. mpz_list_init(sieve, 16);
  101. struct sieve_state state;
  102. mpz_init(state.root);
  103. unsigned long int primorial = 1;
  104. mpz_t c;
  105. mpz_init(c);
  106. mpz_set_ui(c, 2);
  107. while (1)
  108. {
  109. unsigned long int ic = mpz_get_ui(c);
  110. if (test_with_sieve(sieve, state, c))
  111. {
  112. if (primorial * ic > max_primorial)
  113. break;
  114. primorial *= ic;
  115. mpz_set(*mpz_list_push(sieve), c);
  116. }
  117. mpz_add_ui(c, c, 1);
  118. }
  119. mpz_clear(state.root);
  120. mpz_clear(c);
  121. *sieve_out = sieve;
  122. return primorial;
  123. }
  124. //unsigned long int build_totant_list(unsigned long int n, struct mpz_list **list_out)
  125. //{
  126. // struct mpz_list *list = malloc(sizeof(struct mpz_list));
  127. // mpz_list_init(list, 16);
  128. //
  129. // mpz_t c, g;
  130. // mpz_init(c);
  131. // mpz_init(g);
  132. // mpz_set_ui(c, 1);
  133. //
  134. // while (mpz_cmp_ui(c, n) != 0)
  135. // {
  136. // mpz_gcd_ui(g, c, n);
  137. // if (mpz_cmp_ui(g, 1) == 0)
  138. // {
  139. // mpz_set(*mpz_list_push(list), c);
  140. // }
  141. //
  142. // mpz_add_ui(c, c, 1);
  143. // }
  144. //
  145. // mpz_clear(c);
  146. // mpz_clear(g);
  147. //
  148. // *list_out = list;
  149. // return list->numel;
  150. //}
  151. unsigned long int build_sgprime_candidate_list(unsigned long int n, struct mpz_list **list_out)
  152. {
  153. struct mpz_list *list = malloc(sizeof(struct mpz_list));
  154. mpz_list_init(list, 16);
  155. mpz_t c, g, u;
  156. mpz_init(c);
  157. mpz_init(g);
  158. mpz_init(u);
  159. mpz_set_ui(c, 1);
  160. while (mpz_cmp_ui(c, n) != 0)
  161. {
  162. mpz_gcd_ui(g, c, n);
  163. if (mpz_cmp_ui(g, 1) == 0)
  164. {
  165. mpz_add(u, c, c);
  166. mpz_add_ui(u, u, 1);
  167. if (mpz_cmp_ui(u, n) > 0)
  168. mpz_sub_ui(u, u, n);
  169. mpz_gcd_ui(g, u, n);
  170. if (mpz_cmp_ui(g, 1) == 0)
  171. {
  172. mpz_set(*mpz_list_push(list), c);
  173. }
  174. }
  175. mpz_add_ui(c, c, 1);
  176. }
  177. mpz_clear(c);
  178. mpz_clear(g);
  179. mpz_clear(u);
  180. *list_out = list;
  181. return list->numel;
  182. }
  183. //unsigned long int build_sgnprime_candidate_list(int niter, unsigned long int n, struct mpz_list **list_out)
  184. //{
  185. // struct mpz_list *list = malloc(sizeof(struct mpz_list));
  186. // mpz_list_init(list, 16);
  187. //
  188. // mpz_t c, g, u;
  189. // mpz_init(c);
  190. // mpz_init(g);
  191. // mpz_init(u);
  192. // mpz_set_ui(c, 1);
  193. //
  194. // while (mpz_cmp_ui(c, n) != 0)
  195. // {
  196. // mpz_set(u, c);
  197. // mpz_gcd_ui(g, u, n);
  198. // int ii;
  199. // for (ii = 0; ii < niter ; ii++)
  200. // {
  201. // if (mpz_cmp_ui(g, 1) != 0)
  202. // goto cont;
  203. // mpz_add(u, u, u);
  204. // mpz_add_ui(u, u, 1);
  205. // if (mpz_cmp_ui(u, n) > 0)
  206. // mpz_sub_ui(u, u, n);
  207. // mpz_gcd_ui(g, u, n);
  208. // }
  209. // mpz_set(*mpz_list_push(list), c);
  210. //cont:
  211. // mpz_add_ui(c, c, 1);
  212. // }
  213. //
  214. // mpz_clear(c);
  215. // mpz_clear(g);
  216. // mpz_clear(u);
  217. //
  218. // *list_out = list;
  219. // return list->numel;
  220. //}
  221. // This function makes the liberal assumption that each element has another one within the range of an unsigned long ahead of it.
  222. unsigned long int differentiate_list(unsigned long int max, struct mpz_list *list, struct ui_list **out_list)
  223. {
  224. if (list->numel <= 0) return 0;
  225. struct ui_list *difflist = malloc(sizeof(struct ui_list));
  226. ui_list_init(difflist, list->numel);
  227. mpz_t diff;
  228. mpz_init(diff);
  229. unsigned long int offset = mpz_get_ui(list->data[0]);
  230. unsigned long int head;
  231. for (head = 0; head < list->numel - 1; head++)
  232. {
  233. mpz_sub(diff, list->data[head + 1], list->data[head]);
  234. *ui_list_push(difflist) = mpz_get_ui(diff);
  235. }
  236. mpz_set(diff, list->data[0]);
  237. mpz_add_ui(diff, diff, max);
  238. mpz_sub(diff, diff, list->data[list->numel - 1]);
  239. *ui_list_push(difflist) = mpz_get_ui(diff);
  240. mpz_clear(diff);
  241. *out_list = difflist;
  242. return offset;
  243. }
  244. unsigned long int gcd_ui(unsigned long int a, unsigned long int b)
  245. {
  246. unsigned long int r;
  247. r = a % b;
  248. while (r)
  249. {
  250. a = b;
  251. b = r;
  252. r = a % b;
  253. }
  254. return b;
  255. }
  256. unsigned long int thread_separate_difflist(int nthreads, struct ui_list *difflist, unsigned int tid, struct ui_list **out_list)
  257. {
  258. unsigned long int llength = difflist->numel;
  259. unsigned long int plength = llength / gcd_ui(llength, nthreads);
  260. struct ui_list *list = malloc(sizeof(struct ui_list));
  261. ui_list_init(list, plength);
  262. unsigned int head = tid % llength;
  263. unsigned int ii, ij;
  264. for (ii = 0; ii < plength; ii++)
  265. {
  266. unsigned long int cum = 0;
  267. for (ij = 0; ij < nthreads; ij++)
  268. {
  269. cum += difflist->data[head];
  270. head = (head + 1) % llength;
  271. }
  272. *ui_list_push(list) = cum;
  273. }
  274. *out_list = list;
  275. unsigned long int offset = 0;
  276. for (head = 0; head < tid; head++)
  277. {
  278. offset += difflist->data[head % llength];
  279. }
  280. return offset;
  281. }
  282. // q is passed to prevent unnecessary memory allocation
  283. int test_sgprime(mpz_t p, mpz_t q, int reps)
  284. {
  285. if (mpz_probab_prime_p(p, reps))
  286. {
  287. mpz_add(q, p, p);
  288. mpz_add_ui(q, q, 1);
  289. if (mpz_probab_prime_p(q, reps))
  290. {
  291. return 1;
  292. }
  293. }
  294. return 0;
  295. }
  296. // q is passed to prevent unnecessary memory allocation
  297. int search_sgprime_iter(mpz_t a, mpz_t q, int reps, struct ui_list *difflist, int *counter, int chunksize)
  298. {
  299. int ii;
  300. for (ii = 0; ii < chunksize; ii++)
  301. {
  302. if (test_sgprime(a, q, reps))
  303. return 1;
  304. mpz_add_ui(a, a, difflist->data[(*counter)++]);
  305. if (*counter == difflist->numel)
  306. *counter = 0;
  307. }
  308. return 0;
  309. }
  310. void st_sgprime_search(mpz_t r, int reps, unsigned long int offset, struct ui_list *difflist, unsigned long int maximum)
  311. {
  312. mpz_t q;
  313. mpz_init(q);
  314. mpz_mod_ui(q, r, maximum);
  315. mpz_sub(r, r, q);
  316. mpz_add_ui(r, r, offset);
  317. int c = 0;
  318. while(!search_sgprime_iter(r, q, reps, difflist, &c, difflist->numel));
  319. mpz_clear(q);
  320. }
  321. void mt_sgprime_search_kernel(mpz_t p, int reps, unsigned long int offset, struct ui_list *difflist, unsigned long int maximum, int nthreads, int tid, pthread_mutex_t *success_mutex, int *done, int chunksize)
  322. {
  323. mpz_t q, r;
  324. mpz_init(r);
  325. mpz_init(q);
  326. mpz_set(r, p);
  327. struct ui_list *tl_difflist;
  328. int tl_offset = thread_separate_difflist(nthreads, difflist, tid, &tl_difflist);
  329. mpz_mod_ui(q, r, maximum);
  330. mpz_sub(r, r, q);
  331. mpz_add_ui(r, r, offset + tl_offset);
  332. int c = 0;
  333. while(!search_sgprime_iter(r, q, reps, tl_difflist, &c, chunksize))
  334. {
  335. if (pthread_mutex_trylock(success_mutex) == 0)
  336. {
  337. if (*done)
  338. {
  339. pthread_mutex_unlock(success_mutex);
  340. goto cleanup;
  341. }
  342. pthread_mutex_unlock(success_mutex);
  343. }
  344. }
  345. pthread_mutex_lock(success_mutex);
  346. if (!*done) // We're the first ones here
  347. mpz_set(p, r);
  348. *done = 1;
  349. pthread_mutex_unlock(success_mutex);
  350. cleanup:
  351. destroy_ui_list(tl_difflist);
  352. free(tl_difflist);
  353. mpz_clear(q);
  354. mpz_clear(r);
  355. }
  356. struct mt_sgprime_search_kernel_params
  357. {
  358. mpz_t p;
  359. int reps;
  360. unsigned long int offset;
  361. struct ui_list *difflist;
  362. unsigned long int maximum;
  363. int nthreads;
  364. int tid;
  365. pthread_mutex_t *success_mutex;
  366. int *done;
  367. int chunksize;
  368. };
  369. void *mt_sgprime_search_kernel_entry(void *v)
  370. {
  371. struct mt_sgprime_search_kernel_params *p = (struct mt_sgprime_search_kernel_params*) v;
  372. mt_sgprime_search_kernel(p->p, p->reps, p->offset, p->difflist, p->maximum, p->nthreads, p->tid, p->success_mutex, p->done, p->chunksize);
  373. free(p);
  374. return NULL;
  375. }
  376. void mt_sgprime_search(mpz_t r, int reps, unsigned long int offset, struct ui_list *difflist, unsigned long int maximum, int nthreads, int chunksize)
  377. {
  378. pthread_mutex_t *success_mutex = malloc(sizeof(pthread_mutex_t));
  379. pthread_mutex_init(success_mutex, NULL);
  380. pthread_t *threads = malloc(nthreads * sizeof(pthread_t));
  381. int done = 0;
  382. int ii;
  383. for (ii = 0; ii < nthreads; ii++)
  384. {
  385. struct mt_sgprime_search_kernel_params *p = malloc(sizeof(struct mt_sgprime_search_kernel_params));
  386. p->p[0] = r[0];
  387. p->reps = reps;
  388. p->offset = offset;
  389. p->difflist = difflist;
  390. p->maximum = maximum;
  391. p->nthreads = nthreads;
  392. p->tid = ii;
  393. p->success_mutex = success_mutex;
  394. p->done = &done;
  395. p->chunksize = chunksize;
  396. pthread_create(&threads[ii], NULL, &mt_sgprime_search_kernel_entry, p);
  397. }
  398. void *status;
  399. for (ii = 0; ii < nthreads; ii++)
  400. {
  401. pthread_join(threads[ii], &status);
  402. }
  403. free(threads);
  404. pthread_mutex_destroy(success_mutex);
  405. free(success_mutex);
  406. }
  407. struct ui_list *make_difflist(mpz_t lower_bound, unsigned long int *offset, unsigned long int *primorial)
  408. {
  409. struct mpz_list *list;
  410. unsigned long int primorial_cap;
  411. if (mpz_cmp_ui(lower_bound, PRIMORIAL_CAP_CAP) >= 0)
  412. {
  413. primorial_cap = PRIMORIAL_CAP_CAP;
  414. } else
  415. {
  416. primorial_cap = mpz_get_ui(lower_bound);
  417. }
  418. *primorial = build_sieve(primorial_cap, &list);
  419. destroy_mpz_list(list);
  420. free(list);
  421. unsigned long int totient = build_sgprime_candidate_list(*primorial, &list);
  422. struct ui_list *difflist;
  423. *offset = differentiate_list(*primorial, list, &difflist);
  424. destroy_mpz_list(list);
  425. free(list);
  426. return difflist;
  427. }
  428. void get_sg_prime(struct ui_list *difflist, unsigned long int offset, unsigned long int primorial, mpz_t search, unsigned int threads, unsigned int reps, unsigned int chunksize)
  429. {
  430. if (threads <= 1)
  431. {
  432. st_sgprime_search(search, reps, offset, difflist, primorial);
  433. } else
  434. {
  435. mt_sgprime_search(search, reps, offset, difflist, primorial, threads, chunksize);
  436. }
  437. }
  438. void destroy_difflist(struct ui_list *difflist)
  439. {
  440. destroy_ui_list(difflist);
  441. free(difflist);
  442. }
  443. //int main()
  444. //{
  445. // struct mpz_list *list;
  446. //
  447. // unsigned long int primorial = build_sieve(100000000, &list);
  448. //
  449. //// int ii;
  450. //// for (ii = 0; ii < list->numel; ii++)
  451. //// {
  452. //// printf("%lu\n", mpz_get_ui(list->data[ii]));
  453. //// }
  454. // // printf("%lu\n", primorial);
  455. //
  456. // destroy_mpz_list(list);
  457. // free(list);
  458. //
  459. // unsigned long int totient = build_sgprime_candidate_list(primorial, &list);
  460. //
  461. //// printf("finished building candidate list\n");
  462. //// fflush(stdout);
  463. //// printf("totient: %lu\n", totient);
  464. //// printf("ratio: %lu\n", primorial / totient);
  465. //
  466. // struct ui_list *difflist;
  467. //
  468. // unsigned long int offset = differentiate_list(primorial, list, &difflist);
  469. //
  470. //// printf("offset: %lu\n", offset);
  471. //
  472. // mpz_t p;
  473. // mpz_init(p);
  474. //
  475. // gmp_randstate_t rs;
  476. // gmp_randinit_default(rs);
  477. //
  478. // int bits = 32;
  479. //
  480. // int ii;
  481. // for (ii = 0; ii < 1000; ii++)
  482. // {
  483. // mpz_urandomb(p, rs, bits);
  484. // mpz_setbit(p, bits);
  485. //
  486. // mt_sgprime_search(p, 31, offset, difflist, primorial, 8, 10);
  487. //
  488. // gmp_printf("%i-bit safe prime: %Zd\n", bits, p);
  489. // }
  490. //
  491. // gmp_randclear(rs);
  492. //
  493. // mpz_clear(p);
  494. //
  495. // destroy_ui_list(difflist);
  496. // free(difflist);
  497. // destroy_mpz_list(list);
  498. // free(list);
  499. //
  500. // return 0;
  501. //}