模2n 加和模2加混合运算的异或分支数

研究了扩散结构为二元域上非线性变换的异或分支数.给出了扩散结构为二元域上非线性变换的异或分支数的定义及其与分组密码抗差分攻击和线性分析能力的关系,证明了以模2n加和模2加的混合运算为扩散结构的异或分支数等于将模2n加换成模2加且将各变元系数模2后所得的二元域上线性变换的异或分支数,从而简化了此类非线性扩散结构异或分支数的计算问题.     

Toeplitz矩阵相乘的一种新快速算法

将Toeplitz矩阵分解为一个循环矩阵和一个下三角Toeplitz矩阵之和,以及一般卷积向循环卷积的转化,借助快速Fouier变换(FFT),导出了一种计算两个n阶Toeplitz矩阵乘积的新快速算法,其算法复杂性为2n2 63/4n log2n-15n-34次实乘运算,4n2 63/2n log2n-18n 23次实加运算,与已有的优化算法相比,在实乘次数有所降低的同时,实加次数降低了近1/3,是目前复杂性最小的一种算法.     

MIX函数的模加差分概率分析

S函数由Nicky Mouha提出,是只需输入字的第i个bit和第i个运算状态S[i]即可计算出输出字的第i个bit的一类函数,利用其可以有效研究模加、异或运算的性质。为研究Skein算法的核心部件MIX函数的模加差分性质,将MIX函数转化为S函数的形式,给出了一种精确计算MIX函数模加差分概率的方法,通过理论分析,说明相对于通过求各运算部件概率之积以获得整体函数的概率的一般方法,利用S函数的方法得到的结果更为精确。     

基于RSA的概率公钥密码的研究

针对目前概率密码普遍存在加解密效率低、数据膨胀率高等问题,文章以两种基于RSA的概率加密算法为例,在不降低它们安全性的基础上分别对它们进行了改进。改进后的第一种算法针对一种基于RSA的随机数加密算法进行讨论,将大量的模幂运算替换为模乘运算,提高了加解密效率。改进后的第二种算法针对一种基于RSA的多密钥双模数算法进行讨论,将大量模幂运算改为异或运算,同时保留了概率加密安全性高的特点。     

异或加整体逼近模2n加差值函数的和概率分布

为求解密码算法中异或加整体逼近模2n加运算所得差值函数之和的概率分布问题,利用概率分布的定义,通过直接统计满足条件变量的计数,给出2个差值函数之和的概率分布,并进一步提出2个差值函数之和的概率平方和计算公式,将其计算复杂度由O(24n)降为O(1).     

BLAKE抗线性化差分分析安全性研究

基于模加、循环及异或运算的系统(ARX系统)通常被认为是设计密码算法的重要基础。在SHA-3第二轮候选算法中,BLAKE等杂凑函数基于该系统设计。通过对BLAKE-32中的模加运算进行线性化,分析了初始差分在各轮运算过程中的扩散情况,得出了初始状态字存在差分时各轮运算中差分的扩散特征。在此基拙上,研究了多次加法运算的线性化逼近概率,并分析了线性化逼近方法对分析算法的有效性。研究表明,线性化情况下,部分初始差分字在BLAKE-32中的扩散效果并不理想,可以将BLAKE算法局部线性化后进行差分攻击。     

Salsa20的差分故障分析

Salsa20是eSTREAM计划最终获胜算法之一,其主要特征是利用模加、异或和循环移位三种运算的混合提供算法所需扩散性和混淆性.目前对该算法的分析主要集中在统计分析和差分分析两方面.本文研究Salsa20/256的差分故障分析,在基于随机字的故障诱导模型下,通过诱导96个错误,将以近似1的概率获得186比特的密钥信息...     

ARX函数的两轮迭代线性化条件研究

含模加运算、循环移位运算和异或加运算的密码算法称为ARX型算法,3种运算的混合使用可以达到更好的扩散和混乱效果。为此,给出二元ARX函数的定义,研究其两轮迭代同时线性化的条件,利用统计分析方法得到线性化条件成立的元素个数的计算公式。分析两轮独立条件下得到的线性化条件成立的概率,发现利用统计分析的方法能够更准确地刻画线性化条件成立概率的影响因素,并且增加一个左右块变换不会对两轮ARX函数的线性化条件产生影响。     

