精华内容
下载资源
问答
  • 多项式乘法逆元 - NTT
    2021-03-03 11:14:06

    9f56e120a65272dfde141be294613d8b.png

    递归求解即可

    #include

    using namespace std;

    #define int long long

    namespace NTT {

    #define pw(n) (1<

    const int N=4000005; // 4 times!

    const int mod=998244353,g=3;

    int n,m,bit,bitnum,a[N+5],b[N+5],rev[N+5];

    void getrev(int l){

    for(int i=0;i

    rev[i]=(rev[i>>1]>>1)|((i&1)<

    }

    }

    int fastpow(int a,int b){

    int ans=1;

    for(;b;b>>=1,a=1LL*a*a%mod){

    if(b&1)ans=1LL*ans*a%mod;

    }

    return ans;

    }

    void NTT(int *s,int op){

    for(int i=0;i

    for(int i=1;i

    int w=fastpow(g,(mod-1)/(i<<1));

    for(int p=i<<1,j=0;j

    int wk=1;

    for(int k=j;k

    int x=s[k],y=1LL*s[k+i]*wk%mod;

    s[k]=(x+y)%mod;

    s[k+i]=(x-y+mod)%mod;

    }

    }

    }

    if(op==-1){

    reverse(s+1,s+bit);

    int inv=fastpow(bit,mod-2);

    for(int i=0;i

    }

    }

    void solve(vector A,vector B,vector &C) {

    n=A.size()-1;

    m=B.size()-1;

    for(int i=0;i<=n;i++) a[i]=A[i];

    for(int i=0;i<=m;i++) b[i]=B[i];

    m+=n;

    bitnum=0;

    for(bit=1;bit<=m;bit<<=1)bitnum++;

    getrev(bitnum);

    NTT(a,1);

    NTT(b,1);

    for(int i=0;i

    NTT(a,-1);

    C.clear();

    for(int i=0;i<=m;i++) C.push_back(a[i]);

    for(int i=0;i<=min(m*2,N-1);i++) a[i]=b[i]=0;

    }

    }

    const int N=4000005; // 4 times!

    const int mod=998244353,g=3;

    struct poly {

    vector a;

    void cut(int n) {

    while(a.size()>n) a.pop_back();

    }

    poly operator *(int b) {

    poly c=*this;

    for(int i=0;i

    return c;

    }

    poly operator *(const poly &b) {

    poly c;

    NTT::solve(a,b.a,c.a);

    return c;

    }

    poly operator +(poly b) {

    int len=max(a.size(),b.a.size());

    a.resize(len);

    b.a.resize(len);

    poly c;

    for(int i=0;i

    return c;

    }

    poly operator -(poly b) {

    int len=max(a.size(),b.a.size());

    a.resize(len);

    b.a.resize(len);

    poly c;

    for(int i=0;i

    return c;

    }

    };

    void print(poly x) {

    for(int i=0;i

    cout<

    }

    int n,a[N];

    int qpow(int p,int q) {

    int r = 1;

    for(; q; p*=p, p%=mod, q>>=1) if(q&1) r*=p, r%=mod;

    return r;

    }

    int inv(int p) {

    return qpow(p, mod-2);

    }

    poly solve(poly A, int n) {

    A.cut(n);

    poly B;

    if(n==1) {

    B.a.push_back(inv(A.a[0]));

    }

    else {

    poly Bi = solve(A,(n-1)/2+1);

    B = Bi*2 - A*Bi*Bi;

    B.cut(n);

    }

    return B;

    }

    signed main() {

    ios::sync_with_stdio(false);

    cin>>n;

    for(int i=0;i>a[i];

    poly A;

    for(int i=0;i

    poly B = solve(A,n);

    print(B);

    }

    更多相关内容
  • 接收多项式r1,r2(r1>=r2),以及多项式长度nums 返回其每一步的商组成的矩阵Q,以及gcd(r1,r2) Poly_Division(r1,r2,nums): 接收多项式r1,r2(r1>=r2),以及多项式长度nums 返回商,及其余数 Poly_Multi(a,b,nums)...

    一、解析

    Poly_GCD(r1,r2,nums):
    接收多项式r1,r2(r1>=r2),以及多项式长度nums
    返回其每一步的商组成的矩阵Q,以及gcd(r1,r2)

    Poly_Division(r1,r2,nums):
    接收多项式r1,r2(r1>=r2),以及多项式长度nums
    返回商,及其余数

    Poly_Multi(a,b,nums):
    接收多项式a,b,以及多项式长度nums
    返回乘积

    Poly_Multi_Eye(a,b,nums):
    接收多项式a,仅有一个系数为1的多项式b,以及多项式长度nums
    返回乘积

    二、思路

    函数Poly_GCD(r1,r2,nums)返回其商的矩阵Q,以及最大公因式gcd
    X初始迭代值为gcd,Y初始迭代值为任意多项式
    设X初始迭代值为gcd,Y初始迭代值为0
    迭代方程如下:
    Next_X=Y
    Next_Y=X-Q_i*Y
    单击查看迭代方程证明
    最终输出X,Y迭代值

    三、演示图

    请添加图片描述

    四、代码

    1、Main

    nums=9;
    r1=[0 1 0 0 0 0 0 1 1];
    r2=[1 0 0 0 1 1 0 1 1];
    %高次在前,低次在后
    [Q,gcd]=Poly_GCD(r2,r1,nums);
    Size=size(Q);
    X=gcd;
    Y=zeros(1,nums);
    for i=1:Size(1)
        temp1=Y;
        temp2=xor(X,Poly_Multi(Q(i,:),Y,nums));
        X=temp1;
        Y=temp2;
    end
    disp(X);
    disp(Y);
    

    2、Poly_GCD

    function [Q,r2] = Poly_GCD(r1,r2,nums)
    Q=[];
    [q,r3]=Poly_Division(r1,r2,nums);
    Q=[q;Q];
    while(~(max(r3)==0))
        r1=r2;
        r2=r3;
        [q,r3]=Poly_Division(r1,r2,nums);
        Q=[q;Q];
    end
    end
    

    3、Poly_Division

    function [Q,r3] = Poly_Division(r1,r2,nums)
    Q=zeros(1,nums);
    temp1=find(r1==1);
    temp2=find(r2==1);
    temp3=temp2(1)-temp1(1);
    while(temp3>=0)
        q1=zeros(1,nums);
        q1(1,nums-temp3)=1;
        Q=Q+q1;
        Poly_Multi(r2,q1,nums);
        r3=xor(r1,Poly_Multi(r2,q1,nums));
        if(max(r3)==0)
            break;
        end
        r1=r3;
        temp1=find(r1==1);
        temp3=temp2(1)-temp1(1);
    end
    end
    

    4、Poly_Multi

    function [ret] = Poly_Multi(a,b,nums)
    temp1=find(b==1);
    Size=size(temp1);
    ret=zeros(1,nums);
    for i=1:Size(2)
        temp2=zeros(1,nums);
        temp2(1,temp1(i))=1;
        ret=xor(ret,Poly_Multi_Eye(a,temp2,nums));
    end
    end
    

    5、Poly_Multi_Eye

    function [ret] = Poly_Multi_Eye(a,b,nums)
    temp1=find(b==1);
    for i=1:nums-temp1(1)
        a(1,1:nums-1)=a(1,2:nums);
        a(1,nums)=0;
    end
    ret=a;
    end
    `
    
    展开全文
  • AES:有限域的多项式乘法逆元求解

    千次阅读 2017-11-07 17:23:00
    题目: 求解算法, 扩展的欧几里得算法 ...cout多项式(";...cout)的乘法逆元是(";polynomialtostring(x);cout)"; system("pause"); return 0; } 运行结果如下图

    题目:


    求解算法,扩展的欧几里得算法

    /*
    @author tilltheendwjx
    @blog http://blog.csdn.net/wjh200821或者http://www.cnblogs.com/tilltheendwjx/ 
    */ 
    #include<iostream>
    using namespace std;
    int indexofmax1(int value)
    {
        int tmp=1;
        int count=0;
        for(int i=0;i<sizeof(int)*8;++i)
        {
              if((value&tmp))
                 count=i;
              tmp=tmp*2;
        }
        return count;
    }
    void polynomialtostring(int value)
    {
        int tmp=1;
        int flag=0;
        int c=indexofmax1(value);
        for(int i=0;i<sizeof(int)*8;++i)
        {
              if((value&tmp))
              {
                 if(i==0)
                 {
                   cout<<"1";
                 }else if(i==1)
                 {
                   cout<<"x";
                 }else
                 {
                   cout<<"x^"<<i;
                 }
                 flag=1;
                 if(i<c)
                   cout<<"+";
              }   
              tmp=tmp*2;
        }
        if(flag==0)
          cout<<"0";
    }
    int powofvalue(int value)
    {
        return 1<<(value);
    }
    int divide(int m,int b,int &remainvalue)
    {
        int mindex=indexofmax1(m);
        int vindex=indexofmax1(b);
        if(mindex<vindex)
        {
            remainvalue=m;
            return 0;
        }
        int c=mindex-vindex;
        int tmp=b;
        tmp=tmp<<c;
        m=m^tmp;
        return powofvalue(c)|divide(m,b,remainvalue);
    }
    int Tx(int ax,int q,int bx)
    {
        //cout<<endl;
        //cout<<ax<<"\t"<<bx<<"\t";
        int tmp=1;
        int value=0;
        for(int i=0;i<sizeof(int)*8;++i)
        {
              if((q&tmp))
              {
                 value=value^((bx<<i));   
              }   
              tmp=tmp*2;
        }
        //cout<<ax<<"\t"<<value<<"\t";
        //cout<<endl;
        return ax^(value);
    }
    int extent_gcd(int m,int b,int &x,int &y)
    {
       int a1=1,a2=0,a3=m;
       int b1=0,b2=1,b3=b;
       int remainvalue=0;
       while(1)
       {
               polynomialtostring(a1);
               cout<<"    ";
               polynomialtostring(a2);
               cout<<"    ";
               polynomialtostring(a3);
               cout<<"    ";
               polynomialtostring(b1);
               cout<<"    ";
               polynomialtostring(b2);
               cout<<"    ";
               polynomialtostring(b3);
               cout<<"    ";
              if(b3==0)
                  return a3;
              if(b3==1)
                   return b3;
              int q=divide(a3,b3,remainvalue);
              int t1=Tx(a1,q,b1);
              int t2=Tx(a2,q,b2);
              int t3=remainvalue;
              cout<<t1<<endl;
              cout<<t2<<endl;
              a1=b1;a2=b2;a3=b3;
              b1=t1;b2=t2;b3=t3;
              x=b2;y=b3;
              polynomialtostring(q);
              cout<<endl;
       } 
    }
    int main(void)
    {
    int m=283,b=83,x=0,y=0;
    cout<<"中间结果如下:"<<endl; 
    cout<<"a1   a2    a3    b1    b2    b3    q"<<endl;
    int reault=extent_gcd(m,b,x,y);
    cout<<endl;
    cout<<"多项式(";polynomialtostring(b);cout<<")mod(";polynomialtostring(m);cout<<")的乘法逆元是(";polynomialtostring(x);cout<<")"<<endl;
    system("pause"); 
    return 0;
    }
    

    运行结果如下图


    展开全文
  • matlab的M函数文件,附带了函数的使用说明了
  • 很好的东西,很实用的东西,你懂的。基于Gf的多项式乘法逆元,在很多时候都能够用到。
  • [原]有限域的多项式乘法逆元求解

    千次阅读 2012-05-15 22:13:00
    cout)的乘法逆元是(";polynomialtostring(x);cout)"; system("pause"); return 0; } 运行结果如下图 作者:wjh200821 发表于2012-5-15 22:13:00 原文链接 阅读:2 评论:0 查看评论 转载...

    题目:


    求解算法,扩展的欧几里得算法

    /*
    @author tilltheendwjx
    @blog http://blog.csdn.net/wjh200821或者http://www.cnblogs.com/tilltheendwjx/ 
    */ 
    #include<iostream>
    using namespace std;
    int indexofmax1(int value)
    {
        int tmp=1;
        int count=0;
        for(int i=0;i<sizeof(int)*8;++i)
        {
              if((value&tmp))
                 count=i;
              tmp=tmp*2;
        }
        return count;
    }
    void polynomialtostring(int value)
    {
        int tmp=1;
        int flag=0;
        int c=indexofmax1(value);
        for(int i=0;i<sizeof(int)*8;++i)
        {
              if((value&tmp))
              {
                 if(i==0)
                 {
                   cout<<"1";
                 }else if(i==1)
                 {
                   cout<<"x";
                 }else
                 {
                   cout<<"x^"<<i;
                 }
                 flag=1;
                 if(i<c)
                   cout<<"+";
              }   
              tmp=tmp*2;
        }
        if(flag==0)
          cout<<"0";
    }
    int powofvalue(int value)
    {
        return 1<<(value);
    }
    int divide(int m,int b,int &remainvalue)
    {
        int mindex=indexofmax1(m);
        int vindex=indexofmax1(b);
        if(mindex<vindex)
        {
            remainvalue=m;
            return 0;
        }
        int c=mindex-vindex;
        int tmp=b;
        tmp=tmp<<c;
        m=m^tmp;
        return powofvalue(c)|divide(m,b,remainvalue);
    }
    int Tx(int ax,int q,int bx)
    {
        //cout<<endl;
        //cout<<ax<<"\t"<<bx<<"\t";
        int tmp=1;
        int value=0;
        for(int i=0;i<sizeof(int)*8;++i)
        {
              if((q&tmp))
              {
                 value=value^((bx<<i));   
              }   
              tmp=tmp*2;
        }
        //cout<<ax<<"\t"<<value<<"\t";
        //cout<<endl;
        return ax^(value);
    }
    int extent_gcd(int m,int b,int &x,int &y)
    {
       int a1=1,a2=0,a3=m;
       int b1=0,b2=1,b3=b;
       int remainvalue=0;
       while(1)
       {
               polynomialtostring(a1);
               cout<<"    ";
               polynomialtostring(a2);
               cout<<"    ";
               polynomialtostring(a3);
               cout<<"    ";
               polynomialtostring(b1);
               cout<<"    ";
               polynomialtostring(b2);
               cout<<"    ";
               polynomialtostring(b3);
               cout<<"    ";
              if(b3==0)
                  return a3;
              if(b3==1)
                   return b3;
              int q=divide(a3,b3,remainvalue);
              int t1=Tx(a1,q,b1);
              int t2=Tx(a2,q,b2);
              int t3=remainvalue;
              cout<<t1<<endl;
              cout<<t2<<endl;
              a1=b1;a2=b2;a3=b3;
              b1=t1;b2=t2;b3=t3;
              x=b2;y=b3;
              polynomialtostring(q);
              cout<<endl;
       } 
    }
    int main(void)
    {
    int m=283,b=83,x=0,y=0;
    cout<<"中间结果如下:"<<endl; 
    cout<<"a1   a2    a3    b1    b2    b3    q"<<endl;
    int reault=extent_gcd(m,b,x,y);
    cout<<endl;
    cout<<"多项式(";polynomialtostring(b);cout<<")mod(";polynomialtostring(m);cout<<")的乘法逆元是(";polynomialtostring(x);cout<<")"<<endl;
    system("pause"); 
    return 0;
    }
    

    运行结果如下图




    作者:wjh200821 发表于2012-5-15 22:13:00 原文链接
    阅读:2 评论:0 查看评论

    转载于:https://www.cnblogs.com/tilltheendwjx/archive/2012/05/15/2502332.html

    展开全文
  • 最近在复习现代密码理论中的AES,AES中的字节变换的核心操作就是求GF(28)GF(2^8)GF(28)上的多项式逆元,这个问题困扰了我一段时间,今天终于得到解决,其实计算方式和数论中求两个数的Bezout算法是一样的,这里感谢...
  • 题目: /* @author tilltheendwjx @blog http://blog.csdn.net/wjh200821或者http://www.cnblogs.com/tilltheendwjx/ */ #...cout)的乘法逆元是(";polynomialtostring(x);cout)"("pause"); return 0; } 运行结果如下图
  • 多项式乘法

    2021-03-03 11:14:36
    给定一个多项式 \(F(x)\) ,请求出一个多项式 \(G(x)\), 满足 \(F(x) * G(x) \...考虑倍增多项式只有一项时就是乘法逆元假设我们现在得到了\[G^{'}(x) \equiv F(x) (mod\ x^{\frac{n}{2}})\]我们需要求\[G(x)\equiv...
  • 文章目录一、前言二、数学基础1、GF(2⁸)有限域内的多项式2、不可约多项式3、多项式模运算3、乘法逆元三、算法步骤1、扩展欧几里得算法2、多项式除法3、多项式乘法四、代码实现1、多项式除法2、多项式乘法3、...
  • 概述 多项式求逆元是一个非常重要的知识点,许多多项式操作都需要用到该算法,包括多项式...快速数论变换(NTT),求一个数$x$在模$p$意义下的乘法逆元多项式的逆元 给定一个多项式$A(x)$,其次数为$deg_A...
  • 多项式逆元

    千次阅读 2017-11-07 17:21:25
    Contents [hide] 1 概述2 基本概念3 多项式的...多项式逆元多项式除法和多项式取模的必要过程,在竞赛中,有时候多项式逆元的应用比多项式的除法还要多,用快速傅里叶变换以及倍增算法可以做到在 O(nlogn
  • 1.关于扩展欧几里得算法的理解 首先要先学会欧几里得算法(辗转相除法): int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } /* c = a % b; a = b; b = c; if b !... bx1 + (a % b)y1 ...
  • 《密码学》乘法逆元

    2019-10-27 15:12:52
    Euclid算法 乘法逆元 如果 ax+by=1 那么 a×y%x=1 即 a-1%x=y a×x%y=1 即 a-1%y=x
  • 有限域中求乘法逆元

    千次阅读 2020-09-27 17:09:04
    注: 1、模2运算 总结一句话:不管是加法还是减法,相同为0,相异为1; 例题:求57的多项式乘法逆元 转载:https://blog.csdn.net/fat_cai_niao/article/details/90439924
  • #在有限域GF(2^n)下求多项式乘法 Python代码实现 一、了解运算规则 二、例题展示 三、直接上代码(代码有详细备注,不做一一解释) def yxydxscf(a,b,c): # 不可约多项式系数模二运算 c = str(c)[1:] # 不够8...
  • 简单讲解用辗转相除法计算乘法逆元,用于密码学加密,附C语言实现算法(对正整数运算)
  • 乘法逆元的三种求解方法

    千次阅读 2020-09-02 15:15:24
    目录乘法逆元小结逆元的定义求解逆元的方法1. 快速幂测试代码2. 乘法逆元小结 乘法逆元,一般用于求(a / b)(modp)的值(p 通常为质数),是解决模意义下分数数值的必要手段。 关于求余,有以下三种规则: 加法:...
  • (乘法)逆元证明·求解·模板

    千次阅读 2018-03-11 09:43:13
    复习之路:关于逆元,我们首先知道一个叫做“完全剩余系”的东西,记为Zn,即mod n剩下的数;还有一个叫做 “缩系”的东西...我们要求乘法逆元有两种方式,首先介绍三个定理:1、之前讲到的乘法逆元,即ax = 1 (mod ...
  • 逆元——乘法逆元的应用 1、问题引入: (1)对于m=(a/b)(mod p)问题,由于除法不能用同余定理,我们需要将除法转换成乘法 ( a / b ) % p =a * inv ( b , p ) %p =( a%p * inv ( b , p )%p ) %p (其中,inv ( b , p...
  • 有限域 GF(28282^8)上的元素满足加法交换群、线性空间,所以,是和整数有限域上的运算等价的,所以可以直接重载扩展欧几里得来计算多项式逆元 /* &amp;gt; Problem:main &amp;gt; Author: ...
  • C语言实现GF(2^8)下多项式乘法
  • 多项式算法1:多项式乘法

    千次阅读 2019-06-02 11:27:26
    多项式简介 对于数域F\mathbb FF,若有∀i∈{1,2,3,⋯&ThinSpace;,n}\forall i\in\{1,2,3,\cdots,n \}∀i∈{1,2,3,⋯,n},则 f(x)=a0+a1x+a2x2+⋯+anx=∑i=1naixif(x)=a_0+a_1x+a_2x^2+\cdots+a_nx=\sum_{i=1}^...
  • 整理的算法模板合集: ACM模板 目录多项式求逆一、分治FFT二、倍增法及其...P4238 【模板】多项式乘法逆 直接按照上述的思路实现一下模板即可。注意要中间 h(x)h(x)h(x) 要取的是模 x⌈n⌉2x^{\frac{\lceil n \rceil}

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,236
精华内容 494
关键字:

多项式乘法逆元

友情链接: struts2.rar