SHARE
TWEET

Untitled

a guest Mar 24th, 2019 62 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <math.h>
  3. #include <vector>
  4. #include <random>
  5. #include <chrono>
  6. #include <fstream>
  7.  
  8. using namespace std;
  9.  
  10. uint64_t powmod(uint64_t base, uint64_t exp, uint64_t modulo)
  11. {
  12.     unsigned res = 1;
  13.  
  14.     while (exp != 0)
  15.     {
  16.         if ((exp & 1) != 0)
  17.         {
  18.             res = (1ll * res * base) % modulo;
  19.         }
  20.  
  21.         base = (1ll * base * base) % modulo;
  22.         exp >>= 1;
  23.     }
  24.  
  25.     return res;
  26. }
  27.  
  28. vector<uint64_t> factorize(uint64_t base) {
  29.     vector<uint64_t> result;
  30.  
  31.     uint64_t possible_divider = 2;
  32.  
  33.     while(base > 1) {
  34.         if (base % possible_divider == 0) {
  35.             base = base / possible_divider;
  36.             result.push_back(possible_divider);
  37.         }
  38.         else {
  39.             ++possible_divider;
  40.         }
  41.     }
  42.  
  43.     return result;
  44. }
  45.  
  46. int main() {
  47.     fstream input("primes.in", ios::in);
  48.     fstream output("roots.out", ios::out);
  49.  
  50.     uint64_t num;
  51.     input >> num;
  52.     std::mt19937 gen(static_cast<unsigned>(time(nullptr)));
  53.  
  54.     for (int i = 0; i < num; ++i) {
  55.         uint64_t prime_in;
  56.         input >> prime_in;
  57.         uint64_t minus_1 = prime_in - 1;
  58.         vector<uint64_t> dividers = factorize(minus_1);
  59.         bool root_not_found = true;
  60.         int root = -1;
  61.  
  62.         for(int j = 0; j < 1000 && root_not_found; ++j) {
  63.             uint64_t r = gen() % (prime_in - 3) + 2;
  64.             uint64_t prev_divider = 0;
  65.             bool is_root = true;
  66.  
  67.             for(int k = 0; k < dividers.size() && is_root; ++k) {
  68.                 if (dividers[k] != prev_divider) {
  69.                     // do smth
  70.                     uint64_t power = minus_1 / dividers[k];
  71.                     uint64_t r_pow = powmod(r, power, prime_in);
  72.                     prev_divider = dividers[k];
  73.  
  74.                     if (r_pow == 1) {
  75.                         is_root = false;
  76.                     }
  77.                 }
  78.             }
  79.  
  80.             if (is_root) {
  81.                 root_not_found = false;
  82.                 root = r;
  83.             }
  84.         }
  85.  
  86.         output << root << "\n";
  87.     }
  88.  
  89.     input.close();
  90.     output.close();
  91.  
  92.     return 0;
  93. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top