分类目录归档:研究

走别人没有走过的路。

一个合并bib文件的小工具

因为当写过两篇文章之后,偶尔来个汇报之类的,就需要将之前文章的参考文献汇集在一起处理。然而这些文献本身可能是大量重复的,如何将多个bib文件中的重复文献去掉,仅保留不重复的部分,并最终输出到一个合并之后的bib文件中,是写这个小工具的一个背景。

原来的bib文件已经有自己的citation key,而且自己也习惯于这样的生成方式。虽然有一些文献管理软件也有此功能,但有如下弊端:

1)基于title来去重,而不是citation key去重;
2)bib文件中的其他非文献信息会被清除掉;
3)导出后原来的citation key无法保持原样

考虑到以上因素,所以就写了这个小工具:https://github.com/tpu01yzx/BibtexParser

这个工具的用法很简单,主要是几个参数:

1) -O –output 设置合并后输出到的文件名,缺省是标准输出设备。
2) –onlyregular 是否只输出Reguler(类似article,book,misc之类表示具体的文献记录,而非辅助信息如comment, string)的记录,默认为否。
3) –outputplain 是否输出非@开头的记录,这类块大部分是注释或者用于格式控制的,默认为否。

当然了,仅有这个工具,用起来还是有点麻烦,所以最后送上一个Bat批处理文件,把这个批处理文件,bib合并小工具,以及要合并的所有bib文件放在同一个目录。执行这个批处理文件,就不用每次都去找命令行,对于大部分习惯了Windows的用户来说应该是件好事。

@echo off
SetLocal EnableDelayedExpansion

set allbib=_all.bib
set exec=bib_combiner.exe

echo @comment{this file is generated by BibtexParser.exe} > %allbib%
set list=
for  %%i in (*.bib) do ( 
	if not "%%i" == "%allbib%" (		
		set list=!list! "%%i"
	)
)
%exec% "%allbib%" %list% -O "%allbib%" -R
%exec% --help
set exec=
set allbib=
set list=
pause

给伸手党准备好了,Windows下的打包(包含上面提到的一个工具和一个批处理文件:bib_combiner.exe和一个run.bat),点击这里下载

一种二元序列的线性复杂度算法的实现

#include <stdio.h>
#include <memory.h>

#define MAXL (1000)

typedef unsigned char uchar;

void prints(const uchar *s, const int n)
{
    int i;
    for(i=0;i<n;i++) {printf("%u",s[i]);}
    printf("\n");
}

//implement the Berlekamp–Massey algorithm for binary sequences.
//Please see https://en.wikipedia.org/wiki/Berlekamp%E2%80%93Massey_algorithm#The_algorithm_for_the_binary_field
int bm(const uchar*s, const int n)
{
    int i,j,lc,m,d;
    uchar b[MAXL];
    uchar c[MAXL];
    uchar t[MAXL];
    
    b[0]=1;c[0]=1;
    for(i=1;i<n;i++){b[i]=0;c[i]=0;};
  
    lc=0;m=-1;
    
    for(i=0;i<n;i++) {
        d=s[i];
        for(j=1;j<=lc;j++) { d ^=s[i-j] & c[j]; }
        if(d!=0){
            memcpy(t,c,n);
            for(j=0;j<n-i+m;j++) { c[i-m+j]^=b[j]; }
            
            if(2*lc<=i) {
                lc=i+1-lc;
                m=i;
                memcpy(b,t,n);
            }
        }
    }
  
    return lc;
}

int main()
{
    int n;
    int lc;
    char c;
    int i,j;
    uchar s[MAXL];
    uchar ans_s[MAXL];
    int ans_lc;
    int ans_j;
    
    //if you would like to read the sequence from file, please uncomment the follows line.
    //freopen ("s1.txt","r",stdin);
    //skip the first line
    while((c=getchar())!='\n');
    //read the sequence
    n=0;
    while(n<MAXL){
        c=getchar();
        //the line should be ended with '\n' or ']'.
        if(c=='\n' || c==']') break;
        
        //only '0' and '1' are captured.
        if(c>='0' && c<='1') {
            //convert '0' and '1' to 0 and 1.
            s[n++]=c-'0';
        }
    }
    prints(s,n);
    printf("There are %d bits.\n", n);
    
    lc = bm(s,n);
    printf("The original LC is %d\n", lc);
    
    //make sure that current ans_lc is big enough.
    ans_lc=n; ans_j=-1;
    for(i=0;i<n;i++) {
        s[i] ^=1;
        
        lc=bm(s,n);
        if(lc<ans_lc) {
            //save the current optimal answer;
            ans_lc=lc; ans_j=i;
            memcpy(ans_s,s,n);
            printf("Update ans with lc=%d when  s[%u]:%u->%u.\n", 
            ans_lc, ans_j, s[ans_j]^1, ans_s[ans_j]);
        }
        
        s[i] ^=1;
    }
    
    printf("The minimal 1+lc is %d when s[%u]:%u->%u.\n", 
        1+ans_lc, ans_j, s[ans_j], ans_s[ans_j]);
    prints(ans_s,n);
    
    
    return 0;
}

