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

Highly durable and energy-efficient probabilistic bits based on h-BN/SnS2 interface for integer factorization

INFOMAT 2025年第0期

作者： Han, Joon-Kyu Park, Jun-Young Rehman, Shania Khan, Muhammad Farooq Kim, Moon-Seok Kim, Sungho Seoul Natl Univ Dept Mat Sci & Engn Seoul 08826 South Korea Seoul Natl Univ Interuniv Semicond Res Ctr Seoul South Korea Sejong Univ Dept Semicond & Syst Engn Seoul South Korea Sejong Univ Dept Elect Engn Seoul South Korea Hanbat Natl Univ Dept Semicond Syst Engn Daejeon 31538 South Korea Ewha Womans Univ Div Elect & Semicond Engn Seoul 03760 South Korea

As social networks and related data processes have grown exponentially in complexity, the efficient resolution of combinatorial optimization problems has become increasingly crucial. Recent advancements in probabilistic computing approaches have demonstrated significant potential for addressing these problems more efficiently than conventional deterministic computing methods. In this study, we demonstrate a highly durable probabilistic bit (p-bit) device utilizing two-dimensional materials, specifically hexagonal boron nitride (h-BN) and tin disulfide (SnS2 ) nanosheets. By leveraging the inherently stochastic nature of electron trapping and detrapping at the h-BN/SnS2 interface, the device achieves durable probabilistic fluctuations over 108 cycles with minimal energy consumption. To mitigate the static power consumption, we integrated an active switch in series with a p-bit device, replacing conventional resistors. Furthermore, employing the pulse width as the control variable for probabilistic switching significantly enhances noise immunity. We demonstrate the practical application of the proposed p-bit device in implementing invertible Boolean logic gates and subsequent integer factorization, highlighting its potential for solving complex combinatorial optimization problems and extending its applicability to real-world scenarios such as cryptographic systems. image

关键词： integer factorization interface trap invertible logic gate probabilistic bit probabilistic computing

来源：评论

学校读者我要写书评

暂无评论

integer factorization with Stochastic Spiking in Percolating Networks of Nanoparticles

引用

ACS NANO 2024年第41期18卷 28060-28069页

作者： Studholme, Sofie J. Brown, Simon A. Univ Canterbury MacDiarmid Inst Adv Mat & Nanotechnol Sch Phys & Chem Sci Christchurch 8140 New Zealand

As growth in global demand for computing power continues to outpace ongoing improvements in transistor-based hardware, novel computing solutions are required. One promising approach employs stochastic nanoscale devices to accelerate probabilistic computing algorithms. Percolating Networks of Nanoparticles (PNNs) exhibit stochastic spiking, which is of particular interest as it meets criteria for criticality which is associated with a range of computational advantages. Here, we show several ways in which spiking PNNs can be used as the core stochastic components of coupled networks that allow successful factorization of integers up to 945. We demonstrate asynchronous operation and show that a single device is sufficient to solve all factorization tasks and to generate multiple solutions simultaneously.

关键词： nanoparticle networks integer factorization probabilistic computing optimization spiking

来源：评论

学校读者我要写书评

暂无评论

integer factorization: Why Two-Item Joint Replenishment Is Hard

引用

OPERATIONS RESEARCH 2024年第3期72卷 1192-1202页

作者： Schulz, Andreas S. Telha, Claudio Tech Univ Munich Dept Math D-80333 Munich Germany Tech Univ Munich Sch Management D-80333 Munich Germany Univ Los Andes Fac Ingn & Ciencias Aplicadas Santiago 9000000 Chile

Distribution networks with periodically repeating events often hold great promise to exploit economies of scale. Joint replenishment problems are fundamental in inventory management, manufacturing, and logistics and capture these effects. However, finding an efficient algorithm that optimally solves these models or showing that none may exist have long been open regardless of whether empty joint orders are possible or not. In either case, we show that finding optimal solutions to joint replenishment instances with just two items is at least as difficult as integer factorization. To the best of the authors' knowledge, this is the first time integer factorization is used to explain the computational hardness of any optimization problem. We can even prove that the two-item joint replenishment problem with possibly empty joint-ordering points is NP-complete under randomized reductions. This implies that even quantum computers may not be able to solve it efficiently. By relating the computational complexity of joint replenishment to cryptography, prime decomposition, and other aspects of prime numbers, a similar approach may help to establish the (integer factorization) hardness of additional periodic problems in supply chain management and beyond, whose computational complexity has not been resolved yet.

关键词： computational complexity integer factorization joint replenishment

来源：评论

学校读者我要写书评

暂无评论

integer factorization with Compositional Distributed Representations 2022

Integer Factorization with Compositional Distributed Represe...

引用

Annual Neuro-Inspired Computational Elements Conference (NICE)

