Миллера-Рабина тест на простоту с использованием C++ и GMP


Я в настоящее время пишу Миллера-Рабина тест на простоту с использованием C++ и GNU МП Bignum библиотека (ГМП). Как я только начал изучать С++ около суток назад, я уверен, что этот код изобилует ошибками и неэффективностью. Я ищу несколько вещей (в порядке важности):

  1. Сделать код как можно быстрее (правда, за счет еще чего-нибудь)
  2. Сделать код более читабельным
  3. Инкапсуляция все функции в miller_rabin (функция)
  4. Сделать длину кода короче

Я тоже ищу какие-нибудь идеи на мое обращение из кода GMP. Я знаю, что есть способ перераспределить память, но я не уверен, как это сделать. Любые мысли будут оценены по достоинству!

Вот код:

#include <iostream>
#include <gmp.h>
#include <gmpxx.h>

using namespace std;


mpz_class exp_one(mpz_class a, mpz_class b, mpz_class c){
    mpz_class r;
    mpz_powm(r.get_mpz_t(), a.get_mpz_t(), b.get_mpz_t(), c.get_mpz_t());
    return r;
}

mpz_class exp_two(mpz_class a, mpz_class b){
    mpz_class r, c;
    c = 2;
    mpz_powm(r.get_mpz_t(), a.get_mpz_t(), c.get_mpz_t(), b.get_mpz_t());
    return r;
}

mpz_class mr_check_one(mpz_class n){
    if(n % 2 != 0){
        return 0;
    }

    n = n - 1;
    while(n % 2 == 0){
        n = n / 2;
    }
    return n;
}

mpz_class mr_check_two(mpz_class m, mpz_class n){
    mpz_class b, u, j, d;
    u = n - 1;
    j = 0;
    d = 2;

    b = exp_one(d, m, n);

    if(b == u or b == 1){
        return 0;
    }

    while(b != u and j < 7){
        b = exp_two(b, n);
        j++;
    }

    if(b == u){
        return 0;
    } else {
        return 1;
    }
}

mpz_class miller_rabin(mpz_class n){
    mpz_class r;
    r = mr_check_one(n);
    r = mr_check_two(r, n);
    return r;
}


int main(){
    mpz_class n, r;
    n = 2305843009213693951;  //some prime
    r = miller_rabin(n);

    if(r == 0){
        cout << "This number is PRIME!" << endl;
    } else {
        cout << "This number is NOT prime." << endl;
    }
}


477
3
задан 8 марта 2018 в 04:03 Источник Поделиться
Комментарии