精华内容
下载资源
问答
  • 题目:/*@author tilltheendwjx@blog http://blog.csdn.net/wjh200821或者http://www.cnblogs.com/tilltheendwjx/*/#includeusing namespace std;int indexofmax1(int value){int tmp=1;int count=0;...

    题目:

    1337091100_5264.jpg

    /*

    @author tilltheendwjx

    @blog http://blog.csdn.net/wjh200821或者http://www.cnblogs.com/tilltheendwjx/

    */

    #include

    using namespace std;

    int indexofmax1(int value)

    {

    int tmp=1;

    int count=0;

    for(int i=0;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

    {

    if((value&tmp))

    {

    if(i==0)

    {

    cout<

    }else if(i==1)

    {

    cout<

    }else

    {

    cout<

    }

    flag=1;

    if(i

    cout<

    }

    tmp=tmp*2;

    }

    if(flag==0)

    cout<

    }

    int powofvalue(int value)

    {

    return 1<

    }

    int divide(int m,int b,int &remainvalue)

    {

    int mindex=indexofmax1(m);

    int vindex=indexofmax1(b);

    if(mindex

    {

    remainvalue=m;

    return 0;

    }

    int c=mindex-vindex;

    int tmp=b;

    tmp=tmp<

    m=m^tmp;

    return powofvalue(c)|divide(m,b,remainvalue);

    }

    int Tx(int ax,int q,int bx)

    {

    //cout<

    //cout<

    int tmp=1;

    int value=0;

    for(int i=0;i

    {

    if((q&tmp))

    {

    value=value^((bx<

    }

    tmp=tmp*2;

    }

    //cout<

    //cout<

    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<

    cout<

    a1=b1;a2=b2;a3=b3;

    b1=t1;b2=t2;b3=t3;

    x=b2;y=b3;

    polynomialtostring(q);

    cout<

    }

    }

    int main(void)

    {

    int m=283,b=83,x=0,y=0;

    cout<

    cout<

    int reault=extent_gcd(m,b,x,y);

    cout<

    cout<

    system("pause");

    return 0;

    }

    运行结果如下图

    1337091374_4348.png

    展开全文
  • AES:有限域的多项式乘法逆元求解

    千次阅读 2017-11-07 17:23:00
    求解算法,扩展欧几里得算法 /* @author tilltheendwjx @blog http://blog.csdn.net/wjh200821或者http://www.cnblogs.com/tilltheendwjx/ */ #include using namespace std; int indexofmax1(int value) { in

    题目:


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

    /*
    @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;
    }
    

    运行结果如下图


    展开全文
  • 求解算法,扩展欧几里得算法 /* @author tilltheendwjx @blog http://blog.csdn.net/wjh200821或者http://www.cnblogs.com/tilltheendwjx/ */ #include<iostream> using namespace std; int index...

    题目:


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

    /*
    @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

    展开全文
  • 关于有限域多项式因式分解,和不错,对有限域多项式概括很完整
  • 本文为理解FEC(Reed-Solomon)编码补充,简述用到的有限域计算知识有限域定义这里域(Field)定义是有如下特性集合:定义了加法和乘法集合内元素经过加法和乘法计算,结果仍然在集合内计算符合交换率、...

    92557b58dc7edae590e6f66b47165ef2.png

    本文为理解FEC(Reed-Solomon)编码的补充,简述用到的有限域计算的知识

    有限域定义

    这里的域(Field)的定义是有如下特性的集合

    • 定义了加法和乘法
    • 集合内的元素经过加法和乘法计算,结果仍然在集合内
    • 计算符合交换率、结合率、分配率
    • 加法和乘法有单位元素(所有的集合内的值都有对应的负数,所有集合内非零值都有倒数)

    举个例子,我们常见的实数集是域,但整数值不是域(因为除了1,其它数的倒数都不是整数)。

    具有有限个元素的域就是有限域(下文以GF表示,GF是Galois Field的缩写,这个名字纪念发明者Evariste Galois)。

    这可能有点反常识,既然可以一直加、一直乘,怎么会只有有限个元素呢?一个关键的操作就是‘取模’。也就是在域的定义基础上,作如下修改:

    • 定义模p加法模p乘法(加或乘的结果超过p时,模p取余数。p为素数)
    • 集合内的元素经过加法和乘法计算,结果仍然在集合内
    • 计算符合交换率、结合率、分配率
    • 加法和乘法有单位元素(所有的集合内的值都有对应的负数,所有集合内非零值都有倒数)

    举例子,GF(3)是定义了模3加法和乘法的有限域,有三个元素:0、1、2。两个计算示例:

    equation?tex=1%2B2%3D3%5Cleft%28mod+3%5Cright%29%3D0

    equation?tex=2%5Ctimes2%3D4%5Cleft%28mod+3%5Cright%29%3D1

    (另外注意以上两个计算分别说明了1、2互为‘负数’,2是2的倒数)

    下面是GF(3)的加法和乘法的所有组合。

    6c3a05ccf2391c477b25ed604fd50d6a.png

    那么,如果p不是素数会怎样呢?以下面‘GF(4)’的例子来说明:

    15fbde3b9d1347fd230e1ecaf59dad1e.png

    GF(4)并不是有限域的存在,因为它并不能满足所有有限域的定义要求,因为元素2没有倒数。

    不过,如果我们修改一下元素,将'GF(4)'改为

    equation?tex=GF%282%5E2%29 ,4个元素的集合也可以成为有限域:

    507d876267f01a77cea061bea57f162e.png

    ('GF(4)'的

    equation?tex=GF%282%5E2%29 的区别是
    equation?tex=GF%282%5E2%29 在计算时每个位都是模2运算,即'异或')

    在通信编码中使用的就是

    equation?tex=GF%282%5Em%29 这种形式的有限域,因为二进制、加法/异或这些十分适合通信硬件实现。

    多项式

    下面引入多项式的概念以更好的理解

    equation?tex=GF%282%5Em%29 中的乘法。

    二进制数可以表示成多项式的方式:

    equation?tex=11000001%5CRightarrow+x%5E7%2Bx%5E6%2B1%3D1x%5E7%2B1x%5E6%2B0x%5E5%2B0x%5E4%2B0x%5E3%2B0x%5E2%2B0x%5E1%2B1x%5E0

    这个多项式表示中内含了高有效位(MSB)低有限位(LSB)的概念,代表的是不同位的位置权重的区别。(上面多项式中代入

    equation?tex=x%3D2 就可以得到11000001代表的数值193)

    有限域中加法和乘法的多项式表示可以用如下例子来说明:

    34a0a6373b0e0c75176aa20c01352628.png

    再回头看一下前面的

    equation?tex=GF%282%5E2%29 的例子,例子中的00、01、10、11等值用多项式表示就是:

    equation?tex=%5Cbegin%7Baligned%7D++00%5CRightarrow+0x%2B0%5C%5C+01%5CRightarrow+0x%2B1%5C%5C+10%5CRightarrow+1x%2B0%5C%5C+11%5CRightarrow+1x%2B1+%5Cend%7Baligned%7D

    使用取模多项式为

    equation?tex=x%5E2%2Bx%2B1

    76fa62b089ea31b38e4ff4ed1689b438.png

    以上图中红色框的数值计算为例,计算过程是:

    equation?tex=%5Cbegin%7Baligned%7D+%26x%2B1%5C%5C+%5Ctimes%26x+%5C%5C+%3D%26x%5E2%2Bx%5Cpmod%7Bx%5E2%2Bx%2B1%7D%5C%5C+%3D%260x%2B1%5C%5C+%3D%2601+%5Cend%7Baligned%7D

    详细看一下多项式取模的运算:

    equation?tex=%5Cbegin%7Baligned%7D+%26x%5E2%2Bx%2B0+%26%26%26%26110%5C%5C+%2B%26x%5E2%2Bx%2B1%26%5CRightarrow%26%26%2B%26111+%5C%5C+%3D%260x%5E2%2B0x%2B1+%26%26%26%3D%26001+%5Cend%7Baligned%7D

    从硬件角度来看就是两个3位二进制数按位异或操作,消掉最高位。

    指数表示方式

    equation?tex=%5Calpha%3Dx 为有限域的基本元素,则有限域中所有的其它元素都可以用
    equation?tex=%5Calpha%5En 的方式来获得,见下面的例子
    equation?tex=GF%282%5E4%29

    a31416b7a21da29deb98f14f30b0e0f0.png
    展开全文
  • 最近在复习现代密码理论中的AES,AES中的字节变换的核心操作就是求GF(28)GF(2^8)GF(28)上的多项式逆元,这个问题困扰了我一段时间,今天终于得到解决,其实计算方式和数论中求两个数的Bezout算法是一样的,这里感谢...
  • 有限域的本原多项式

    千次阅读 2020-01-02 09:07:27
    查询有限域本原多项式: http://wims.unice.fr/wims/cn_tool~algebra~primpoly.cn.html
  • 如要转贴,必须注明原文网址http://www.cnblogs.com/Colin-Cai/p/9489225.html作者:窗户QQ/微信:6679072E-mail:6679072@qq.com接着上两章内容,我们还是得继续寻找有限域的构造方法。上章证明矩阵环是个单环,...
  • 多项式的同余取定 为 上非常值多项式(即 )Def1. 多项式 与 模 同余式指 ,此时用同余式 来表示。Thm1. 模 同余关系是 上等价关系,且如果 , ,则: Prf. 显然。记 为多项式 所在同余等价类,由多项式的带余...
  • 设有非线性方程: 其中, 为 上连续函数且设 (不妨设方程在 内仅有一个实根),求上述方程实根二分法过程,就是将含根区间[a,b]逐步分半,检查函数值符号变化,以便确定含根充分小区间。二分法叙述如下:记 第...
  • 这次我们单独来谈谈整系数多项式环 首先来看一下 上多项式与整数环 上的多项式的不同:因子关系令 ,我们有 中, 与 互为因子,但在 中, 是 的因子,但 不是 的因子。带余除法令 ,则 。这是 中的带余除法,其中 。...
  • 今年网络安全一个小作业,简单用C++实现了下 有些粗糙 先放这儿吧 ^_^算法描述 考完试再附上ExEuclid简单实现/* * 文件名称:myecu.cpp * 摘 要:Extend Euclid Algorithm * 作者:ld * 完成日期:25th June,...
  • 常见数域: 复数C;实数R;有理数域Q。(注意:自然数集N及整数集Z都不是数域。)说明:1)若数集P中任意两个数作某一运算结果仍在P中,则说数集P对这个运算是封闭。2)数域等价定义:如果一个包含0,1在内...
  • 写在前面:本人小白,刚刚开始学习拓扑优化和C++相关知识,如果写有错误请大家不吝赐教,也欢迎私信讨论~这篇文章是学习王勖成有限单元法》后梳理知识,所有截图来自该书,也可以理解为抄书hhh有限元分析...
  • 第四章 多项式有限域 陆以勤 学习本章目的:对Xn-1进行因式分解(n=qm-1,q为素数) X15-1=(x+1)(x 4 + x 3+1)(x4+x3+x2 +x +1)(x2 +x +1)(x4+x +1) Xn-1? 循环:只有最高位和最低位 一、剩余类环 环,子环、扩环 ...
  • 共回答了14个问题采纳率:...“有限域GF(2)上的多项式”,说明:(1)多项式的系数只能是0或1,(不能是2,3,.也不能是-1,-2.)(2)同类项合并时的运算按照上面的GF(2)上的加法运算例子:F(X)*G(X):(1)先做普通多项是乘法:...
  • 域的性质:群和域在数学上的概念就不解释,可以参考维基百科。当然也可以参考《密码编码学与网络安全》这书的有限域一章。形象地说,域有这样一个性质:在加法和乘法上具有封闭性。也就是说对域中的元素进行加法或...
  • 上篇文章里已经说了那份分圆多项式的讲义,今天有机会就稍微翻译一下。引入:定义 此为次数为n分圆多项式。几个例子: 可以看出,分圆多项式 为 上次数为 不可约多项式。这也就是说, 是 上 (表示最大公因数...
  • ![图片说明]... 如图计算九阶分圆多项式求和在mod p结果(不知道自己理解有没有问题) 九阶分圆多项式是x^6+x^3+1,有没有大佬告诉我该怎么做。。。
  • 匿名用户1级2010-11-15 回答这个软件功能很强大,数学建模时候可以用到它1、特殊变量与常数ans 计算结果变量名computer 确定运行计算机eps 浮点相对精度Inf 无穷大I 虚数单位inputname 输入参数名NaN 非数...
  • 现在我们可以讨论因式分解理论中最重要也是最困难部分——不可约多项式. 同样, 我们需要对比整数情形素数理论.素数算术基本定理告诉我们, 素数在正整数研究中地位是非常重要. 对素数探索贯穿了数学...
  • 内容提要:1 有限域的初步讨论; 2 有限域的存在唯一性; 3 有限域的Frobenius自同构; 本文主要参考文献.本文的前置内容为:格罗卜:域论和Galois理论(1): 基本内容格罗卜:域论和Galois理论(2): 代数闭包, 分裂域与正规...
  • 大家好!这一份复习提纲是提供给厦门大学18级本科生作为高等代数月考使用。和之前类似,我们只会点出一些...1. 一元多项式和运算其实多项式这个概念你在初中就见过(整式),它就是一个表达式 。在这个式子中, 这些...
  • 本文主要翻译自这篇文章译者注★ 本文承接上文所讨论的椭圆曲线,并将曲线的定义域从实数域缩小到了有限域,引出离散对数问题 ”★ 首先介绍了有限域的定义,并给出了一种基于模运算的有限域 ”★ 然后对离散域上的...
  • 文章目录一、前言二、数学基础1、GF(2⁸)有限域的多项式2、不可约多项式3、多项式模运算3、乘法逆元三、算法步骤1、扩展欧几里得算法2、多项式除法3、多项式乘法四、代码实现1、多项式除法2、多项式乘法3、...
  • 若大家发现那些翻译不够准确还望指出,不胜感激。首先放上原文链接:http://andrea.corbellini.name/2015/05/23/elliptic-curve-cryptography-finite-fields-and-discrete-logarithms/​andrea.corbellini.name ...
  • 顾名思义,有限域就是含有有限个元素的域。既然是含有有限个元素的域,那么关键点就在于有限和域两个概念。首先我们看一下域的定义(来自维基百科): 在抽象代数中,域(Field)是一种可以进行加,减,乘,除(除了除以...
  • 有限域上低重不可约多项式生成及判断算法,程序
  • 抑或是给定一个椭圆曲线的方程,去计算该曲线在某个有限域的有点个数(这里就涉及了Division Polynomial)。多项式除法可以在一定情形下转变为多项式乘法。从而如何快速计算多项式乘法是个很...
  • ——————————————— 完更撒花~(10/10)——————————————[参考文献] Michael Artin: Algebra (2nd Edition)1 域的例子[域扩张] 给定一对域 , 称为 的一个域扩张,或扩域。记号 表示 是 的域...

空空如也

空空如也

1 2 3 4 5 ... 10
收藏数 192
精华内容 76
关键字:

有限域的多项式