Search

An algorithm is presented that, taking independent Bernoulli random variables with parameter 1 / 2 as inputs and using only rational arithmetic, simulates a Bernoulli random variable with possibly irrational parameter τ. It requires a series representation of τ with positive, rational terms, and a rational bound on its truncation error that converges to 0. The number of required inputs has an exponentially bounded tail, and its mean is at most 3. The number of arithmetic operations has a tail that can be bounded in terms of the sequence of truncation error bounds. The algorithm is applied to two specific values of τ , including Euler's constant, for which obtaining a simple simulation algorithm was an open problem. [ABSTRACT FROM AUTHOR]

Permutations mostly in the form of sboxes are very efficient components largely present in cryptographic artifacts either hardware or software. They have been well studied as an individual component and have a large body of knowledge. Here we look at the properties of tiny transformations employing permutations and a few field operations. That gives functions with few components, which can be safely used either as PRG building blocks or as a component in lightweight ciphers. At the end, we propose a PRG implementation with those components. Lastly, we formalize a key assumption over the system functions and give a theorem for the equivalence of some system instances. [ABSTRACT FROM AUTHOR]

An efficient random variable generator for a truncated gamma distribution with shape parameter greater than 1 is designed using an acceptance-rejection algorithm. Based on an approximation to a transformed gamma density function by the standard normal density, numerical information for the standard normal density is prepared in advance, and the calculation is performed with reference to that information. An improvement via a squeezing method is proposed to reduce the computational burden and time. The algorithm's acceptance rate for generating truncated gamma variables is very high and almost 1 when the truncated distribution is unimodal. Numerical experiments for one- and two-sided truncated domain cases are conducted to measure the execution time, including the parameter setup time. Compared with existing truncated gamma variate generators, the proposed method performs better when the distribution is unimodal and the shape parameter is equal to or greater than 3.3. [ABSTRACT FROM AUTHOR]

Simplices are the fundamental domain when integrating over convex polytopes. The aim of this work is to establish a novel framework of Monte Carlo integration over simplices, throughout from sampling to variance reduction. Namely, we develop a uniform sampling method on the standard simplex consisting of two independent procedures and construct theories on change of measure on each of the two independent elements in the developed sampling technique with a view towards variance reduction by importance sampling. We provide illustrative figures and numerical results to support our theoretical findings and demonstrate the strong potential of the developed framework for effective implementation and acceleration of Monte Carlo integration over simplices. [ABSTRACT FROM AUTHOR]

As the first generic method for finding the optimal differentialand linear characteristics, Matsui's branch and bound search algorithm has played an important role in evaluating the security of symmetric ciphers. By combining Matsui's bounding conditions with automatic search models, search efficiency can be improved. In this paper, by studying the properties of Matsui's bounding conditions, we give the general form of bounding conditions that can eliminate all the impossible solutions determined by Matsui's bounding conditions. Then, a new method of combining bounding conditions with sequential encoding method is proposed. With the help of some small size Mixed Integer Linear Programming (MILP) models, we can use fewer variables and clauses to build Satisfiability Problem (SAT) models. As applications, we use our new method to search for the optimal differential and linear characteristics of some SPN, Feistel, and ARX block ciphers. The number of variables and clauses and the solving time of the SAT models are decreased significantly. In addition, we find some new differential and linear characteristics covering more rounds. [ABSTRACT FROM AUTHOR]

In this paper, we introduce a new algorithm for estimating the lower bounds for the star discrepancy of any arbitrary point sets in [ 0 , 1 ] s . Computing the exact star discrepancy is known to be an NP-hard problem, so we have been looking for effective approximation algorithms. The star discrepancy can be thought of as the maximum of a function called the local discrepancy, and we will develop approximation algorithms to maximize this function. Our algorithm is analogous to the random walk algorithm described in one of our previous papers [M. Alsolami and M. Mascagni, A random walk algorithm to estimate a lower bound of the star discrepancy, Monte Carlo Methods Appl.28 (2022), 4, 341–348.]. We add a statistical technique to the random walk algorithm by implementing the Metropolis algorithm in random walks on each chosen dimension to accept or reject this movement. We call this Metropolis random walk algorithm. In comparison to all previously known techniques, our new algorithm is superior, especially in high dimensions. Also, it can quickly determine the precise value of the star discrepancy in most of our data sets of various sizes and dimensions, or at least the lower bounds of the star discrepancy. [ABSTRACT FROM AUTHOR]

