Synthesis of cryptographic interleaved sequences by means of linear cellular automata

This work shows that a class of pseudorandom binary sequences, the so-called interleaved sequences, can be generated by means of linear multiplicative polynomial cellular automata. In fact, these linear automata generate all the solutions of a type of linear difference equations with binary coefficients. Interleaved sequences are just particular solutions of such equations. In this way, popular nonlinear sequence generators with cryptographic application can be linearized in terms of simple cellular automata.     

On the Use of Cellular Automata in Symmetric Cryptography

In this work, pseudorandom sequence generators based on finite fields have been analyzed from the point of view of their cryptographic application. In fact, a class of nonlinear sequence generators has been modelled in terms of linear cellular automata. The algorithm that converts the given generator into a linear model based on automata is very simple and is based on the concatenation of a basic structure. Once the generator has been linearized, a cryptanalytic attack that exploits the weaknesses of such a model has been developed. Linear cellular structures easily model sequence generators with application in stream cipher cryptography.Work supported by Ministerio de Educación y Ciencia (Spain), Projects SEG2004-02418 and SEG2004-04352-C04-03.     

Uniform random number generation

In typical stochastic simulations, randomness is produced by generating a sequence of independent uniform variates (usually real-valued between 0 and 1, or integer-valued in some interval) and transforming them in an appropriate way. In this paper, we examine practical ways of generating (deterministic approximations to) such uniform variates on a computer. We compare them in terms of ease of implementation, efficiency, theoretical support, and statistical robustness. We look in particular at several classes of generators, such as linear congruential, multiple recursive, digital multistep, Tausworthe, lagged-Fibonacci, generalized feedback shift register, matrix, linear congruential over fields of formal series, and combined generators, and show how all of them can be analyzed in terms of their lattice structure. We also mention other classes of generators, like non-linear generators, discuss other kinds of theoretical and empirical statistical tests, and give a bibliographic survey of recent papers on the subject.     

Predicting masked linear pseudorandom number generators over finite fields

We study the security of the linear generator over a finite field. It is shown that the seed of a linear generator can be deduced from partial information of a short sequence of consecutive outputs of such generators.     

具有一般终端时刻和非一致线性增长生成元的倒向随机微分方程的$L^p$解

In this paper, we establish the existence of the minimal L~p(p 1) solution of backward stochastic differential equations(BSDEs) where the time horizon may be finite or infinite and the generators have a non-uniformly linear growth with respect to t. The main idea is to construct a sequence of solutions {(Y~n, Z~n)} which is a Cauchy sequence in S~p× M~p space, and finally we prove {(Y~n, Z~n)} converges to the L~p(p 1) solution of BSDEs.     

On lattice profile of the elliptic curve linear congruential generators

Lattice tests are quality measures for assessing the intrinsic structure of pseudorandom number generators. Recently a new lattice test has been introduced by Niederreiter and Winterhof. In this paper, we present a general inequality that is satisfied by any periodic sequence. Then, we analyze the behavior of the linear congruential generators on elliptic curves (EC-LCG) under this new lattice test and prove that the EC-LCG passes it up to very high dimensions. We also use a result of Brandstätter and Winterhof on the linear complexity profile related to the correlation measure of order $k$ to present lower bounds on the linear complexity profile of some binary sequences derived from the EC-LCG.     

Testing cut generators for mixed-integer linear programming

In this paper, a methodology for testing the accuracy and strength of cut generators for mixed-integer linear programming is presented. The procedure amounts to random diving towards a feasible solution, recording several kinds of failures. This allows for a ranking of the accuracy of the generators. Then, for generators deemed to have similar accuracy, statistical tests are performed to compare their relative strength. An application on eight Gomory cut generators and six Reduce-and-Split cut generators is given. The problem of constructing benchmark instances for which feasible solutions can be obtained is also addressed. Supported by ONR grant N00014-09-1-0033.     

On the linear complexity profile of nonlinear congruential pseudorandom number generators with Rédei functions

