The (Non)Enumerability of the Determinant and the Rank

We investigate the complexity of enumerative approximation of two fundamental problems in linear algebra, computing the rank and the determinant of a matrix. We show that both are as hard to approximate (in the enumerative sense) as to compute exactly. In particular, if there exists an enumerator that, given a matrix over some finite field, outputs a list of constantly many numbers, one of which is guaranteed to be the rank of the matrix, then it can be determined in AC ⁰ (with oracle access to the enumerator) which of these numbers is the rank. Thus, for example, if the enumerator is an FL function, then the problem of computing the rank is in FL. For the determinant function we establish the following two results: (1) If the determinant is poly-enumerable in logspace, then it can be computed exactly in FL. (2) For any prime p , if computing the determinant modulo p is (p-1) -enumerable in FL (i.e., if one could eliminate a single possible value for the determinant modulo p ), then the determinant modulo p can be computed in FL. Because there is a close connection between these two functions and logspace counting classes, we hope that our results can give a better understanding of the power of counting in logspace, and the relationships among the complexity classes sandwiched between NL and uniform TC ¹ .     

Global robust stabilization of nonlinear systems subject to input constraints

Our main purpose in this paper is to further address the global stabilization problem for affine systems by means of bounded feedback control functions, taking into account a large class of control value sets: p, r ‐weighted balls ??^m _r (p), with 1<p?∞, defined via p, r ‐weighted gauge functions. Observe that p=∞ is allowed, so that m‐dimensional r ‐hyperboxes ??^m _r (∞)?[?r₁^?,r₁⁺]×???×[?r_m^?,r_m⁺], r_j^±>0 are also considered. Working along the line of Artstein–Sontag's approach, we construct an explicit formula for a one‐parameterized family of continuous feedback controls taking values in ?? _r ^m(p) that globally asymptotically stabilize an affine system, provided an appropriate control Lyapunov function is known. The designed family of controls is suboptimal with respect to the robust stability margin for uncertain systems. The problem of achieving disturbance attenuation for persistent disturbances is also considered. Copyright © 2002 John Wiley & Sons, Ltd.     

The Complexity of Boolean Functions in Different Characteristics

Every Boolean function on n variables can be expressed as a unique multivariate polynomial modulo p for every prime p. In this work, we study how the degree of a function in one characteristic affects its complexity in other characteristics. We establish the following general principle: functions with low degree modulo p must have high complexity in every other characteristic q. More precisely, we show the following results about Boolean functions f : {0, 1}ⁿ → {0, 1} which depend on all n variables, and distinct primes p, q:

Exponentiation modulo a polynomial for data security

This paper describes some properties of exponentiation modulo a polynomial and suggests its use for encryption in a mode that can be cryptanalyzed in approximatelyO(pd ³) time, whered is the size of the message frame andp is the prime modulo which the rankwise computations are carried out. While for sufficiently largepd (～10⁵) this appears to provide a one-way function which can be used in a public-key cryptosystem, we show that since encryption/ decryption effort is defined inO(d ² logpd log logp) time, a practical application of the proposed algorithm would be either in a secret key or in a tamper-proof, hardwired secret polynomial system.     

Toward a theory of Pollard's rho method

Pollard's “rho” method for integer factorization iterates a simple polynomial map and produces a nontrivial divisor of n when two such iterates agree modulo this divisor. Experience and heuristic arguments suggest that a prime divisor p should be detected in steps, but this has never been proved. Indeed, nothing seems to be have been rigorously proved about the probability of success that would improve the obvious lower bound of 1/p. This paper shows that for fixed k, this probability is at least (₂^k)/p + O(p^−3/2) as p → ∞. This leads to an Ω(log²p)/p estimate of the success probability.     

Time Bounded Frequency Computations

