Let (Un)n is an element of N be a fixed linear recurrence sequence defined over the integers (with some technical restrictions). We prove that there exist effectively computable constants B and N0 such that for any b,...
详细信息
Let (Un)n is an element of N be a fixed linear recurrence sequence defined over the integers (with some technical restrictions). We prove that there exist effectively computable constants B and N0 such that for any b, c E Z with b > B the equation Un -bm = c has at most two distinct solutions (n, m) E N2 with n > N0 and m > 1. Moreover, we apply our result to the special case of Tribonacci numbers given by T1 = T2 = 1, T3 = 2 and Tn = Tn-1 + Tn-2 + Tn-3 for n > 4. By means of the lll-algorithm and continued fraction reduction we are able to prove N0 = 2 and B = e438. The corresponding reduction algorithm is implemented in Sage.
For k >= 2, the sequence (F-n((k)))(n >=-(k-2)) of k-generalized Fibonacci numbers is defined by the initial values 0, ..., 0, 1 = F-1((k)) and such that each term afterwards is the sum of the k preceding ones. ...
详细信息
For k >= 2, the sequence (F-n((k)))(n >=-(k-2)) of k-generalized Fibonacci numbers is defined by the initial values 0, ..., 0, 1 = F-1((k)) and such that each term afterwards is the sum of the k preceding ones. There are many recent results about the Diophantine equation (F-n((k)))(s) + (F-n+1((k)))(s) = F-m((l)), most of them dealing with the case k = l. In 2018, Bednarik et al. solved the equation for k <= l, but with s = 2. The aim of this paper is to continue this line of investigation by solving this equation for all s >= 2, but with (k, l) = (3, 2).
The Shortest Vector Problem and the computation of the tame kernel in algebraic K-theory are two different but very important problems, and up to now no one has found any manipulated relations between them. In this pa...
详细信息
The Shortest Vector Problem and the computation of the tame kernel in algebraic K-theory are two different but very important problems, and up to now no one has found any manipulated relations between them. In this paper, we are successful for the first time to reduce the computation of tame kernel, in particular the computation of elements of the set C-m, the key part in the method proposed by Tate, to the Shortest Vector Problem of some lattice. Then, with the help of PARI library we implement the above idea and develop a program for computing the tame kernels of the cyclotomic fields with class number 1, and as an example, by running the program we obtain the tame kernel of the cyclotomic field Q(zeta(7)). (C) 2021 Elsevier Inc. All rights reserved.
Let h and (f, g) be the public and private keys of NTRU respectively. We present a new lattice to attack NTRU when the private polynomial g has one or more consecutive coefficients which are equal zeros, i.e., zero pa...
详细信息
Let h and (f, g) be the public and private keys of NTRU respectively. We present a new lattice to attack NTRU when the private polynomial g has one or more consecutive coefficients which are equal zeros, i.e., zero patterns. The target vector of the new lattice contains the private polynomial f, and the ratio between the size of the target vector and the expected size of a shortest non-zero vector in the new lattice is smaller than the ratio declared in the previous results. The zero patterns are not necessarily of the same or long lengths. Experimental results show that our attack succeeded to cryptanalyze NTRU faster than the previous attacks.
In this article we develop algorithms for solving the dual problems of approximating linear forms and of simultaneous approximation in number fields F. Using earlier ideas for computing independent units by Buchmann, ...
详细信息
In this article we develop algorithms for solving the dual problems of approximating linear forms and of simultaneous approximation in number fields F. Using earlier ideas for computing independent units by Buchmann, Petho and later Pohst we construct sequences of suitable modules in F and special elements beta contained in them. The most important ingredient in our methods is the application of the lll-reduction procedure to the bases of those modules. For lll-reduced bases we derive improved bounds on the sizes of the basis elements. From those bounds it is quite straightforward to show that the sequence of coefficient vectors (x(1),..., x(n)) of the presentation of beta in the module basis becomes periodic. We can show that the approximations which we obtain are close to being optimal. Moreover, it is periodic on bases of real number fields. Thus our algorithm can be considered as a generalization, within the framework of number fields, of the continued fraction algorithm. (C) 2016 Elsevier Inc. All rights reserved.
Lattice-based reformulation techniques have been used successfully both theoretically and computationally. One such reformulation is obtained from the kernel lattice associated with an input matrix. Some of the hard i...
详细信息
Lattice-based reformulation techniques have been used successfully both theoretically and computationally. One such reformulation is obtained from the kernel lattice associated with an input matrix. Some of the hard instances in the literature that have been successfully tackled by lattice-based techniques have randomly generated input. Since the considered instances are very hard even in low dimension, less experience is available for larger instances. Recently, we have studied larger instances and observed that the lll-reduced basis of the kernel lattice has a specific sparse structure. In particular, this translates into a map in which some of the original variables get a "rich"' translation into a new variable space, whereas some variables are only substituted in the new space. If an original variable is important in the sense of branching or cutting planes, this variable should be translated in a nontrivial way. In this paper we partially explain, through a probabilistic analysis, the obtained structure of the lll-reduced basis in the case that the input matrix consists of one row. The key ingredient is a bound on the probability that the lll-algorithm will interchange two subsequent basis vectors.
Average bit error rate (BER) performance of single-carrier (SC) transmission significantly degrades due to the strong inter-symbol interference (ISI) in a severe frequency-selective fading channel. Recently, we propos...
详细信息
ISBN:
(纸本)9781424424238
Average bit error rate (BER) performance of single-carrier (SC) transmission significantly degrades due to the strong inter-symbol interference (ISI) in a severe frequency-selective fading channel. Recently, we proposed a joint Tomlinson-Harashima precoding (THP)/frequency-domain pre-equalization (pre-FDE) using LQ-decomposition to improve the BER performance of SC transmission. However, since the dummy symbols insertion is necessary, the data rate reduces. In this paper, we apply lll-algorithm to joint THP/pre-FDE to avoid the dummy symbol insertion and evaluate the BER performance by computer simulation.
Average bit error rate (BER) performance of singlecarrier (SC) transmission significantly degrades due to the strong inter-symbol interference (ISI) in a severe frequency-selective fading channel. Recently, we propose...
详细信息
Average bit error rate (BER) performance of singlecarrier (SC) transmission significantly degrades due to the strong inter-symbol interference (ISI) in a severe frequency-selective fading channel. Recently, we proposed a joint Tomlinson-Harashima precoding (THP)/frequency-domain pre-equalization (pre-FDE) using LQ-decomposition to improve the BER performance of SC transmission. However, since the dummy symbols insertion is necessary, the data rate reduces. In this paper, we apply lll-algorithm to joint THP/pre-FDE to avoid the dummy symbol insertion and evaluate the BER performance by computer simulation.
In this paper,the integer N = pkq is called a -integer,if p and q are odd primes with almost the same size and k is a positive integer. Such integers were previously proposed for various cryptographic applications. Th...
详细信息
In this paper,the integer N = pkq is called a -integer,if p and q are odd primes with almost the same size and k is a positive integer. Such integers were previously proposed for various cryptographic applications. The conditional factorization based on lattice theory for n-bit -integersis considered,and there is an algorithm in time polynomial in n to factor these integers if the least significant 「((2k-1)n)/((3k-1)(k+1))」bits of p are given.
This is a complement to my previous article "Advanced Determinant Calculus" [C. Krattenthaler, Advanced determinant calculus, Seminaire Lotharingien Combin. 42 (1999) ("The Andrews Festschrift"), A...
详细信息
This is a complement to my previous article "Advanced Determinant Calculus" [C. Krattenthaler, Advanced determinant calculus, Seminaire Lotharingien Combin. 42 (1999) ("The Andrews Festschrift"), Article B42q, 67 pp.]. In the present article, I share with the reader my experience of applying the methods described in the previous article in order to solve a particular problem from number theory [G. Almkvist, C. Krattenthaler, J. Petersson, Some new formulas for pi, Experiment. Math. 12 (2003) 441-456]. Moreover, I add a list of determinant evaluations which I consider as interesting, which have been found since the appearance of the previous article, or which I failed to mention there, including several conjectures and open problems. (c) 2005 Elsevier Inc. All rights reserved.
暂无评论