A regression model, based on the well-known log-logistic distribution is proposed. This model is parameterized in terms of the median of the distribution, through a link function. The regression model assumes the censored data structure. The unknown parameters are estimated by maximum likelihood. Monte Carlo simulations with censoring and application to real censored data show the good quality of the proposed regression model. [ABSTRACT FROM AUTHOR]

A quaternary sequence is said to be good if its maximum nontrivial autocorrelation is very low relative to its period. In this paper, we present some new classes of quaternary sequences with low autocorrelation of period N via two binary cyclotomic sequences, where N ≡ 1 (mod 4) is an odd prime. Furthermore, we determine the linear complexity and minimal polynomials of these quaternary sequences over F 2 2 as well. [ABSTRACT FROM AUTHOR]

In many Monte Carlo applications, one can substitute the use of pseudorandom numbers with quasirandom numbers and achieve improved convergence. This is because quasirandom numbers are more uniform that pseudorandom numbers. The most common measure of that uniformity is the star discrepancy. Moreover, the main error bound in quasi-Monte Carlo methods, called the Koksma–Hlawka inequality, has the star discrepancy in the formulation. A difficulty with this bound is that computing the star discrepancy is very costly. The star discrepancy can be computed by evaluating a function called the local discrepancy at a number of points. The supremum of these local discrepancy values is the star discrepancy. If we have a point set in [ 0 , 1 ] s with N members, we need to compute the local discrepancy at N s points. In fact, computing star discrepancy is NP-hard. In this paper, we will consider an approximate algorithm for a lower bound on the star discrepancy based on using a random walk through some of the N s points. This approximation is much less expensive that computing the star discrepancy, but still accurate enough to provide information on convergence. Our numerical results show that the random walk algorithm has the same convergence rate as the Monte Carlo method, which is O (N - 1 2 ). [ABSTRACT FROM AUTHOR]

Traditional global stability measure for sequences is hard to determine because of large search space. We propose the k-error linear complexity with a zone restriction for measuring the local stability of sequences. For several classes of sequences, we demonstrate that the k-error linear complexity is identical to the k-error linear complexity within a zone, while the length of a zone is much smaller than the whole period when the k-error linear complexity is large. These sequences have periods 2 n , or 2 v r (r odd prime and 2 is primitive modulo r), or 2 v p 1 s 1 ⋯ p n s n ( p i is an odd prime and 2 is primitive modulo p i 2 , where 1 ≤ i ≤ n ) respectively. In particular, we completely determine the spectrum of 1-error linear complexity with any zone length for an arbitrary 2 n -periodic binary sequence. [ABSTRACT FROM AUTHOR]

R. Hofer and A. Winterhof proved that the 2-adic complexity of the two-prime (binary) generator of period pq with two odd primes p ≠ q is close to its period and it can attain the maximum in many cases. When the two-prime generator is applied to producing quaternary sequences, we need to determine the 4-adic complexity. It is proved that there are only two possible values of the 4-adic complexity for the two-prime quaternary generator, which are at least p q - 1 - max { log 4 (p q 2) , log 4 (p 2 q) } . Examples for primes p and q with 5 ≤ p , q < 10000 illustrate that the 4-adic complexity only takes one value larger than p q - max { log 4 (p) , log 4 (q) } , which is close to its period. So it is good enough to resist the attack of the rational approximation algorithm. [ABSTRACT FROM AUTHOR]

Random numbers are used in a variety of applications including simulation, sampling, and cryptography. Fortunately, there exist many well-established methods of random number generation. An example of a well-known pseudorandom number generator is the lagged-Fibonacci generator (LFG). Marsaglia showed that the lagged-Fibonacci generator using addition failed some of his DIEHARD statistical tests, while it passed all when longer lags were used. This paper presents a scrambler that takes bits from a pseudorandom number generator and outputs (hopefully) improved pseudorandom numbers. The scrambler is based on a modified Feistel function, a method used in the generation of cryptographic random numbers, and multiplication by a chosen multiplier. We show that this scrambler improves the quality of pseudorandom numbers by applying it to the additive LFG with small lags. The scrambler performs well based on its performance with the TestU01 suite of randomness tests. The TestU01 suite of randomness tests is more comprehensive than the DIEHARD tests. In fact, the specific suite of tests we used from TestU01 includes the DIEHARD tests The scrambling of the LFG is so successful that scrambled LFGs with small lags perform as well as unscrambled LFGs with long lags. This comes at the cost of a doubling of execution time, and provides users with generators with small memory footprints that can provide parallel generators like the LFGs in the SPRNG parallel random number generation package. [ABSTRACT FROM AUTHOR]

