An Efficient Parallel Reverse Conversion of Residue Code to Mixed-Radix Representation Based on the Chinese Remainder Theorem

In this paper, we deal with the critical problems in residue arithmetic. The reverse conversion from a Residue Number System (RNS) to positional notation is a main non-modular operation, and it constitutes a basis of other non-modular procedures used to implement various computational algorithms. We present a novel approach to the parallel reverse conversion from the residue code into a weighted number representation in the Mixed-Radix System (MRS). In our proposed method, the calculation of mixed-radix digits reduces to a parallel summation of the small word-length residues in the independent modular channels corresponding to the primary RNS moduli. The computational complexity of the developed method concerning both required modular addition operations and one-input lookup tables is estimated as , where k equals the number of used moduli. The time complexity is modular clock cycles. In pipeline mode, the throughput rate of the proposed algorithm is one reverse conversion in one modular clock cycle.     

N=2^t点DFT的快速卷积算法

从所周知,循环卷积和离散富里叶变换(DFT)可以互相计算,只要得到其中一个的快速算法就可导出另一个的快速算法。循环卷积目前已有乘法量为O(N)的最佳算法(特别是当N较小时),为此关键是如何将DFT转化为循环卷积,当DFT的长度N=p(p为素数),Rader利用有限域GF(p)的乘法群是循环群就成功地将p点DFT转化为Q(p)(F(p)为户的Euler函数)点循环卷积;当N=p~e时,由于商环Z/(p~e)存在F(p~c)阶元素,人们也成功地将p~c点DFT转化为P(p~(c-1))一系列循环卷积,即一个y(p~c)点循环卷积,二个P(p~(c-1))点     

非等距三次样条(Ⅰ)型插值函数余项渐近展开

摘要本文利用基样条插值方法,给出非等距I型三次样条插值误差的余项渐近展开式,推广了文献[1]中的结果。     

带约束条件和多余参数的线性模型的比较

对于带约束条件和多余参数的两个线性模型ｅ１＝Ｌ（Ｘ１β＋Ｚ１γ,Ｖ１,Ｌ１）和ｄ２＝Ｌ（Ｘ２β＋Ｚ２δ,Ｖ２,Ｌ２）,其中Ｖ１和Ｖ２是已知对称的正定矩阵,γ和δ是多余参数,Ｌ１和Ｌ２是已知的约束矩阵,文中给出了一种新的比较准则,并得到了几个充要条件。     

Independence of vectors in codes over rings

We study codes over Frobenius rings. We describe Frobenius rings via an isomorphism to the product of local Frobenius rings and use this decomposition to describe an analog of linear independence. Special attention is given to codes over principal ideal rings and a basis for codes over principal ideal rings is defined. We prove that a basis exists for any code over a principal ideal ring and that any two basis have the same number of vectors. Hongwei Liu is supported by the National Natural Science Foundation of China (10571067).     

Quantum Secret Sharing Based on Chinese Remainder Theorem

A novel quantum secret sharing (QSS) scheme is proposed on the basis of Chinese Remainder Theorem (CRT). In the scheme, the classical messages are mapped to secret sequences according to CRT equations, and distributed to different receivers by different dimensional superdense-coding respectively. CRT's secret sharing function,together with high-dimensional superdense-coding, provide convenience, security, and large capability quantum channel forsecret distribution and recovering. Analysis shows the security of the scheme.     

Some Solved and Unsolved Remainder Equations

The remainder set A?B of a set of sentences A modulo a set of sentences B is the set of all maximal subsets of A not implying any element of B. A remainder equation is an expression containing remainder sets, such as {A} = B?X, in which at least one set is unknown. Solutions to some classes of remainder equations are reported, and some unsolved problems are listed.     

A quantitative Sobolev inequality in BV

A quantitative version of the standard Sobolev inequality, with sharp constant, for functions u in W1,1(Rn) (or BV(Rn)) is established in terms of a distance of u from the manifold of all multiples of characteristic functions of balls. Inequalities involving non-Euclidean norms of the gradient are discussed as well.     

Finding -strong pseudoprimes

Let be odd primes and . Put

Then we call the kernel, the triple the signature, and the height of , respectively. We call a -number if it is a Carmichael number with each prime factor . If is a -number and a strong pseudoprime to the bases for , we call a -spsp . Since -numbers have probability of error (the upper bound of that for the Rabin-Miller test), they often serve as the exact values or upper bounds of (the smallest strong pseudoprime to all the first prime bases). If we know the exact value of , we will have, for integers , a deterministic efficient primality testing algorithm which is easy to implement.

In this paper, we first describe an algorithm for finding -spsp(2)'s, to a given limit, with heights bounded. There are in total -spsp's with heights . We then give an overview of the 21978 - spsp(2)'s and tabulate of them, which are -spsp's to the first prime bases up to ; three numbers are spsp's to the first 11 prime bases up to 31. No -spsp's to the first prime bases with heights were found. We conjecture that there exist no -spsp's to the first prime bases with heights and so that

which was found by the author in an earlier paper. We give reasons to support the conjecture. The main idea of our method for finding those -spsp's is that we loop on candidates of signatures and kernels with heights bounded, subject those candidates of -spsp's and their prime factors to Miller's tests, and obtain the desired numbers. At last we speed our algorithm for finding larger -spsp's, say up to , with a given signature to more prime bases. Comparisons of effectiveness with Arnault's and our previous methods for finding -strong pseudoprimes to the first several prime bases are given.