Vol 37, No 6 (2016)

We introduce quantum alternation as a generalization of quantum nondeterminism. We define q-alternating Turing machine (qATM) by augmenting alternating Turing machine with constant-size quantum memory. We show that one-way constant-space qATMs (1AQFAs) are Turing equivalent. Then, we introduce strong version of qATM by requiring to halt in every computation path and we show that strong qATMs can simulate deterministic spacewith exponentially less space. This leads to shifting the deterministic space hierarchy exactly by one level. We also focus on realtime versions of 1AQFAs (rtAQFAs) and obtain many results: rtAQFAs can recognize a PSPACE-complete problem; they cannot be simulated by sublinear deterministic Turing machines; for any level of polynomial hierarchy, say k, there exists a complete language that can be recognized by rtAFAs with only (k +1) alternations; and polynomial hierarchy lies in its log-space q-alternation counterpart.

In the paper we investigate Ordered Binary Decision Diagrams (OBDDs)–a model for computing Boolean functions. We present a series of results on the comparative complexity for several variants of OBDDmodels.

• We present results on the comparative complexity of classical and quantum OBDDs. We consider a partial function depending on a parameter k such that for any k > 0 this function is computed by an exact quantum OBDD of width 2, but any classical OBDD (deterministic or stable bounded-error probabilistic) needs width 2^k+1.

• We consider quantum and classical nondeterminism. We show that quantum nondeterminismcan bemore efficient than classical nondeterminism. In particular, an explicit function is presented that is computed by a quantum nondeterministic OBDD of constant width but any classical nondeterministic OBDD for this function needs non-constant width.

• We also present new hierarchies on widths of deterministic and nondeterministic OBDDs.

We present two new constructions of quantum hash functions: the first based on expander graphs and the second based on extractor functions and estimate the amount of randomness that is needed to construct them. We also propose a keyed quantum hash function based on extractor function that can be used in quantum message authentication codes and assess its security in a limited attacker model.

In our paper we elaborate a new version of the k-ary GCD algorithm. Our algorithm is based on the Farey Series and surpasses all existing realizations of the k-ary algorithm. It can have practical applications inMathematics and Cryptography.

Integer n is called pseudoprime (psp) relative to base a if n is composite, (a, n) = 1, and aⁿ⁻¹ mod n = 1. Integer n is called strong pseudoprime (spsp) relative to base a if n is composite, (a, n) = 1, and, a^d mod n = 1, or, \({a^{d{2^i}}}\) mod n = −1, where n −1 = 2^s * d, d is odd, 0 ≤ i < s. Pseudoprime and strong pseudoprime numbers are used in public-key cryptography in probabilistic tests. We use recurrent sequences in the task of search pseudoprime and strong pseudoprime numbers. This article describes acceleration of GCD calculation.

The criterion for coincidence of spectral radiuses of a complex matrix A and of the matrix |A| obtained by replacing entries of A by their absolute values was given by Wielandt. In this paper we give the new criterion for the above coincidence.

In the paper we define a notion of quantum resistant ((δ, є)-resistant) hash function which combine together a notion of pre-image (one-way) resistance (δ-resistance) property and the notion of collision resistance (є-resistance) properties. We present a discussion that supports the idea of quantum hashing oriented for cryptographical purposes. We propose a quantum setting of a classical digital signature scheme do demonstrate a theoretical possibilities and restrictions of (δ, є)-hashing. The assumption we use is that a set of qubits (quantum hash) we generate, send, and receive during the execution of a protocol can be stored for a certain (a large enough) amount of time; next, the scheme requires the high degree of entanglement between the qubits which makes such a quantum hash. These properties make quantum hash cryptographically efficient.

A numerical method is suggested for solving the multidimensional inverse problem of finding the flow rates of wells from given bottomhole pressures in the multidimensional flow model of a weakly compressible liquid in a poroelastic medium. Spatial approximation is based on the finite element method, which allows one to employ unstructured grids with refinements near the location of wells. Time discretization is performed with the use of implicit difference approximation. The numerical results for two- and three-dimensional test problems are presented.

A class of functionals on a domain in Euclidean space is constructed and a Brunn–Minkowski-type inequality for this class is proved. The construction of the functionals on the domain uses a point of minimum of a function of many variables related to these functionals; proving the existence of this function is an essential point of the study. Special cases of functionals for which the point of minimum can be found explicitly are considered. The obtained Brunn–Minkowski inequality generalizes the corresponding inequality for moments with respect to the center of mass and hyperplanes proved by Hadwiger to the case of power moments. It is worth mentioning that the point of minimum of the functional does not generally coincide with the center of mass; the coincidence occurs only in special cases, which is confirmed by particular examples.