(1) We obtain two new results concerning the inclusion problem of polynomial time frequency classes with equal numbers of errors. 1. (m, m+d) P(m+1, m+d+1) Pform<2^d. 2. (m, m+d) P=(m+1, m+d+1) Pformc(d) wherec(d) is large enough. This disproves a conjecture of Kinber. (2) We give a transparent proof of a generalization of Kinber's result that there exist arbitrarily complex problems admitting a polynomial time frequency computation. Several corollaries provide more insight into the structure of the hierarchy of polynomial time frequency classes. (3) The relationships between polynomial time frequency classes and selectivity classes are studied.     

Solvability of systems of polynomial congruences modulo a large prime

We consider the following polynomial congruences problem: given a prime p, and a set of polynomials of total degree at most d, solve the system for solution(s) in . We give a randomized algorithm for the decision version of this problem. For a fixed number of variables, the sequential version of the algorithm has expected time complexity polynomial in d, m and log p; the parallel version has expected time complexity polylogarithmic in d, m and p, using a number of processors, polynomial in d, m and log p. The only point which prevents the algorithm from being deterministic is the lack of a deterministic polynomial time algorithm for factoring univariate polynomials over . Received: April 9, 1997.     

Optimization and pole placement for a single input controllable system

Given the system [xdot]=Ax+bu and the cost function J=dt, relations are to be determined among the open-loop characteristic polynomial, the closed-loop characteristic polynomial and the matrices A and Q. Those relations take a simple form if the system is in the standard controllable form. In this case the optimal control law can be found easily without solving the matrix Riccati equation while the minimum value of the cost function, if it is required, can be determined by solving a matrix equation of the form C ^T. X+XC= ?D     

Rijndael分组密码的研究与分析

该文对Rijndael分组密码进行了较为深入的研究,将字节代替变换中的有限域GF(28)上模乘求逆运算和仿射变换归并成了一个8×8的S盒,将圈中以字节为单位进行的行移位、列混合、密钥加三种运算归并成了一个广义仿射变换,归并结果表明Rijndael密码实质上是一个形如仿射变换的非线性迭代算法。基于分析给出了Rijndael密码算法的精简描述,并指出了算法预计算快速实现的有效方法。     

Optimal input sets for steering quantized systems

Limited capacity of communication channels has strongly pushed the analysis of control systems subject to a quantized input set. Quantized control system of type x ⁺ = x + u, where the u takes values in a set of 2m + 1 integer numbers, symmetric with respect to 0 arise in some fundamental situations, e.g., flat, nilpotent, and linear systems with quantized feedback. In this paper we consider this special type of systems and analyze the reachable set after K steps. We find explicit expressions, for each K and for each m, of m input values such that the reachable set after K steps is as large as possible.     

Application of coding theory to the construction of the Singer difference sets†

In this paper we give a new and simple construction for the cyclic [(q ^m ? 1)/(q ? 1), q ^m?1, q ^m?2(q? 1)]—difference sets (q = p ^γ is a prime power) using the methods of coding theory. The construction is such that, in the case q = 2, the 2-ranks of both the incidence matrix and its complementary matrix are easily determined.     

Multidimensional adapted Runge–Kutta–Nyström methods for oscillatory systems

For the general multidimensional perturbed oscillators y^″+Ky=f(y,y^′) with K∈Rd×d, the order conditions for the ARKN methods are presented by X. Wu et al. [Order conditions for ARKN methods solving oscillatory systems, Comput. Phys. Comm. 180 (2009) 2250–2257]. These methods integrate exactly the multidimensional unperturbed oscillators and are highly efficient when the perturbing function is small. In this paper, we are concerned with the analysis of the concrete multidimensional ARKN methods based on the order conditions for the multidimensional ARKN methods. We extent the matrix K to a general case, in which K is not required to be symmetric. Numerical experiments demonstrate that the novel multidimensional ARKN methods presented in this paper are more efficient compared with some well-know RKN methods in the scientific literature.     

面向低精度环境的安全高速批图像加密

