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

Seventeen lines and one-hundred-and-one points

THEORETICAL COMPUTER SCIENCE 2004年第2-3期321卷 415-421页

作者： Woeginger, GJ Univ Twente Dept Math NL-7500 AE Enschede Netherlands

We investigate a curious problem from additive number theory: Given two positive integers S and Q, does there exist a sequence of positive integers that add up to S and whose squares add up to Q? We show that this problem can be solved in time polynomially bounded in the logarithms of S and Q. As a consequence, also the following question can be answered in polynomial time: For given numbers n and m, do there exist n lines in the Euclidean plane with exactly m points of intersection? (C) 2004 Published by Elsevier B.V.

关键词： algorithmic number theory geometry polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer

引用

SIAM REVIEW 1999年第2期41卷 303-332页

作者： Shor, PW AT&T Bell Labs Res Florham Pk NJ 07932 USA

A digital computer is generally believed to be an efficient universal computing device;that is, it is believed to be able to simulate any physical computing device with an increase in computation time by at most a polynomial factor. This may not be true when quantum mechanics is taken into consideration. This paper considers factoring integers and finding discrete logarithms, two problems that are generally thought to be hard on classical computers and that have been used as the basis of several proposed cryptosystems. Efficient randomized algorithms are given for these two problems on a hypothetical quantum computer. These algorithms take a number of steps polynomial in the input size, for example, the number of digits of the integer to be factored.

关键词： algorithmic number theory prime factorization discrete logarithms Church's thesis quantum computers foundations of quantum mechanics spin systems Fourier transforms

来源：评论

学校读者我要写书评

暂无评论

Abelian lifts of polynomials

引用

JOURNAL OF number theory 2023年 246卷 265-278页

作者： Wong, Siman Univ Massachusetts Dept Math & Stat Amherst MA 01003 USA

Let p be a prime, and let f is an element of Z[x] be a non-constant polynomial whose leading coefficient is prime to p and that f has no repeated root modulo p. Suppose the mod -p irreducible factors off all have the same degree. Then there are infinitely many Abelian extensions of number fields L/K such that O-L/POL similar or equal to(Z/p)[x]/f, where O-L denotes the ring of integers of L and p subset of O-K is a maximal ideal with O-K/POK similar or equal to Z/p. Moreover, under the generalized Riemann hypothesis for the Dedekind zeta functions of number fields, for fixed deg(f) we can construct Abelian lifts in polynomial time in log p. This confirms in a stronger form a question raised by Mihailescu and Vuletescu concerning polynomial cyclic algebras. The proofs make use of a weak form of Artin's conjecture on primitive roots and polynomial time polynomial factoring algorithms over number fields.(c) 2022 Elsevier Inc. All rights reserved.

关键词： Abelian lifts algorithmic number theory Artin?s conjecture Polynomial factorization Primitive roots

来源：评论

学校读者我要写书评

暂无评论

How to compute the coefficients of the elliptic modular function j(z)

引用

EXPERIMENTAL MATHEMATICS 2003年第1期12卷 115-121页

作者： Baier, H Köhler, G TH Darmstadt Darmstadt Ctr IT Secur D-64283 Darmstadt Germany Univ Wurzburg Dept Math D-97074 Wurzburg Germany

We discuss various methods to compute the Fourier coefficients of the elliptic modular function j(z). We present run times to compute the coefficients in practice. If possible, we discuss the theoretical complexity of the corresponding method, too. We conclude that, in practice, an approach due to Kaneko and Zagier turns out to be most efficient.

关键词： algorithmic number theory elliptic modular function j Fourier coefficients Fourier series

来源：评论

学校读者我要写书评

暂无评论

Computing generators of the tame kernel of a global function field

引用

JOURNAL OF SYMBOLIC COMPUTATION 2006年第9期41卷 964-979页

作者： Weng, Annegret Univ Mainz Fachbereich Math D-55128 Mainz Germany

The group K-2 of a curve C over a finite field is equal to the tame kernel of the corresponding function field. We describe two algorithms for computing generators of the tame kernel of a global function field. The first algorithm uses the transfer map and the fact that the l-torsion can easily be described if the ground field contains the lth roots of unity. The second method is inspired by an algorithm of Belabas and Gangl for computing generators of K2 of the ring of integers in a number field. We finally give the generators of the tame kernel for some elliptic function fields. (c) 2006 Elsevier Ltd. All rights reserved.

关键词： algorithmic number theory K-theory global function fields

来源：评论

学校读者我要写书评

暂无评论

Approximating the number of integers free of large prime factors

引用

MATHEMATICS OF COMPUTATION 1997年第220期66卷 1729-1741页

作者： Hunter, S Sorenson, J Department of Mathematics and Computer Science Butler University

Define psi(x, y) to be the number of positive integers n less than or equal to x such that n has no prime divisor larger than y. We present a simple algorithm that approximates psi(x,y) in O(y{log log x/log y + 1/log log y}) floating point operations. This algorithm is based directly on a theorem of Hildebrand and Tenenbaum. We also present data which indicate that this algorithm is more accurate in practice than other known approximations, including the well-known approximation psi(x, y) approximate to xp(log x/log y), where p(u) is Dickman's function.