Discrete tempered stable distributions are a large and flexible class of models for heavy tailed and overdispersed count data. In this paper we derive various properties of these distributions and develop an exact simulation method based on rejection sampling and a compound Poisson representation. We extend this method to exact simulation of the corresponding bilateral distributions and Lévy processes. [ABSTRACT FROM AUTHOR]

The primary aim of the paper is to put forward methods of generating two dimensional (2D) and three dimensional (3D) normal pseudo-random numbers (NPRNs). Both proposed methods are presented in two versions. The first version is based on uniform (0,1) random variables, while the second version is based on normal random variables. Joint summands in these methods make resulting normal numbers correlated. The secondary aim of the paper is to compare the existing methods of generating 2D and 3D NPRNs with new proposals using goodness-of-fit tests (GoFTs), generation time and specially defined measures. The obtained results indicate that the methods based on uniform (0,1) random variables are faster than the others (have the best computational complexity) and also stand out from the other measures and GoFTs used. [ABSTRACT FROM AUTHOR]

Linear complexity test included in the NIST test suite only checks whether or not the observed linear complexity is close to the expected linear complexity. To take full advantage of the information of the linear complexity profile, we propose two randomness tests including a jump test based on the jump complexity, i. e., the number of changes in the linear complexity profile of a sequence, and a hop test checking the sum of jump heights at intervals. By using an iterative algorithm we calculate some necessary statistical measures of a random sequence of length M, and combining with hypothesis test we determine whether a given binary sequence is random or not. Moreover, we provide the explicit formulae of the expectation and the variance of the statistical measure of the hop test. The computational complexity of the jump test and the hop test is the same as that of the linear complexity test. Additionally, we provide a type of sample which, having passed all tests in the NIST test suite, is rejected by the jump test and hop test. So the proposed tests deserve to be considered. [ABSTRACT FROM AUTHOR]

By applying the cumulative hazard transformation, nonparametric prediction, inner and outer intervals based on generalized order statistics (GOSs) are obtained and their exact coverage probabilities are determined. The predictive intervals are accomplished based on informative sample of fixed, as well as random, number of GOSs from a continuous cumulative distribution function (CDF) F. When the sample size is random variable (RV), it is assumed to be positive integer and independent of both informative and future samples. Simulation study and numerical computations are conducted for illustrative purposes. [ABSTRACT FROM AUTHOR]

This paper is devoted to two efficient algorithms for solving variational inequality on Hadamard manifolds. The algorithms are inspired by Tseng's extragradient methods with new step sizes, established without the knowledge of the Lipschitz constant of the mapping. Under a pseudomonotone assumption on the underlying vector field, we prove that the sequence generated by the methods converges to a solution of variational inequality, whenever it exists. [ABSTRACT FROM AUTHOR]

Two simulation algorithms for hierarchical Archimedean copulas in the case when intra-group generators are not necessarily completely monotone are presented. Both generalize existing algorithms for the completely monotone case. The underlying stochastic models for both algorithms arise as a particular instance of a more general probability space studied recently in Ressel, P. (2018): A multivariate version of Williamson’s theorem, ℓ1-symmetric survival functions, and generalized Archimedean copulas. Depend. Model. 6, 356–368. On this probability space the inter-group dependence need not be Archimedean, however, we highlight two particular circumstances that guarantee that a hierarchical Archimedean copula is obtained.

A projected extrapolated gradient method is designed for solving monotone variational inequality in Hilbert space. Requiring local Lipschitz continuity of the operator, our proposed method improves the value of the extrapolated parameter and admits larger step sizes, which are predicted based a local information of the involved operator and corrected by bounding the distance between each pair of successive iterates. The correction will be implemented when the distance is larger than a given constant and its main cost is to compute a projection onto the feasible set. In particular, when the operator is the gradient of a convex function, the correction step is not necessary. We establish the convergence and ergodic convergence rate in theory under the larger range of parameters. Related numerical experiments illustrate the improvements in efficiency from the larger step sizes. [ABSTRACT FROM AUTHOR]