SAFER++的差分分析

SAFER++是欧洲信息工程的参选算法,并且是进入第2轮的7个候选算法之一。算法的设计者称5轮SAFER++算法可以抵抗差分分析。本文利用异或差分与模减差分串连得到3.75轮的高概率特征,对4轮SAFER++进行选择明文攻击。攻击过程的计算复杂度约为298.2次加密运算,数据复杂度是296,可以恢复出12字节的密钥。而且如果存在4轮特征(设计者称已经通过搜索的方法找到),可以利用本文提出的方法得到更高轮数的特征,用于攻击5轮以上的SAFER++算法。     

Toeplitz矩阵之逆矩阵的新分解式及快速算法

本文利用线性方程组是否有解给出了Toeplitz矩阵可逆的条件,表明Toeplitz矩阵的逆矩阵可以表示为循环矩阵与下三角Toeplitz矩阵的乘积之和,给出了其逆矩阵列的递推公式,得到了求Toeplitz矩阵之逆矩阵的快速算法,计算复杂性为O(n2),一般n阶矩阵求逆的计算复杂性为O(n3).     

Parallel computation of determinants of matrices with multivariate polynomial entries

In this paper we present an extension to the work of Björck et al. for computing the determinants of matrices with univariate or bivariate polynomials as entries to multivariate case. The algorithm supports parallel computation and has been implemented on a multi-core cluster computer system. We show how to use our approach to calculate two unsolved problems, which arise from computational geometry optimization and electric power engineering, and analyze the time complexity as well as bits complexity.     

Matrix strategies for computing the least trimmed squares estimation of the general linear and SUR models

An algorithm for computing the exact least trimmed squares (LTS) estimator of the standard regression model has recently been proposed. The LTS algorithm is adapted to the general linear and seemingly unrelated regressions models with possible singular dispersion matrices. It searches through a regression tree to find the optimal estimates and has combinatorial complexity. The model is formulated as a generalized linear least squares problem. Efficient matrix techniques are employed to update the generalized residual sum of squares of a subset model. Specifically, the new algorithm utilizes previous computations to update a generalized QR decomposition by a single row. The sparse structure of the model is exploited. Theoretical measures of computational complexity are provided. Experimental results confirm the ability of the new algorithms to identify outlying observations.     

基于BS预判的H.264去块滤波优化算法

首先介绍了H.264去块滤波的滤波强度计算原理,并基于滤波强度的计算量为去块滤波过程中最大的部分,提出了一种滤波强度提前预判的优化算法。通过仿真实验证明该算法在对解码图像质量没有任何影响的情况下较标准算法降低了75％左右的滤波运算时间,有效地缓解了H.264解码运算复杂度,提高整体解码时间,以有助于实时应用的实现。     

Computation of system balancing transformations and other applications of simultaneous diagonalization algorithms

An algorithm is presented in this paper for computing state-space balancing transformations directly from a state-space realization. The algorithm requires no "squaring up" or unnecessary matrix products. Various algorithmic aspects are discussed in detail. A key feature of the algorithm is the determination of a contragredient transformation through computing the singular value decomposition of a certain product of matrices without explicitly forming the product. Other contragredient transformation applications are also described. It is further shown that a similar approach may be taken, involving the generalized singular value decomposition, to the classical simultaneous diagonalization problem. These SVD-based simultaneous diagonalization algorithms provide a computational alternative to existing methods for solving certain classes of symmetric positive definite generalized eigenvalue problems.     

Symbolic algorithm for inverting cyclic pentadiagonal matrices recursively — Derivation and implementation

In this paper, by using parallel computing along with recursion, we describe a reliable symbolic computational algorithm for inverting cyclic pentadiagonal matrices. The algorithm is implemented in MAPLE. Two other symbolic algorithms are developed and the computational costs for all algorithms are given. An example is presented for the sake of illustration.     

