Advertisement
gchilders

Untitled

Jun 22nd, 2022
41
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.87 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <gmp.h>
  3.  
  4. int is_prime(mpz_t n) {
  5.  
  6. unsigned long j, r;
  7. int prime = 0;
  8. mpz_t d, a, x, n_sub_1;
  9. mpz_inits(d, a, x, n_sub_1, NULL);
  10.  
  11. mpz_sub_ui(n_sub_1, n, 1);
  12. r = mpz_scan1(n_sub_1, 0);
  13. mpz_fdiv_q_2exp(d, n_sub_1, r);
  14.  
  15. mpz_set_ui(a, 3);
  16. mpz_powm(x, a, d, n);
  17.  
  18. if (mpz_cmp_ui(x, 1) == 0 || mpz_cmp(x, n_sub_1) == 0) {
  19. mpz_clears(d, a, x, n_sub_1, NULL);
  20. return 1;
  21. }
  22.  
  23. for (j = 0; j < r-1; j++) {
  24. mpz_powm_ui(x, x, 2, n);
  25. if (mpz_cmp_ui(x, 1) == 0) break;
  26. if (mpz_cmp(x, n_sub_1) == 0) {
  27. prime = 1;
  28. break;
  29. }
  30. }
  31.  
  32. mpz_clears(d, a, x, n_sub_1, NULL);
  33. return prime;
  34. }
  35.  
  36. int main(int argc, char **argv) {
  37. mpz_t n;
  38. mpz_init(n);
  39. mpz_set_str(n, argv[1], 10);
  40. if (is_prime(n)) printf("prp\n");
  41. else printf("composite\n");
  42. mpz_clear(n);
  43. }
  44.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement