fork download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3.  
  4. template <typename R, typename S, typename T>
  5. T POW(R base, S exponent, const T mod){
  6.     T result = 1;
  7.     while (exponent){
  8.         if (exponent & 1)
  9.             result = (result * base) % mod;
  10.         exponent >>= 1;
  11.         base = (base * base) % mod;
  12.     }
  13.     return result;
  14. }
  15.  
  16. // used uint64_t to prevent overflow, but only testing with small numbers for now
  17. bool MillerRabin_FIPS186(uint64_t w, unsigned int iterations = 50){
  18.     srand(time(0));
  19.     unsigned int a = 0;
  20.     uint64_t W = w - 1; // dont want to keep calculating w - 1
  21.     uint64_t m = W;
  22.     while (!(m & 1)){
  23.         m >>= 1;
  24.         a++;
  25.     }
  26.  
  27.     // skipped getting wlen
  28.     // when i had this function using my custom arbitrary precision integer class,
  29.     // and could get len(w), getting it and using it in an actual RBG 
  30.     // made no difference 
  31.  
  32.     for(unsigned int i = 0; i < iterations; i++){
  33.         uint64_t b = (rand() % (W - 3)) + 2; // 2 <= b <= w - 2
  34.         uint64_t z = POW(b, m, w);
  35.         if ((z == 1) || (z == W))
  36.             continue;
  37.         else
  38.             for(unsigned int j = 1; j < a; j++){
  39.                 z = POW(z, 2, w);
  40.                 if (z == W)
  41.                     break;
  42.                 if (z == 1)
  43.                     return 0;// Composite
  44.             }
  45.     }
  46.     return 1;// Probably Prime
  47. }
  48.  
  49. int main() {
  50. 	std::cout << MillerRabin_FIPS186(33) << std::endl;
  51. 	std::cout << MillerRabin_FIPS186(35) << std::endl;
  52. 	std::cout << MillerRabin_FIPS186(37) << std::endl;
  53. 	std::cout << MillerRabin_FIPS186(39) << std::endl;
  54. 	std::cout << MillerRabin_FIPS186(45) << std::endl;
  55. 	std::cout << MillerRabin_FIPS186(49) << std::endl;
  56. 	return 0;
  57. }
Success #stdin #stdout 0.01s 2684KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
1
1
1
0
1
https://ideone.com/xoDHx
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!