The efficient evaluation of high-dimensional integrals is important from both theoretical and practical points of view. In particular, multidimensional integration plays a central role in Bayesian inference, statistical physics, data science, and machine learning. However, due to the curse of dimensionality, deterministic numerical methods are inefficient in the high-dimensional setting. Consequentially, for many practical problems one must resort to approximate estimation techniques such as Monte Carlo methods. In this article, we introduce a novel sequential Monte Carlo algorithm called stratified splitting. The method provides unbiased estimates and can handle various integrand types including indicator functions, which are important for rare-event probability estimation problems. We provide rigorous analysis of the efficiency of the proposed method and present a numerical demonstration of the algorithmic performance when applied to practical application domains. Our numerical experiments suggest that the stratified splitting method is capable of delivering accurate results for a variety of integration problems while requiring reasonable computational effort. [ABSTRACT FROM AUTHOR]

We propose Tseng's extragradient methods for finding a solution of variational inequality problems associated with pseudomonotone vector fields in Hadamard manifolds. Under standard assumptions such as pseudomonotone and Lipschitz continuous vector fields, we prove that any sequence generated by the proposed methods converges to a solution of variational inequality problem, whenever it exits. Moreover, we give some numerical experiments to illustrate our main results. [ABSTRACT FROM AUTHOR]

NIST SP800-22 is one of the most widely used statistical testing tools for pseudorandom number generators (PRNGs). This tool consists of 15 tests (one-level tests) and two additional tests (two-level tests). Each one-level test provides one or more p-values. The two-level tests measure the uniformity of the obtained p-values for a fixed one-level test. One of the two-level tests categorizes the p-values into ten intervals of equal length, and apply a chi-squared goodness-of-fit test. This two-level test is often more powerful than one-level tests, but sometimes it rejects even good PRNGs when the sample size at the second level is too large, since it detects approximation errors in the computation of p-values. In this paper, we propose a practical upper limit of the sample size in this two-level test, for each of six tests appeared in SP800-22. These upper limits are derived by the chi-squared discrepancy between the distribution of the approximated p-values and the uniform distribution U(0, 1). We also computed a "risky" sample size at the second level for each one-level test. Our experiments show that the two-level test with the proposed upper limit gives appropriate results, while using the risky size often rejects even good PRNGs. We also propose another improvement: to use the exact probability for the ten categories in the computation of goodness-of-fit at the two-level test. This allows us to increase the sample size at the second level, and would make the test more sensitive than the NIST's recommending usage. [ABSTRACT FROM AUTHOR]

We give an explicit representation for the transition law of a tempered stable Ornstein–Uhlenbeck process and use it to develop a rejection sampling algorithm for exact simulation of increments from this process. Our results apply to general classes of both univariate and multivariate tempered stable distributions and contain a number of previously studied results as special cases. [ABSTRACT FROM AUTHOR]

We construct an algorithm that permits a large group of individuals to reach consensus on a random number, without having to rely on any third parties. The algorithm works with high probability if there are less than 50 of colluding parties in the group. We describe also some modifications and generalizations of the algorithm.

For distinct odd primes N and p, we view the N-periodic binary Legendre sequence as a p-ary sequence and present its trace representation via trace functions over F p . We use a skill to calculate the Mattson–Solomon polynomials of Legendre sequences and then describe the Mattson–Solomon polynomials by means of trace functions over F p . [ABSTRACT FROM AUTHOR]

It is well-known that the expected scaled maximum of non-negative random variables with unit mean defines a stable tail dependence function associated with some extreme-value copula. In the special case when these random variables are independent and identically distributed, min-stable multivariate exponential random vectors with the associated survival extreme-value copulas are shown to arise as finite-dimensional margins of an infinite exchangeable sequence in the sense of De Finetti’s Theorem. The associated latent factor is a stochastic process which is strongly infinitely divisible with respect to time, which induces a bijection from the set of distribution functions F of non-negative random variables with finite mean to the set of Lévy measures ν on ( 0 , ∞ ] . Since the Gumbel and the Galambos copula are the most popular examples of this construction, the investigation of this bijection contributes to a further understanding of their well-known analytical similarities. Furthermore, a simulation algorithm based on the latent factor representation is developed, if the support of F is bounded. Especially in large dimensions, this algorithm is efficient because it makes use of the De Finetti structure. [ABSTRACT FROM AUTHOR]

