On RSA moduli with almost half of the bits prescribed

We show that using character sum estimates due to H. Iwaniec leads to an improvement of recent results about the distribution and finding RSA moduli M=pl, where p and l are primes, with prescribed bit patterns. We are now able to specify about n bits instead of about n/2 bits as in the previous work. We also show that the same result of H. Iwaniec can be used to obtain an unconditional version of a combinatorial result of W. de Launey and D. Gordon that was originally derived under the Extended Riemann Hypothesis.     

On the Number of Sparse RSA Exponents

An RSA modulus is a product M=pl of two primes p and l. We show that for almost all RSA moduli M, the number of sparse exponents e (which allow for fast RSA encryption) with the property that gcd(e,?(M))=1 (hence RSA decryption can also be performed) is very close to the expected value.     

合数模上的伪随机二进制数列

设m为"RSA"类型的模,即m为两个大小差不多的素数的乘积:m=pqp,q为素数,p相似文献   

云计算在RSA密码体制分析中的应用

RSA是著名的公钥密码体制之一,其安全性是基于大整数因子分解困难性假设的,求解RSA问题的最直接方法是分解RSA的模数.由于云计算的大规模分布式计算能力,一些使用分布式计算模型MapReduce的大整数分解手段已经实现,针对大整数因子分解的问题,提出了给定范围内搜索因子的新方法,并对相应的实验数据和结果进行了分析.结果表明,在云中的分布式计算的运行时间远小于单台机器.     

On some congruence with application to exponential sums

We will study the solution of a congruence,x ≡g ^1/2)ωg(2 ⁿ ) mod 2 ⁿ , depending on the integersg andn, where ω _g (2 ⁿ ) denotes the order ofg modulo 2 ⁿ . Moreover, we introduce an application of the above result to the study of an estimation of exponential sums.     

On the Use of RSA as a Secret Key Cryptosystem

One fundamental difference between the use of symmetric and publickey cryptosystems is that the former requires trust between sender and receiver. Typically they will share a secret key and neitherhas any protection from the other. However, many users are nowfinding that they want keys to be used for 'one purpose only'and are relying on hardware functionality to introduce the conceptof unidirectional keys for symmetric algorithms. (So, for instance,the hardware functionality might ensure that a key used for encryptingmessages from user A to user B cannot be used for encrypting messages in the opposite direction.) For public key systems this concept of unidirectional keys is automatically satisfied. However,when the encrypting key is made public, the exposure of this key means that the deciphering key is only safe from compromise when the keys are very large. If, on the other hand, both keys were kept secret then it might be possible to use much smallerkeys. In this paper we investigate ways of using the primitives of an RSA public key cryptosystem in a symmetric key 'setting'i.e. where neither key is made public.     

An approximate expression related with RSA fixed points

