检索结果-内蒙古大学图书馆

On Deterministic Reduction of factoring Integers to Computing the Exponents of Elements in Modular Group

FUNDAMENTA INFORMATICAE 2017年第3期152卷 289-295页

作者： Pomykala, Jacek Warsaw Univ Inst Math Banacha 2 PL-02097 Warsaw Poland

In the paper we prove that all but at most x/A(x) positive integers n <= x can be completely factored in deterministic polynomial time C(x), querying the prime decomposition exponent oracle at most D(x) times. The ... 详细信息

关键词： Brun-Titchmarsh inequality factoring algorithms Z(n)(*)-generating sets Dirichlet characters smooth numbers Discrete Logarithm Problem for Composite Numbers

来源：评论

学校读者我要写书评

暂无评论

Large Sieve, Miller-Rabin Compositeness Witnesses and Integer factoring Problem

引用

FUNDAMENTA INFORMATICAE 2017年第2期156卷 179-185页

作者： Durnoga, Konrad Pomykala, Jacek Univ Warsaw Inst Informat Banacha 2 PL-02097 Warsaw Poland

G. Miller in his seminal paper from the mid 1970s has proven that the problem of factoring integers reduces to computing Euler's totient function phi under the Extended Riemann Hypothesis. We show, unconditionally... 详细信息

关键词： large sieve factoring algorithms Z*(n)-generating sets Dirichlet characters smooth numbers Discrete Logarithm Problem for Composite Numbers

来源：评论

学校读者我要写书评

暂无评论

A PIPELINE ARCHITECTURE FOR factoring LARGE INTEGERS WITH THE QUADRATIC SIEVE ALGORITHM

引用

SIAM JOURNAL ON COMPUTING 1988年第2期17卷 387-403页

作者： POMERANCE, C SMITH, JW TULER, R UNIV GEORGIA DEPT COMP SCIATHENSGA 30602

We describe the quadratic sieve factoring algorithm and a pipeline architecture on which it could be efficiently implemented. Such a device would be of moderate cost to build and would be able to factor 100-digit numbers in less than a month. This represents an order of magnitude speed-up over current implementations on supercomputers. Using a distributed network of many such devices, it is predicted much larger numbers could be practically factored.

关键词： 11Y05 68M05 pipeline architecture factoring algorithms quadratic sieve

来源：评论

学校读者我要写书评

暂无评论

factoring NUMBERS IN O(LOG N) ARITHMETIC STEPS

引用

INFORMATION PROCESSING LETTERS 1979年第1期8卷 28-31页

作者： SHAMIR, A Department of Mathematics Massachusetts Institute of Technology Cambridge MA 02139 U.S.A.

来源：评论

学校读者我要写书评

暂无评论

Small Generating Sets and DLPC Problem

引用

FUNDAMENTA INFORMATICAE 2016年第2期145卷 143-150页

作者： Pomykala, Jacek Warsaw Univ Inst Math Banacha 2 PL-02097 Warsaw Poland

In the paper we investigate the set of odd, squarefree positive integers n that can be factored completely in polynomial time O (log(6+epsilon) n), given the prime decomposition of orders or d(n)b for b <= log(eta) n, (eta > 2), which is closely related to DLPC problem. We prove that the number of n <= x that may not be factored in deterministic time O (log(6+epsilon) n), is at most (eta - 2)(-1) x(log x)(-c(eta-2)), for some c > 0 and arbitrary epsilon > 0.

关键词： factoring algorithms Z(n)*-generating sets Dirichlet characters smooth numbers discrete logarithm problem for composite numbers large sieve estimates

来源：评论

学校读者我要写书评

暂无评论

The Most Frequent Values of the Largest Prime Divisor Function

引用

EXPERIMENTAL MATHEMATICS 2017年第2期26卷 210-224页

作者： Mcnew, Nathan Towson Univ Dept Math 8000 York Rd Towson MD 21252 USA

We consider the distribution of the largest prime divisor of the integers in the interval [2, x] and investigate in particular the mode of this distribution, the prime number(s) which show up most often in this list. In addition to giving an asymptotic formula for this mode as x tends to infinity, we look at the set of those prime numbers which, for some value of x, occur most frequently as the largest prime divisor of the integers in the interval [2, x]. We find that many prime numbers never have this property. We compare the set of "popular primes," those primes which are at some point the mode, to other interesting subsets of the prime numbers. Finally, we apply the techniques developed to a similar problem which arises in the analysis of factoring algorithms.

关键词： largest prime divisor smooth numbers factoring algorithms

来源：评论

学校读者我要写书评

暂无评论

Jacobians of Hyperelliptic Curves over Zn and Factorization of n

引用

FUNDAMENTA INFORMATICAE 2019年第4期169卷 275-283页

作者： Drylo, Robert Pomykala, Jacek Warsaw Sch Econ Aleja Niepodleglosci 162 PL-02554 Warsaw Poland Fac Math Informat & Mech Ul Banacha 2 PL-02097 Warsaw Poland

E. Bach showed that factorization of an integer n can be reduced in probabilistic polynomial time to the problem of computing exponents of elements in Z(n)* (in particular the group order of Z(n)*). It is also known that factorization of square-free integer n can be reduced to the problem of computing the group order of an elliptic curve E/Z(n). In this paper we describe the analogous reduction for computing the orders of Jacobians over Z(n) of hyperelliptic curves C over Z(n) using the Mumford representation of divisor classes and Cantor's algorithm for addition. These reductions are based on the group structure of the Jacobian. We also propose other reduction of factorization to the problem of determining the number of points vertical bar C(Z(n))vertical bar, which makes use of elementary properties of twists of hyperelliptic curves.

关键词： factoring algorithms abelian varieties Jacobians hyperelliptic curves

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：