T-functions have been widely used in the design of symmetric ciphers, hash functions, and fast cryptographic primitives. Single cycle polynomial T-functions are a special category. If they are used as state transition functions of stream ciphers, the security of the generated sequences is crucial. In 2008, Kolokotronis proposed a conjecture regarding the autocorrelation function’s values of coordinate sequences generated by single cycle polynomial T-functions. In this paper, we show that the conjecture does not hold in general and prove the conditions under which it holds. [ABSTRACT FROM AUTHOR]

Pseudo-random sequences with good statistical properties, such as low autocorrelation, high linear complexity and large 2-adic complexity, have been used in designing reliable stream ciphers. In this paper, we obtain the exact autocorrelation distribution of a class of binary sequences with three-level autocorrelation and analyze the 2-adic complexity of this class of sequences. Our results show that the 2-adic complexity of such a binary sequence with period N is at least (N + 1) − log2 (N + 1). We further show that it is maximal for infinitely many cases. This indicates that the 2-adic complexity of this class of sequences is large enough to resist the attack of the rational approximation algorithm (RAA) for feedback with carry shift registers (FCSRs). [ABSTRACT FROM AUTHOR]

For an elliptic curve E over a finite field we define the point sequence (Pn) recursively by Pn=ϑ(Pn-1)=ϑn(P0) with an endomorphism ϑ∈End(E) and with some initial point P0 on E. We study the distribution and the linear complexity of sequences obtained from (Pn). [ABSTRACT FROM AUTHOR]

Trustworthy generation of public random numbers is necessary for the security of a number of cryptographic applications. It was suggested to use the inherent unpredictability of blockchains as a source of public randomness. Entropy from the Bitcoin blockchain in particular has been used in lotteries and has been suggested for a number of other applications ranging from smart contracts to election auditing. In this Arcticle, we analyse this idea and show how an adversary could manipulate these random numbers, even with limited computational power and financial budget. [ABSTRACT FROM AUTHOR]

We quantify precisely the distribution of the output of a binary random number generator (RNG) after conditioning with a binary linear code generator matrix by showing the connection between the Walsh spectrum of the resulting random variable and the weight distribution of the code. Previously known bounds on the performance of linear binary codes as entropy extractors can be derived by considering generator matrices as a selector of a subset of that spectrum. We also extend this framework to the case of non-binary codes. [ABSTRACT FROM AUTHOR]

This article simulates the stationary M/M/1 retrial queues using Simple Random Sampling (SRS) and Refined Descriptive Sampling (RDS) to generate input variables. We design and realize a software under Linux using C language which establishes the performance measures of the M/M/1 retrial queues, computes their relative deviation and their variance reductions in order to compare both sampling methods. The simulation results demonstrate that RDS produces more accurate and efficient point estimates of the true parameters and can significantly improves performance sometimes by an important variance reduction factor in the M/M/1retrial queue compared to SRS. [ABSTRACT FROM AUTHOR]

Simulation of multivariate distributions is important in many applications but remains computationally challenging in practice. In this article, we introduce three classes of multivariate distributions from which simulation can be conducted by means of their stochastic representations related to the Dirichlet random vector. More emphasis is made to simulation from the class of uniform distributions over a polyhedron, which is useful for solving some constrained optimization problems and ha's many applications in sampling and Monte Carlo simulations. Numerical evidences show that, by utilizing state-of-the-art Dirichlet generation algorithms, the introduced methods become superior to other approaches in terms of computational efficiency. [ABSTRACT FROM AUTHOR]

We define a family of quaternary sequences over the residue class ring modulo 4 of length pq, a product of two distinct odd primes, using the generalized cyclotomic classes modulo pq and calculate the discrete Fourier transform (DFT) of the sequences. The DFT helps us to determine the exact values of linear complexity and the trace representation of the sequences. [ABSTRACT FROM AUTHOR]

This paper proposes non parametric adaptive refined descriptive sampling algorithm (NARDS) to estimate the survival function in lifetime models using Kaplan–Meier and Fleming–Harrington estimators. Simulations were performed using real data to generate inputs. The obtained results prove that NARDS works well on non parametric data. [ABSTRACT FROM AUTHOR]