目的 随着存在大量低性能电子设备的物联网系统迅速发展和普及,人们对低精度计算环境下安全高效的图像加密技术有着越来越迫切的需求。现有以混沌系统为代表的图像加密方法不仅加密速度普遍较低,而且在低精度计算环境下存在严重的安全缺陷,难以满足实际需求。针对上述问题,本文提出了一种基于素数模乘线性同余产生器的批图像加密方法,用以提升低精度环境下图像加密的效率和安全性。方法 该方法的核心是构建一个能在低精度环境下有效运行的素数模乘线性同余产生器;将图像集均分为3组,并借助异或运算生成3幅组合图像;接着引入图像集的哈希值更新上述第3组图像;将更新后的组合图像作为上述产生器的输入,进而生成一个加密序列矩阵;基于加密序列矩阵对明文图像进行置乱和扩散,并使用异或运算生成密文图像;使用具有较高安全性的改进版2D-SCL(a new 2D hypher chaotic map based on the sine map, the chebysher map and a linear function)加密方法对加密序列矩阵进行加密。结果 仿真结果表明,本文提出的批图像加密方法在计算精度为2^-8     

LINEAR TRANSFORMATIONS IN GALOIS FIELDS AND THEIR APPLICATION TO CRYPTOGRAPHY

A plaintext message is first subdivided into groups of n letters and then mapped on the Galois Field GF(pⁿ) where p is the alphabet size. The elements of the Galois Field so obtained are considered as the components of a vector V and submitted to a linear transformation within the field. In the event that n=1 the algorithm reduces to the famous Hill cipher.     

Computing Frobenius maps and factoring polynomials

A new probabilistic algorithm for factoring univariate polynomials over finite fields is presented. To factor a polynomial of degreen overF _q , the number of arithmetic operations inF _q isO((n ²+nlogq). (logn)² loglogn). The main technical innovation is a new way to compute Frobenius and trace maps in the ring of polynomials modulo the polynomial to be factored.     

A complex-number Fourier technique for lower bounds on the Mod-m degree

We say an integer polynomial p, on Boolean inputs, weakly m-represents a Boolean function f if p is nonconstant and is zero (mod m), whenever f is zero. In this paper we prove that if a polynomial weakly m-represents the Mod _q function on n inputs, where q and m are relatively prime and m is otherwise arbitrary, then the degree of the polynomial is . This generalizes previous results of Barrington, Beigel and Rudich, and Tsai, which held only for constant or slowly growing m. In addition, the proof technique given here is quite different. We use a method (adapted from Barrington and Straubing) in which the inputs are represented as complex q-th roots of unity. In this representation it is possible to compute the Fourier transform using some elementary properties of the algebraic integers. As a corollary of the main theorem and the proof of Toda's theorem, if q, p are distinct primes, any depth-three circuit that computes the Mod _q function, and consists of an exact threshold gate at the output, Mod _p gates at the next level, and AND gates of polylog fan-in at the inputs, must be of exponential size. We also consider the question of how well circuits consisting of one exact gate over ACC(p)-type circuits (where p is an odd prime) can approximate parity. It is shown that such circuits must have exponential size in order to agree with parity for more than 1/2 + o(1) of the inputs. Received: February 21, 1996.     

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

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

Generic and Explicit Realization of Smallp-groups

We prove the existence of a generic polynomial for the Heisenberg groupH_p³ over a field of characteristic not p, where p is an odd prime.     

Hashing via finite field

In order to produce full length probe sequences, the table size m for many existing open addressing hash functions, for example, the widely used double hashing, must be prime, i.e., m = p where p is prime. In this paper, we propose a new and efficient open addressing technique, called hashing via finite field, to construct a new class of hash functions with table size m = pⁿ, where p is prime and n ? 1. It is clear that it includes prime m as a special case when n = 1. We show that the new class of hash functions constructed via finite field produces full length probe sequences on all table elements. Also, some theoretic analysis is provided along with concrete examples.