作者： Kleyko, Denis Bybee, Connor Kymn, Christopher Olshausen, Bruno Khosrowshahi, Amir Nikonov, Dmitri E. Sommer, Friedrich T. Frady, Paxon Univ Calif Berkeley Berkeley CA 94720 USA Res Inst Sweden Kista Sweden Intel Technol Dev Santa Clara CA USA Intel Components Res Hillsboro OR USA Intel Labs Santa Clara CA USA

ISBN: (纸本)9781450395595

In this paper, we present an approach to integer factorization using distributed representations formed with Vector Symbolic Architectures. The approach formulates integer factorization in a manner such that it can be solved using neural networks and potentially implemented on parallel neuromorphic hardware. We introduce a method for encoding numbers in distributed vector spaces and explain how the resonator network can solve the integer factorization problem. We evaluate the approach on factorization of semiprimes by measuring the factorization accuracy versus the scale of the problem. We also demonstrate how the proposed approach generalizes beyond the factorization of semiprimes;in principle, it can be used for factorization of any composite number. This work demonstrates how a well-known combinatorial search problem may be formulated and solved within the framework of Vector Symbolic Architectures, and it opens the door to solving similarly difficult problems in other domains.

关键词： Collective-State Computing Hyperdimensional Computing Vector Symbolic Architectures Resonator network Fractional Power Encoding integer factorization

来源：评论

学校读者我要写书评

暂无评论

Smooth Subsum Search A Heuristic for Practical integer factorization

引用

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 2024年第8期35卷 949-974页

作者： Hittmeir, Markus SBA Res Floragasse 7 A-1040 Vienna Austria

The two currently fastest general-purpose integer factorization algorithms are the Quadratic Sieve and the Number Field Sieve. Both techniques are used to find so-called smooth values of certain polynomials, i.e., values that factor completely over a set of small primes (the factor base). As the names of the methods suggest, a sieving procedure is used for the task of quickly identifying smooth values among the candidates in a certain range. While the Number Field Sieve is asymptotically faster, the Quadratic Sieve is still considered the most efficient factorization technique for numbers up to around 100 digits. In this paper, we challenge the Quadratic Sieve by presenting a novel approach based on representing smoothness candidates as sums that are always divisible by several of the primes in the factor base. The resulting values are generally smaller than those considered in the Quadratic Sieve, increasing the likelihood of them being smooth. Using the fastest implementations of the Self-initializing Quadratic Sieve in Python as benchmarks, a Python implementation of our approach runs consistently 5 to 7 times faster for numbers with 45-100 digits, and around 10 times faster for numbers with 30-40 digits. We discuss several avenues for further improvements and applications of the technique.

关键词： integer factorization smooth numbers

来源：评论

学校读者我要写书评

暂无评论

The Space Complexity Analysis in the General Number Field Sieve integer factorization

引用

THEORETICAL COMPUTER SCIENCE 2016年 630卷 76-94页

作者： Wang, Qi Fan, Xiubin Zang, Hongyan Wang, Yu Beijing Univ Sci & Technol Beijing 100083 Peoples R China State Key Lab Cryptol Beijing 100878 Peoples R China

The General Number Sieve is the most efficient algorithm for integer factorization. It consists of polynomial selection, sieving, solving equations and finding square roots. Root lifting of polynomial is discussed in this paper. The p-adic evaluation provided by each root and the expected p-value are also given. Then we gain the space complexity of sieving and building equations over the ring Z/2Z. (C) 2016 Elsevier B.V. All rights reserved.

关键词： General Number Field Sieve integer factorization Mathematical expectation p-adic evaluation Computational complexity Space complexity

来源：评论

学校读者我要写书评

暂无评论

RETRACTED: An integrated parallel GNFS algorithm for integer factorization based on Linbox Montgomery block Lanczos method over GF(2) (Retracted article. See vol. 20, pg. 1, 2009)

引用

COMPUTERS & MATHEMATICS WITH APPLICATIONS 2010年第2期60卷 338-346页

作者： Yang, Laurence T. Xu, Li Yeo, Sang-Soo Hussain, Sajid St Francis Xavier Univ Dept Comp Sci Antigonish NS Canada Mokwon Univ Div Comp Engn Taejon South Korea Acadia Univ Jodrey Sch Comp Sci Wolfville NS B0P 1X0 Canada

integer factorization is known to be one of the most important and useful methods in number theory and arithmetic. It also has a very close relationship to some algorithms in cryptography such as RSA algorithm. The RSA cryptosystem is one of the most popular and attractive public-key cryptosystems in the world today. Its security is based on the difficulty of integer factorization. Solving a large and sparse linear system over GF(2) is one of the most time consuming steps in most modern integer factorization algorithms including the fastest one, GNFS algorithm. The Montgomery block Lanczos method from Linbox [13] is for solving large and sparse linear systems over finite fields and it can be integrated into the general number field sieve (GNFS) algorithm which is the best known algorithm for factoring large integers over 110 digits. This paper will present an improved Montgomery block Lanczos method integrated with parallel GNFS algorithm. The experimental results show that the improved Montgomery block Lanczos method has a better performance compared with the original method. It can find more solutions or dependencies than the original method with less time complexities. Implementation details and experimental results are provided in this paper as well. (C) 2010 Elsevier Ltd. All rights reserved.