关键词： Psixyology Integer factoring analytic number theory algorithmic number theory computational number theory.

来源：评论

学校读者我要写书评

暂无评论

Computation of Euclidean minima in totally definite quaternion fields

引用

INTERNATIONAL JOURNAL OF number theory 2019年第1期15卷 43-66页

作者： Cerri, Jean-Paul Lezowski, Pierre Univ Bordeaux IMB 351 Cours Liberat F-33400 Talence France Univ Clermont Auvergne Lab Math Blaise Pascal F-63000 Clermont Ferrand France

We describe an algorithm that allows to compute the Euclidean minimum (for the norm form) of any order of a totally definite quaternion field over a number field K of degree strictly greater than 1. Our approach is a generalization of the previous work dealing with number fields. The algorithm was practically implemented when K has degree 2.

关键词： Quaternion algebras norm-Euclidean orders norm-Euclidean minimum algorithmic number theory

来源：评论

学校读者我要写书评

暂无评论

ON THE MINIMAL number OF SMALL ELEMENTS GENERATING FINITE PRIME FIELDS

引用

BULLETIN OF THE AUSTRALIAN MATHEMATICAL SOCIETY 2017年第2期96卷 177-184页

作者： Munsch, Marc 5010 Inst Anal & Zahlentheorie Steyrergasse 30 A-8010 Graz Austria

In this note, we give an upper bound for the number of elements from the interval [1, p(1/4 root e+is an element of)]necessary to generate the finite field F-p(*) with p an odd prime. The general result depends on the... 详细信息

关键词： finite field generating set primitive root sieve theory character sum algorithmic number theory

来源：评论

学校读者我要写书评

暂无评论

Collatz Conjecture for 2¹⁰⁰⁰⁰⁰-1 is True - Algorithms for Verifying Extremely Large numbers 4

Collatz Conjecture for 2<SUP>100000</SUP>-1 is True - Algori...

引用

IEEE SmartWorld, Ubiquitous Intelligence & Computing, Advanced & Trusted Computing, Scalable Computing & Communications, Cloud & Big Data Computing, Internet of People and Smart City Innovation (SmartWorld/SCALCOM/UIC/ATC/CBDCom/IOP/SCI)

作者： Ren, Wei Li, Simin Xiao, Ruiyang Bi, Wei China Univ Geosci Hubei Key Lab Intelligent Geoinformat Proc Sch Comp Sci Wuhan 430074 Peoples R China Guizhou Univ Guizhou Prov Key Lab Publ Big Data Guizhou Peoples R China China Univ Geosci Sch Comp Sci Wuhan 430074 Peoples R China China Univ Geosci Sch Comp Sci Sch Math & Phys Wuhan 430074 Peoples R China SeeleTech Corp San Francisco CA 94107 USA

ISBN: (纸本)9781538693803

Collatz conjecture (or 3x+1 problem) has been explored for about 80 years. By now the largest number that has been verified for Collatz conjecture is about 60 bits. In this paper, we propose new algorithms that can verify much greater numbers than known algorithms, i.e., about 100000 bits (30000 digits) on whether they can return 1 after 3*x+1 and x/2 computations. The proposed algorithms change numerical computation to bit computation (or logical computation), and change inner memory data representation to hard disk file manipulation. We make it possible to verify extremely large numbers without concerning computer memory upper-bound. The largest number verified for Collatz conjecture until now in the world is 2(100000) - 1, and this magnitude of extremely large numbers has never been verified. We discovered that this number can return to 1 after 481603 times of 3*x+1 computation, and 863323 times of x/2 computation. At last, we stress that some open problems may be used for the green mining in blockchain-based cryptocurrencies, e.g., BTC. We discuss the applicability of Collatz conjecture for the Proof of Work in Blockchain.

关键词： Collatz Conjecture 3x+1 Problem Computational Algebra algorithmic number theory Numerical Algorithm

来源：评论

学校读者我要写书评

暂无评论

Primality proving using elliptic curves with complex multiplication by imaginary quadratic fields of class number three

引用

FINITE FIELDS AND THEIR APPLICATIONS 2024年 99卷

作者： Onuki, Hiroshi Univ Tokyo Dept Math Informat 7-3-1 HongoBunkyo Ku Tokyo 1138656 Japan

In 2015, Abatzoglou, Silverberg, Sutherland, and Wong presented a framework for primality proving algorithms for special sequences of integers using an elliptic curve with complex multiplication. They applied their framework to obtain algorithms for elliptic curves with complex multiplication by imaginary quadratic field of class numbers one and two, but, they were not able to obtain primality proving algorithms in cases of higher class number. In this paper, we present a method to apply their framework to imaginary quadratic fields of class number three. In particular, our method provides a more efficient primality proving algorithm for special sequences of integers than the existing algorithms by using an imaginary quadratic field of class number three in which 2 splits. As an application, , we give two special peci al sequences of integers derived from Q( root-23) and Q( root-31), which are all the imaginary quadratic fields of class number three in which 2 splits. Finally, we give a computational result for the primality of these sequences. (c) 2024 Elsevier Inc. All rights are reserved, including those for text and data mining, AI training, and similar technologies.

关键词： algorithmic number theory Primality proving Elliptic curves Complex multiplication

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：