Automatic generation of fast algorithms for matrix–vector multiplication

This paper describes the methods for finding fast algorithms for computing matrix–vector products including the procedures based on the block-structured matrices. The proposed methods involve an analysis of the structural properties of matrices. The presented approaches are based on the well-known optimization techniques: the simulated annealing and the hill-climbing algorithm along with its several extensions. The main idea of the proposed methods consists in finding a decomposition of the original matrix into a sparse matrix and a matrix corresponding to an appropriate block-structured pattern. The main criterion for optimizing is a reduction of the computational cost. The methods presented in this paper can be successfully implemented in many digital signal processing tasks.     

Physis语言框架在WENO高阶数值格式异构计算中的应用

WENO(weighted essentially non-oscillatory)是计算流体力学中广泛采用的一种高阶数值格式。由于算法本身和异构计算编程的复杂性,需要开展异构计算代码自动生成的研究,以加速更多的应用。本文基于Physis这一领域编程语言框架,针对三维五阶WENO计算的天文应用,实现了其异构代码的自动生成。在超级计算机"元"上的测试结果表明,自动生成的异构计算代码具有良好的可扩展性,计算性能达到手工优化异构代码的72%,可为相关流体计算的异构代码生成提供借鉴。     

移动音频带宽扩展算法计算复杂度优化

移动通信设备由于计算资源有限,对计算复杂度较为敏感。我国自主研发提出的移动音频编解码算法标准AVS P10中的带宽扩展算法有利于提高移动音频编解码质量,但其计算复杂度较高,不利于该编解码算法在移动环境中应用。通过分析该带宽扩展算法的流程,发现其计算复杂度较高的主要原因是时频变换次数过多,为此从算法和代码两个方面对该算法进行优化:算法方面通过减少快速傅里叶变换(FFT)次数来降低算法计算复杂度;而代码方面则通过空间换时间等方法来减少算法消耗时间。测试结果表明,在不降低整体音频编解码主观质量的情况下,带宽扩展模块在编码端和解码端运行时间比例分别降低了4.5和14.3个百分点,算法计算复杂度显著降低,这有利于进一步在移动音频领域推广应用该编解码算法。     

Parallel block tridiagonalization of real symmetric matrices

Two parallel block tridiagonalization algorithms and implementations for dense real symmetric matrices are presented. Block tridiagonalization is a critical pre-processing step for the block tridiagonal divide-and-conquer algorithm for computing eigensystems and is useful for many algorithms desiring the efficiencies of block structure in matrices. For an “effectively” sparse matrix, which frequently results from applications with strong locality properties, a heuristic parallel algorithm is used to transform it into a block tridiagonal matrix such that the eigenvalue errors remain bounded by some prescribed accuracy tolerance. For a dense matrix without any usable structure, orthogonal transformations are used to reduce it to block tridiagonal form using mostly level 3 BLAS operations. Numerical experiments show that block tridiagonal structure obtained from this algorithm directly affects the computational complexity of the parallel block tridiagonal divide-and-conquer eigensolver. Reduction to block tridiagonal form provides significantly lower execution times, as well as memory traffic and communication cost, over the traditional reduction to tridiagonal form for eigensystem computations.     

Hadoop Based Parallel Binary Bat Algorithm for Network Intrusion Detection

In Internet applications, due to the growth of big data with more features, intrusion detection has become a difficult process in terms of computational complexity, storage efficiency and getting optimized solutions of classification through existing sequential computing environment. Using a parallel computing model and a nature inspired feature selection technique, a Hadoop Based Parallel Binary Bat Algorithm method is proposed for efficient feature selection and classification in order to obtain optimized detection rate. The MapReduce programming model of Hadoop improves computational complexity, the Parallel Binary Bat algorithm optimizes the prominent features selection and parallel Naïve Bayes provide cost-effective classification. The experimental results show that the proposed methodologies perform competently better than sequential computing approaches on massive data and the computational complexity is significantly reduced for feature selection as well as classification in big data applications.