关键词： integer factorization Public-key RSA algorithm GNFS algorithm Linear system over GF(2) Lanczos method Parallelization High performance computing

来源：评论

学校读者我要写书评

暂无评论

Representing the integer factorization Problem Using Ordered Binary Decision Diagrams

引用

THEORY OF COMPUTING SYSTEMS 2023年第6期67卷 1307-1332页

作者： Brown, David E. Skidmore, David Utah State Univ Dept Math 3900 Old Main Hill Logan UT 84322 USA

A method is given to reduce the problem of finding a nontrivial factorization of a positive integer alpha, greater than one, to the problem of finding a solution to a system of Boolean equations, that is, a system of equations such that each equation is of the form f=g where f and g are Boolean functions, meaning {0,1}-valued functions in zero or more Boolean ({0,1}-valued) variables. Our system is obtained by applying a sequence of reductions to an initial system of equations of the form {fi((x) over right arrow,(y) over right arrow),=alpha i|i is an element of{0,,2n}} where for each i fi((x) over right arrow,(y) over right arrow)=fi(x0...,,xn,y0...,,yn) gives the coefficient of 2i in the binary expansion of (x0+2x1+...+2(n)xn)(y0+2y1+...+2nyn), alpha i gives the coefficient of 2i in the binary expansion of alpha, and xi and yi are {0,1}-valued variables. That is, the initial system represents a binary multiplier whose output bits have been set equal to the bits of alpha. It is shown that each Boolean function in our reduced system, that is, each Boolean function (g-h) mod2={0 double left right arrow g=h/1 double left right arrow g not equal h such that g=h is an equation in the reduced system, can be represented by a type of graph called an ordered binary decision diagram (OBDD) with an upper bound on its number of vertices of O(log2(alpha/log2(alpha))3. Previous work has shown that the initial system has at least one Boolean function with an OBDD representation with number of vertices exponential in log2 (alpha).

关键词： integer factorization Binary decision diagram Boolean satisfiability

来源：评论

学校读者我要写书评

暂无评论

Heuristic algorithm based on molecules optimizing their geometry in a crystal to solve the problem of integer factorization

引用

SOFT COMPUTING 2016年第9期20卷 3363-3371页

作者： Mishra, Mohit Chaturvedi, Utkarsh Shukla, K. K. Indian Inst Technol BHU Varanasi Uttar Pradesh India

integer factorization is a vital number theoretic problem finding frequent use in public key cryptography, and other areas like Fourier transforms. There has been growing interest among researchers in innovative alternative approaches to solving the problem by modeling some optimizing natural or biological behaviour in a form of an algorithm that can be used to solve the problem provided the problem can be represented as an optimization task. In this paper, we present a new model based on computational chemistry behind how molecules interact among each other to minimize their surface energy potential in a typical crystal. While this phenomenon itself is a research problem, it interestingly provides a new way of solving other problems like integer factorization which can be represented in different forms of discrete optimization task. However, we must note that the present methods based on such models are not scalable to the real-world scenario, and we present a brief discussion on this issue.

关键词： integer factorization Energy minimization Metaheuristics Optimization

来源：评论

学校读者我要写书评

暂无评论

Relation collection using Pollard special-qsieving to solve integer factorization and discrete logarithm problem

引用

JOURNAL OF SUPERCOMPUTING 2021年第3期77卷 2734-2769页

作者： Varshney, Shubham Charpe, Pankaj Padmavathy, R. Pal, S. K. Natl Inst Technol Warangal Andhra Pradesh India DRDO SAG New Delhi India

The strength of many security protocols lies on the computational intractability of the integer factorization and discrete logarithm problems. Currently, the best-known techniques employed are number field sieve (NFS) family of algorithms. They come under the class of sub-exponential time algorithms. This class of algorithms comprises of multiple steps. The relation collection (sieving step) is one of the computationally costly and highly memory-dependent phase of these algorithms. This paper discusses various ways to improve the efficiency of the relation collection phase by using parallelization techniques. Experiments have been carried out by using function field sieve, which is one of the NFS family algorithms, to show the computation efficiency of parallelization techniques along with the suitable sieving techniques and the key parameters. The result of our basic implementation is compared with the parallelized version of it. The result analysis depicts that the relation collection phase can be improved by using parallelization techniques up to fourfold.

关键词： integer factorization Discrete logarithm Number field sieve (NFS ) Function field sieve (FFS) Special-qlattice sieving Bucket sieving Line sieving

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：