Linear complexity and linear complexity profile are important characteristics of a sequence for applications in cryptography and quasi-Monte Carlo methods. The nonlinear congruential method is an attractive alternative to the classical linear congruential method for pseudorandom number generation. We prove lower bounds on the linear complexity profile of nonlinear congruential pseudorandom number generators with Rédei functions which are much stronger than bounds known for general nonlinear congruential pseudorandom number generators.     

On the Linear Complexity Profile of Nonlinear Congruential Pseudorandom Number Generators with Dickson Polynomials

Linear complexity and linear complexity profile are important characteristics of a sequence for applications in cryptography and Monte-Carlo methods. The nonlinear congruential method is an attractive alternative to the classical linear congruential method for pseudorandom number generation. Recently, a weak lower bound on the linear complexity profile of a general nonlinear congruential pseudorandom number generator was proven by Gutierrez, Shparlinski and the first author. For most nonlinear generators a much stronger lower bound is expected. Here, we obtain a much stronger lower bound on the linear complexity profile of nonlinear congruential pseudorandom number generators with Dickson polynomials.     

On the Lax Pairs of the Symmetric Painlevé Equations

The symmetric forms of the Painlevé equations are a sequence of nonlinear dynamical systems in N + 1 variables that admit the action of an extended affine Weyl group of type     , as shown by Noumi and Yamada. They are equivalent to the periodic dressing chains studied by Veselov and Shabat, and by Adler. In this paper, a direct derivation of the symmetries of a corresponding sequence of ( N + 1) × ( N + 1) matrix linear systems (Lax pairs) is given. The action of the generators of the extended affine Weyl group of type     on the associated Lax pairs is realized through a set of transformations of the eigenfunctions, and this extends to an action of the whole group.     

Permutations which make transitive groups primitive

In this article we look into characterizing primitive groups in the following way. Given a primitive group we single out a subset of its generators such that these generators alone (the so-called primitive generators) imply the group is primitive. The remaining generators ensure transitivity or comply with specific features of the group. We show that, other than the symmetric and alternating groups, there are infinitely many primitive groups with one primitive generator each. These primitive groups are certain Mathieu groups, certain projective general and projective special linear groups, and certain subgroups of some affine special linear groups.     

A discrete model for optimal operation of fossil-fuel generators of electricity

This paper presents a new discrete approach to the price-based dynamic economic dispatch (PBDED) problem of fossil-fuel generators of electricity. The objective is to find a sequence of generator temperatures that maximizes profit over a fixed-length time horizon. The generic optimization model presented in this paper can be applied to automatic operation of fossil-fuel generators or to prepare market bids, and it works with various price forecasts. The model’s practical applications are demonstrated by the results of simulation experiments involving 2009 NYISO electricity market data, branch-and-bound, and tabu-search optimization techniques.     

Weakly Confluent Quadratic Algebras

Any quadratic algebra endowed with an ordered set of generators can bedescribed by some linear map called a reduction operator. The general lineargroup naturally acts on reduction operators, which allows us to introduceweak and strong confluence. With respect to these notions, a completeclassification for two generators and complex coefficients is obtainedshowing that weak confluence is equivalent to Koszulity in this case. Bycontrast, some Sklyanin algebras with three generators fail to be weaklyconfluent. For an arbitrary number of generators and under some assumptionson the first terms of the Hilbert series, a weak confluence hypothesis isequivalent to some rather drastic conditions which determine the whole ofthe Hilbert series.     

Hypernormal form theory: foundations and algorithms

Hypernormal forms (unique normal forms, simplest normal forms) are investigated both from the standpoint of foundational theory and algorithms suitable for use with computer algebra. The Baider theory of the Campbell-Hausdorff group is refined, by a study of its subgroups, to determine the smallest substages into which the hypernormalization process can be divided. This leads to a linear algebra algorithm to compute the generators needed for each substage with the least amount of work. A concrete interpretation of Jan Sanders’ spectral sequence for hypernormal forms is presented. Examples are given, and a proof is given for a little-known theorem of Belitskii expressing the hypernormal form space (in the inner product style) as the kernel of a higher-order differential operator.     