这是基于C语言实现的wiki上二元序列的线性复杂度,如果需要对应的极小多项式可以从最后的c变量数组中直接转换过来,这并不是什么有难度的事情。

同伴矩阵的方幂

最近在研究一个矩阵的方幂,这个矩阵如下

    \[A=\left( \begin{array}{ccc}  0 & 0 & -a_0 \\  1 & 0 & -a_1 \\  0 & 1 & -a_2 \\ \end{array} \right).\]

事实上这个矩阵和下面这个多项式存在一一对应的关系,

    \[f(x)=x^3+a_2x^2+a_1x+a_0.\]

使用Mathematica计算A^k, 代码如下:
<< FiniteFields` Assuming[Element[p, Primes] && Element[n, Integers] && n > 0,
F = GF[p, n];
A = {{0, 0, -a[0]}, {1, 0, -a[1]}, {0, 1, -a[2]}};
Print[MatrixForm[
Simplify[MatrixPower[A, k],
Element[a[0], F] && Element[a[1], F] && Element[a[2], F] &&
Element[k, Integers] && k > 1]]];
];

计算结果为:

    \[\left( \begin{array}{ccc}  \frac{x_2 x_3 x_1^k}{\left(x_1-x_2\right) \left(x_1-x_3\right)}+\left(\frac{x_3 x_2^k}{x_2^2-a_1+2 x_1 x_3}+\frac{x_3^k x_2}{\left(x_1-x_3\right) \left(x_2-x_3\right)}\right) x_1 & a_0 \left(\frac{x_2^k}{-x_2^2+a_1-2 x_1 x_3}+\frac{\frac{x_3^k}{x_3-x_2}-\frac{x_1^k}{x_1-x_2}}{x_1-x_3}\right) & a_0 \left(\frac{\left(a_2+x_2+x_3\right) x_1^k}{\left(x_1-x_2\right) \left(x_1-x_3\right)}+\frac{x_3^{k+1}}{\left(x_1-x_3\right) \left(x_3-x_2\right)}+\frac{x_2^{k+1}}{-x_2^2+a_1-2 x_1 x_3}\right) \\  \frac{x_1 x_2 x_3 \left(-\frac{\left(a_2+x_1\right) x_1^k}{\left(x_1-x_2\right) \left(x_1-x_3\right)}+\frac{x_3^k \left(a_2+x_3\right)}{\left(x_1-x_3\right) \left(x_3-x_2\right)}+\frac{x_2^k \left(a_2+x_2\right)}{-x_2^2+a_1-2 x_1 x_3}\right)}{a_0} & \frac{\left(a_2+x_1\right) x_1^{k+1}}{\left(x_1-x_2\right) \left(x_1-x_3\right)}+\frac{x_3^{k+1} \left(a_2+x_3\right)}{\left(x_3-x_1\right) \left(x_3-x_2\right)}+\frac{x_2^{k+1} \left(a_2+x_2\right)}{x_2^2-a_1+2 x_1 x_3} & -\frac{\left(a_2+x_1\right) \left(a_2+x_2+x_3\right) x_1^{k+1}}{\left(x_1-x_2\right) \left(x_1-x_3\right)}+\frac{x_3^{k+2} \left(a_2+x_3\right)}{\left(x_1-x_3\right) \left(x_2-x_3\right)}+\frac{x_2^{k+2} \left(a_2+x_2\right)}{x_2^2-a_1+2 x_1 x_3} \\  \frac{-x_1 x_3 \left(x_1^k+x_2^k-2 x_3^k\right) x_2^2+x_1 x_3^2 \left(x_1^k-2 x_2^k+x_3^k\right) x_2+a_0 a_2 \left(x_2^k-x_3^k\right)}{a_0 \left(x_1-x_2\right) \left(x_1-x_3\right) \left(x_2-x_3\right)} & \frac{x_1^{k+1}}{\left(x_1-x_2\right) \left(x_1-x_3\right)}+\frac{x_3^{k+1}}{\left(x_3-x_1\right) \left(x_3-x_2\right)}+\frac{x_2^{k+1}}{x_2^2-a_1+2 x_1 x_3} & -\frac{\left(a_2+x_2+x_3\right) x_1^{k+1}}{\left(x_1-x_2\right) \left(x_1-x_3\right)}+\frac{x_3^{k+2}}{\left(x_1-x_3\right) \left(x_2-x_3\right)}+\frac{x_2^{k+2}}{x_2^2-a_1+2 x_1 x_3} \\ \end{array} \right).\]

显然在化简方面,Mathematica并没有充分利用a_0,a_1,a_2是有限域上的元素的特点,所以这个表达式还是挺复杂的,需要自己进一步做化简. 最终的目标是为了计算det(A^k-I).

突然灵机一动, 改动了一下Mathematica的代码如下:
<< FiniteFields` Assuming[Element[p, Primes] && Element[n, Integers] && n > 0,
F = GF[p, n];
A = {{0, 0, -a[0]}, {1, 0, -a[1]}, {0, 1, -a[2]}};
Print[MatrixForm[
Simplify[Det[MatrixPower[A, k] - IdentityMatrix[3]],
Element[a[0], F] && Element[a[1], F] && Element[a[2], F] &&
Element[k, Integers] && k > 1]]];
];

