蒙哥马利约减和barret约减代码

科技前沿 • 2025-01-04 23:28 • 阅读 52

大家好，我是讯享网，很高兴认识大家。

 #include<iostream> using namespace std; struct Barret { 
    int p; int k; int u; int bk_1, bka1; Barret(int p) { 
    this->p = p; k = (int)log2(p) + 1; u = (1<<(2*k))/p; bk_1 = 1 << (k - 1); bka1 = 1 << (k + 1); } int calc(int z) { 
    int q_ = (z / bk_1 * u / bka1); int r = (z & (bka1 - 1)) - (q_ * p & (bka1 - 1)); if (r < 0)r = r + bka1; while (r >= p)r = r - p; return r; } }; struct Mong { 
    int r; int n; int n_; int r_; int rn; int k; int beta; Mong(int n,int n_,int r,int r_,int k,int rn) { 
    this->n = n; this->n_ = n_; this->r = r; this->r_=r_; this->k = k; beta = 1 << k; this->rn = rn; if (n * n_ - r * r_ !=-1)cout << "error" << endl; } //优化实现(0,2*n) //input a :k*r; //output o = k % n; int Mon(int a) { 
    int m = ((a & (beta- 1)) * rn) & (beta - 1); if (m > (beta / 2))m -= beta; int t1 = (m * n) >> k; return ((a >> k) - t1); } //普通实现(t,n) int Mon2(int t) { 
    int m = ((t & (beta - 1))*n_) &(beta-1); int tt = (t + m * n) >> k; if (tt >= n) tt -= n; return tt; } int MonPro(int a_, int b_) { 
    int t = (a_ * b_); int m = (t * n_) & (beta - 1); int u = (t + m * n) >> k; if (u >= n)return u - n; else return u; } //意义不大，用到了取模 int monMul(int a, int b) { 
    int a_ = (a * r)%n; int b_ = (b * r)%n; int x_ = MonPro(a_, b_); int x = MonPro(x_, 1); return x; } int MonExp(int a, int e) { 
    int a_ = a * r %n; int x_ = r % n; while (e) { 
    if (e & 1)x_ = MonPro(a_, x_); e >>= 1; a_ = MonPro(a_, a_); } int x = MonPro(x_, 1); return x; } }; int main(int argc, char** argv) { 
    auto t=Barret(255); auto a = Mong(7, 9, 16, 4, 4,7); cout << a.monMul(3, 4) << endl; cout << a.Mon(13 * 16) << endl; cout << a.Mon2(13 * 16) << endl; cout << a.Mon(5)*a.Mon(9)*16*16%7<<endl; cout << a.MonExp(3, 4) << endl; }

讯享网

蒙哥马利约减和barret约减代码

相关推荐