Automatic generation of linear programming problems for computer aided instruction

The paper presents a method for generating random linear programming problems with a previously selected type of solution. The user can choose a problem whose solution is unbounded, bounded for minima, maxima or both, unique or multiple, with given structure, at wish. Initially, the feasible solution of the LPP is generated as the sum of a linear space, a cone, and a polytope, depending on the desired properties of the solution. With the aim of obtaining a simple set of constraints, the generators of these three structures are selected as random vectors with integer simple components, the range of which can be given. Next, an objective function that satisfies the required conditions, i.e. leads to a solution of the desired type, is obtained. The generating algorithms have been implemented in Mathematica and some illustrative examples are given to clarify the generation process. With this tool, a LPP can be generated, according to the instructor requirements, where this is a human or an expert system. They can control student progress and generate a sequence of problems covering all possible cases, in steps of increasing difficulty. Combining this tool with another (also produced by the same authors) that solves the problems and explains the whole process, step by step, a computer aided module for learning LPP, which is completely autonomous, can be easily obtained.     

����Ԫ���������������ķ��䵹�����΢�ַ�������Ԫ�ı�ʾ����

In this paper, we establish a local representation theorem for generators of reflected backward stochastic differential equations (RBSDEs), whose generators are continuous with linear growth. It generalizes some known representation theorems for generators of backward stochastic differential equations (BSDEs). As some applications, a general converse comparison theorem for RBSDEs is obtained and some properties of RBSDEs are discussed.     

On the structure of digital explicit nonlinear and inversive pseudorandom number generators

We analyze the lattice structure and distribution of the digital explicit inversive pseudorandom number generator introduced by Niederreiter and Winterhof as well as of a general digital explicit nonlinear generator. In particular, we extend a lattice test designed for this class of pseudorandom number generators to parts of the period and arbitrary lags and prove that these generators pass this test up to very high dimensions. We also analyze the behavior of digital explicit inversive and nonlinear generators under another very strong lattice test which in its easiest form can be traced back to Marsaglia and provides a complexity measure essentially equivalent to linear complexity.     

On linear monotone iteration and Schwarz methods for nonlinear elliptic PDEs

Summary The Schwarz Alternating Method can be used to solve elliptic boundary value problems on domains which consist of two or more overlapping subdomains. The solution is approximated by an infinite sequence of functions which results from solving a sequence of elliptic boundary value problems in each subdomain. In this paper, proofs of convergence of some Schwarz Alternating Methods for nonlinear elliptic problems which are known to have solutions by the monotone method (also known as the method of subsolutions and supersolutions) are given. In particular, an additive Schwarz method for scalar as well some coupled nonlinear PDEs are shown to converge to some solution on finitely many subdomains, even when multiple solutions are possible. In the coupled system case, each subdomain PDE is linear, decoupled and can be solved concurrently with other subdomain PDEs. These results are applicable to several models in population biology. This work was in part supported by a grant from the RGC of HKSAR, China (HKUST6171/99P)     

Properties of Richard Thompson’s group F related to Følner sets

The group F was invented in the 1960s by Richard Thompson, and is a subgroup of the group of all piecewise linear, orientation preserving homeomorphisms of the unit interval. R. Geoghegan has conjectured that F is an example of a finitely presented nonamenable group which has no free subgroup on two generators. In this article, we study properties of F related to amenability. We state some necessary conditions that a sequence of nonempty finite subsets of F must satisfy to be a sequence of Følner sets of F.     

On the linear complexity profile of some new explicit inversive pseudorandom numbers

Linear complexity and linear complexity profile are interesting characteristics of a sequence for applications in cryptography and Monte-Carlo methods. We introduce some new explicit inversive pseudorandom number generators and prove lower bounds on their linear complexity profile which are close to the best possible.