结果为:

    \[det(A^k-I)=(-1+x_1^k) (-1+x_2^k) (-1+x_3^k),\]

其中x_1,x_2,x_3是方程f(x)的三个根.

中国密码学年会PPT(2013/2015/2016)

2013年密码学年会PPT
本地下载:chinacrypt2013ppt.zip

2014年密码学年会PPT(待续)
本地下载:无

2015年密码学年会PPT
本地下载:chinacrypt2015ppt.zip

2016年密码学年会PPT
http://cacr2016.cacrnet.org.cn/ShowNews.aspx?ID=87
本地下载:chinacrypt2016ppt.zip

本文仅为转载,如有侵权,请在文章后面给我留言,谢谢。

On Some Papers (5)

On Generalized Zero-Difference Balanced Functions
对ZDB函数进行了推广得到G-ZDB函数,同样可以用于构造CCC码和DSS结构。基本思路还是做cyclotomic cosets的划分,不过这种划分是不平衡的,大概是这样

    \[1,1,\ldots,1,m,m,\ldots,m\]

的样子,然后就数一下有多少个1和多少个m。

On Some Papers (4)

已经几天没写了,始终有些过意不去,既然现在记得就再写点吧。

A note on the behaviour of the NFS in the medium prime case: Smoothness of Norms
作者就NFS算法的理论算法复杂度是实际算法运行时间进行了试验,并对其中多项式的选择给出了一些观察的结果,这可以指导我们实际操作的时候如何设定参数的大小。其中在筛阶段的光滑概率似乎还没有很好的计算方法,多项式的的预选择就是先估计这个光滑概率。
继续阅读

On Some Papers (3)

天气预报说今天有台风,然后是狂风暴雨的,但是该看的还是要看,继续吧。

On the Arithmetic Complexity of Strassen-Like Matrix Multiplications
矩阵乘法的时间复杂度啊,考虑的是没有稳定问题的情况,比如密码学中有限域元素构成的矩阵。n=2^k时,是这个5n^2:81 + 0:5n^2:59 + 2n^2:32;n=8*2^k时,是这个3:55n^2:81 + 0:148n^2:59 + 1:02n^2:32。跟原来的复杂度比起来,感觉改进不大,具体做法没细看,扫了一眼,不适合自己看,记住这个复杂度就好。
继续阅读

On Some Papers (2)

中断了几天,接着看文章,希望能坚持下去,无论在哪里。

Square Root Algorithm in F(q) for q ≡ 2^s+ 1 (mod 2^(s+1))
平方根算法,之前在课本上看的那个应该是素域上的平方根算法吧,还真没仔细看是否适用于这种扩域上的情况。作者提出的这类平方根算法都很简单,复杂度也很低,只需要一个指数运算。s是满足如下条件的最大整数:2^s|q-1,因为算法有2^(s-1)个,所以暂时也只能解决s很小的情况,比如作者解决了s=2,3,4的情况,也就是q ≡ 5 (mod 8),q ≡ 9 (mod 16),q ≡ 17 (mod 32)这三种情况的平方根算法。
继续阅读