共查询到20条相似文献,搜索用时 31 毫秒
1.
The rth order nonlinearity of a Boolean function is an important cryptographic criterion in analyzing the security of stream as well as block ciphers. It is also important in coding theory as it is related to the covering radius of the Reed-Muller code R(r,n). In this paper we deduce the lower bounds of the second order nonlinearities of the following two types of Boolean functions:
- 1.
- with d=22r+2r+1 and , where n=6r.
- 2.
- , where x,y∈F2t,n=2t,n?6 and i is an integer such that 1?i<t,gcd(2t-1,2i+1)=1.
2.
We propose cryptanalysis of the First Domingo-Ferrer's algebraic privacy homomorphism where n=pq. We show that the scheme can be broken by (d+1) known plaintexts in O(d3log2n) time. Even when the modulus n is kept secret, it can be broken by 2(d+1) known plaintexts in O(d4logdn+d3log2n+?(m)) time with overwhelming probability. 相似文献
3.
Jianbo Qian 《Information Processing Letters》2006,100(5):194-198
In this paper, we investigate the problem of the minimum nonzero difference between two sums of square roots of integers. Let r(n,k) be the minimum positive value of where ai and bi are integers not larger than integer n. We prove by an explicit construction that r(n,k)=O(n−2k+3/2) for fixed k and any n. Our result implies that in order to compare two sums of k square roots of integers with at most d digits per integer, one might need precision of as many as digits. We also prove that this bound is optimal for a wide range of integers, i.e., r(n,k)=Θ(n−2k+3/2) for fixed k and for those integers in the form of and , where n′ is any integer satisfied the form and i is any integer in [0,k−1]. We finally show that for k=2 and any n, this bound is also optimal, i.e., r(n,2)=Θ(n−7/2). 相似文献
4.
Cheng-shi Liu 《Computer Physics Communications》2010,181(2):317-2276
If a partial differential equation is reduced to an ordinary differential equation in the form u′(ξ)=G(u,θ1,…,θm) under the traveling wave transformation, where θ1,…,θm are parameters, its solutions can be written as an integral form . Therefore, the key steps are to determine the parameters' scopes and to solve the corresponding integral. When G is related to a polynomial, a mathematical tool named complete discrimination system for polynomial is applied to this problem so that the parameter's scopes can be determined easily. The complete discrimination system for polynomial is a natural generalization of the discrimination △=b2−4ac of the second degree polynomial ax2+bx+c. For example, the complete discrimination system for the third degree polynomial F(w)=w3+d2w2+d1w+d0 is given by and . In the paper, we give some new applications of the complete discrimination system for polynomial, that is, we give the classifications of traveling wave solutions to some nonlinear differential equations through solving the corresponding integrals. In finally, as a result, we give a partial answer to a problem on Fan's expansion method. 相似文献
5.
We present a simple method to use an [n−d−1,m,t+1] code to construct an n-input, m-output, t-resilient function with degree d>m and nonlinearity 2n−1−2n−⌈(d+1)/2⌉−(m+1)2n−d−1. For any fixed values of parameters n,m,t and d, with d>m, the nonlinearity obtained by our construction is higher than the nonlinearity obtained by Cheon in Crypto 2001. 相似文献
6.
Livio Colussi 《Theoretical computer science》2011,412(39):5409-5419
7.
E. Demenkov A. Kojevnikov A. Kulikov G. Yaroslavtsev 《Information Processing Letters》2010,110(7):264-267
In this note, we present improved upper bounds on the circuit complexity of symmetric Boolean functions. In particular, we describe circuits of size 4.5n+o(n) for any symmetric function of n variables, as well as circuits of size 3n for function. 相似文献
8.
Given a conjunctive normal form F with n variables and m=cn 2-clauses, it is interesting to study the maximum number of clauses satisfied by all the assignments of the variables (MAX 2-SAT). When c is sufficiently large, the upper bound of of random MAX 2-SAT had been derived by the first-moment argument. In this paper, we provide a tighter upper bound (3/4)cn+g(c)cn also using the first-moment argument but correcting the error items for f(n,cn), and when considering the ε3 error item. Furthermore, we extrapolate the region of the validity of the first-moment method is c>2.4094 by analyzing the higher order error items. 相似文献
9.
10.
The recursive circulant RC(n2,4) enjoys several attractive topological properties. Let max_?G(m) denote the maximum number of edges in a subgraph of graph G induced by m nodes. In this paper, we show that , where p0>p1>?>pr are nonnegative integers defined by . We then apply this formula to find the bisection width of RC(n2,4). The conclusion shows that, as n-dimensional cube, RC(n2,4) enjoys a linear bisection width. 相似文献
11.
12.
Let γ(G) denote the domination number of a digraph G and let Cm□Cn denote the Cartesian product of Cm and Cn, the directed cycles of length m,n?2. In this paper, we determine the exact values: γ(C2□Cn)=n; γ(C3□Cn)=n if , otherwise, γ(C3□Cn)=n+1; if , otherwise, . 相似文献
13.
Improving the running time of embedded upward planarity testing 总被引:1,自引:0,他引:1
Sarmad Abbasi 《Information Processing Letters》2010,110(7):274-278
We consider the standard algorithm by Bertolazzi et al. to test the upward planarity of embedded digraphs. We show how to improve its running time from O(n+r2) to , where r is the number of sources and sinks in the digraph. We also discuss an application of this technique: improving the running time of getting a quasi-upward planar drawing for an embedded digraph with minimum number of bends. 相似文献
14.
15.
Recently, S. Müller developed a generalized Atkin algorithm for computing square roots, which requires two exponentiations in finite fields GF(q) when . In this paper, we present a simple improvement to it and the improved algorithm requires only one exponentiation for half of squares in finite fields GF(q) when . Furthermore, in finite fields GF(pm), where and m is odd, we reduce the complexity of the algorithm from O(m3log3p) to O(m2log2p(logm+logp)) using the Frobenius map and normal basis representation. 相似文献
16.
Juan Liu 《Information Processing Letters》2008,108(3):90-93
We study the super-connected, hyper-connected and super-arc-connected Cartesian product of digraphs. The following two main results will be obtained:
- (i)
- If δ+(Di)=δ−(Di)=δ(Di)=κ(Di) for i=1,2, then D1×D2 is super-κ if and only if ,
- (ii)
- If δ+(Di)=δ−(Di)=δ(Di)=λ(Di) for i=1,2, then D1×D2 is super-λ if and only if ,
17.
18.
19.
It has been shown that for every perfect matching M of the d-dimensional n-vertex hypercube, d?2, n=d2, there exists a second perfect matching M′ such that the union of M and M′ forms a Hamiltonian circuit of the d-dimensional hypercube. We prove a generalization of a special case of this result when there are two dimensions that do not get used by M. It is known that the number Md of perfect matchings of the d-dimensional hypercube satisfies and, in particular, (2d/n)n/2(n/2)!?Md?(d!)n/(2d). It has also been shown that the number Hd of Hamiltonian circuits of the hypercube satisfies 1?limd→∞(logHd)/(logMd)?2. We finally strengthen this result to a nearly tight bound ((dlog2/(eloglogd))(1−on(1)))?Hd?(d!)n/(2d)((d−1)!)n/(2(d−1))/2 proving that limd→∞(logHd)/(logMd)=2. This means that the bound Hd?Md is improved to a nearly tight , so the number of Hamiltonian circuits in the hypercube is nearly quadratic in the number of perfect matchings. The proofs are based on a result for graphs that are the Cartesian product of squares and arbitrary bipartite regular graphs that have a Hamiltonian cycle. We also study a labeling scheme related to matchings. 相似文献
20.
Chris Giannella 《Information Processing Letters》2009,109(19):1109-1113
Consider a dataset of n(d) points generated independently from Rd according to a common p.d.f. fd with support(fd)=d[0,1] and sup{fd(Rd)} growing sub-exponentially in d. We prove that: (i) if n(d) grows sub-exponentially in d, then, for any query point and any ?>0, the ratio of the distance between any two dataset points and is less that 1+? with probability →1 as d→∞; (ii) if n(d)>d[4(1+?)] for large d, then for all (except a small subset) and any ?>0, the distance ratio is less than 1+? with limiting probability strictly bounded away from one. Moreover, we provide preliminary results along the lines of (i) when . 相似文献