Let T=T(n,e,a)be the number of fixed points of RSA(n,e)that are co-prime with n=pq,and A,B be sets of prime numbers in (1,x)and(1,y) respectively.An estimation on the mean-value M(A,B,e,a)=1/(#A)(#B)∑p∈A,q∈B,(p.q)=1 logT(pq,e,a)is given.     

关于(a,a,b)类型的三维除数问题

本文研究（ａ,ａ,ｂ）类型的三维除数问题,通过把此问题和熟知的Ｄｉｒｉｃｈｌｅｔ问题相联系并估计余项的新形式,我们得到了更好的结果。     

一个二元丢番图不等式

本文证明了如果1相似文献   

一个素变数丢番图不等式

本文证明了如果1相似文献   

On the Construction of Affine Extractors

In this paper, we address the problem of explicit construction of so-called ‘affine extractors’ of δ-entropy ratio, when δ ≤ 1/2 (for δ > 1/2, there is a well-known and easy example based on the Hadamard function). We first give examples for δ slightly below 1/2 and produce then a construction for arbitrary given δ > 0. All these examples are again of a simple algebraic nature. The mathematics involved includes recent developments in the sum-product theory in finite fields and certain new bounds on multilinear exponential sums. Supported in part by NSF grant DMS 0322370. Submitted: May 2005 Accepted: February 2006     

短区间的并集中整数及其m次幂的差的均值分布

本文研究了短区间的并集中整数及其m次幂的差的均值分布问题,给出了渐近公式.具体来说,设P是奇素数,1≤H≤p,实数δ满足0 δ≤1,整数m≥2.设I~((j))是(0,p)的互不相交的子区间,1≤j≤J,满足H/2≤|I~((j))|≤H,以及(y)_p表示y在模p下的非负最小剩余.定义I=∪_(j=1)~JI~((j)),并设X是模p的Dirichlet非主特征.证明了Σ x∈1 |x-(x~m)p|δp 1=1/p∫_0~([δp]) (Σ x∈1 x≤p-1-t 1+Σ x∈1 x≥t=1 1)dt+O(mJ~(1/2)P~(1/2)log~2 plog H),以及Σ x∈1 |x-(x~m)p|δp X(x)mJ~(1/2)P~(1/2)log~2 plog H.     

On Waring's Problem for Cubes and Smooth Weyl Sums

Non-trivial estimates for fractional moments of smooth cubicWeyl sums are developed. Complemented by bounds for such sumsof use on both the major and minor arcs in a Hardy-Littlewooddissection, these estimates are applied to derive an upper boundfor the sth moment of the smooth cubic Weyl sum of the expectedorder of magnitude as soon as s> 7.691. Related argumentsdemonstrate that all large integers n are represented as thesum of eight cubes of natural numbers, all of whose prime divisorsare at most exp (c(log nlog log n)^1/2}, for a suitable positivenumber c. This conclusion improves a previous result of G. Harcosin which nine cubes are required. 1991 Mathematics Subject Classification:11P05, 11L15, 11P55.     

A Comparative Study on Dynamic and Static Sparsity Patterns in Parallel Sparse Approximate Inverse Preconditioning

Sparse approximate inverse (SAI) techniques have recently emerged as a new class of parallel preconditioning techniques for solving large sparse linear systems on high performance computers. The choice of the sparsity pattern of the SAI matrix is probably the most important step in constructing an SAI preconditioner. Both dynamic and static sparsity pattern selection approaches have been proposed by researchers. Through a few numerical experiments, we conduct a comparable study on the properties and performance of the SAI preconditioners using the different sparsity patterns for solving some sparse linear systems. This revised version was published online in July 2006 with corrections to the Cover Date.     

On the Lower Bound of the Divisibility of Exponential Sums in Binomial Case

In this article,we analyze the lower bound of the divisibility of families of exponential sums for binomials over prime field.An upper bound is given for the lower bound,and,it is related to permutation polynomials.     

Exponential sum estimates over subgroups and almost subgroups of \mathbb{Z}_{Q}^{*} , where Q is composite with few prime factors

In this paper we extend the exponential sum results from [BK] and [BGK] for prime moduli to composite moduli q involving a bounded number of prime factors. In particular, we obtain nontrivial bounds on the exponential sums associated to multiplicative subgroups H of size q^δ, for any given δ > 0. The method consists in first establishing a ‘sumproduct theorem’ for general subsets A of . If q is prime, the statement, proven in [BKT], expresses simply that either the sum-set A + A or the product-set A.A is significantly larger than A, unless |A| is near q. For composite q, the presence of nontrivial subrings requires a more complicated dichotomy, which is established here. With this sum-product theorem at hand, the methods from [BGK] may then be adapted to the present context with composite moduli. They rely essentially on harmonic analysis and graph-theoretical results such as Gowers’ quantitative version of the Balog–Szemeredi theorem. As a corollary, we get nontrivial bounds for the ‘Heilbronn-type’ exponential sums when q = p^r (p prime) for all r. Only the case r = 2 has been treated earlier in works of Heath-Brown and Heath-Brown and Konyagin (using Stepanov’s method). We also get exponential sum estimates for (possibly incomplete) sums involving exponential functions, as considered for instance in [KS]. Submitted: October 2004 Revision: June 2005 Accepted: August 2005     

On the Mean Square of the Error Terms Corresponding to Exponential Sums Involving the Ideal Counting Function

In this paper we consider the asymptotic behaviour of the error term Q(x;h/q), which is defined by (1.2). In particular, we derive a certain lower bound estimate of this function when h, k and q are fixed integers, and study the non-trivial upper bound estimates of the mean value of Q(x;h/q).     

关于指数型丢番图方程的整数解

本文简要地介绍了有关Ｓ－单位方程、Ｒａｍａｎｕｊａｎ－Ｎａｇｅｌｌ方程、Ｔｈｕｅ－Ｍａｈｌｅｒ方程、ＬｅＶｅｑｕｅ方程、Ｃａｔａｌａｎ方程、Ｐｉｌｌａｉ方程等指数型丢番图方程整数解的最新结果。这些结果大多是用Ｔｈｕｅ－Ｓｉｅｇｌｅ－Ｒｏｔｈ－Ｓｃｈｍｉｄｔ方法和Ｇｅｌ’ｆｏｎｄ－Ｂａｋｅｒ方法得到的。     

关于三项纯指数Diophantine方程ax+by=cz

设a、b、c是互素的正整数.本文证明了:当a b2l-1=c2,b≡5(mod 12),c是适合c≡-1(mod b2l)的奇素数,其中l是正整数时,方程ax by=cz仅有正整数解(x,y,z)=(1,2l-1,2).