Self-witnessing polynomial-time complexity and prime factorization

For a number of computational search problems, the existence of a polynomial-time algorithm for the problem implies that a polynomial-time algorithm for the problem is constructively known. Some instances of such self-witnessing polynomial-time complexity are presented. Our main result demonstrates this property for the problem of computing the prime factorization of a positive integer, based on a lemma which shows that a certificate for primality or compositeness can be constructed for a positive integer p in deterministic polynomial time given a complete factorization of p - 1.     

On the number of divisors of x2 + x + A

Let A be a positive or negative rational integer such that integers in the field of √1 ? 4A have unique prime factorization. An elementary criterion will be obtained for x² + x + A to be a prime number, where x is a positive integer. The criterion implies that for positive A the polynomial x² + x + A is prime for x = 0, 1,…, A ? 2.     

Generalized automorphs of the sum of four squares

A unique factorization theorem is given for 4 × 4 integral matrices T satisfying T′T = mI, m a positive integer.     

On Separation Index of Heegaard Splittings

§１．ＩｎｔｒｏｄｕｃｔｉｏｎＴｈｅｃｏｎｃｅｐｔｏｆｒｅｄｕｃｉｂｌｅＨｅｅｇａａｒｄｓｐｌｉｔｉｎｇｓｗａｓｆｉｒｓｔｄｅｖｅｌｏｐｅｄｂｙＨａｋｅｎ［１］．Ｉｔｓｒｅｌａ－ｔｉｏｎｔｏｔｈｅｃｏｒｒｅｓｐｏｎｄｉｎｇ３－ｍａｎｉｆｏｌｄｓｃｏｎ...     

关于调和数的一个结论

设n是大于1的正常数,并且设n=pα11p2α2…ptαt,其中pi为素数,i=1,2,…,t,ω(n)表示n的不同素因子的个数,即ω(n)=t.若n的所有因子的倒数和为整数,即0≤∑ij≤αjj=1,2,…,t1p1i1pi22…ptit为整数,称n是调和数.证明了和调和数相关的一个结论.     

A New Computational Approach to Ideal Theory in Number Fields

Let K be the number field determined by a monic irreducible polynomial f(x) with integer coefficients. In previous papers we parameterized the prime ideals of K in terms of certain invariants attached to Newton polygons of higher order of f(x). In this paper we show how to carry out the basic operations on fractional ideals of K in terms of these constructive representations of the prime ideals. From a computational perspective, these results facilitate the manipulation of fractional ideals of K avoiding two heavy tasks: the construction of the maximal order of K and the factorization of the discriminant of f(x). The main computational ingredient is the Montes algorithm, which is an extremely fast procedure to construct the prime ideals.     

有限素数度弧正则图

如果一个图的全自同构群在其弧集上正则,则称此图为弧正则图.本文刻画素数度的立方自由阶弧正则图,证明任何素数度2倍奇立方自由阶弧正则图都是正规或二部正规Cayley图,且不存在任意素数度4倍奇立方自由阶的弧正则图,推广了一些已知的结果,得到阶为8倍奇平方自由阶素数度弧正则图的分类,并发现新的弧正则图类.此外,基于所得的结果,我们提出一个猜想和有待后续研究的一些问题.     

一个包含欧拉函数的方程

设n为任意正整数,如果n〉1,设n=p1^α1p2^α2…pk^αk是n的标准分解式,函数Ω（n）定义为Ω（1）=0,Ω（n）=∑i=1^kαi,φ（n）为Euler函数,本文的主要目的是利用初等方法研究方程φ（φ（n））=2Ω（n）的可解性,并获得该方程的所有正整数解,从而彻底解决了前学者提出的一个问题．     

On the distribution of square-full and cube-full primitive roots

Periodica Mathematica Hungarica - A positive integer n is called an r-full integer if for all primes $$p\mid n$$ we have $$p^r\mid n.$$ Let p be an odd prime. For $$\gcd (n,p)=1$$, the smallest...     

Replacement of Factors By Subgroups in the Factorization of Abelian Groups

In his book Abelian groups, L. Fuchs raised the question asto whether, in general, in the factorization of a finite (cyclic)abelian group one factor may always be replaced by some subgroup.The answer turned out to be negative in general, but positivein certain cases. In this paper the complete answer for cyclicgroups is given. In all previously unsolved cases, the answerturns out to be positive. It is shown that a cyclic group hasthe property that in every factorization, one factor may bereplaced by a subgroup if and only if the group has order equalto the product of a prime and a square-free integer. Certainresults are also given in non-cyclic cases. 1991 MathematicsSubject Classification 20K01.     

Entiers Lexicographiques

An integer n is called lexicographic if the increasing sequence of its divisors, regarded as words on the (finite) alphabet of the prime factors (arranged in increasing size), is ordered lexicographically. This concept easily yields to a new type of multiplicative structure for the exceptional set in the Maier-Tenenbaum theorem on the propinquity of divisors, which settled a well-known conjecture of Erdös. We provide asymptotic formulae for the number of lexicographic integers not exceeding a given limit, as well as for certain arithmetically weighted sums over the same set. These results are subsequently applied to establishing an Erdös-Kac theorem with remainder for the distribution of the number of prime factors over lexicographic integers. This provides quantitative estimates for lexicographical exceptions to Erdos' conjecture that also satisfy the Hardy-Ramanujan theorem.     

关于多项式系数的整除性

设 n是正整数 ,k1 ,k2 ,… ,ks 是适合 k1 +k2 +… +ks=n的非负整数 ,正整数 nk1 k2 … ks=n!k1 !k2 !… ks!称为多项式系数 .本文讨论了当n=a0 +a1 p+a2 p2 +… +arpr ,其中 p为素数且 p≤ n,0≤ ai相似文献   

On the distribution of square-full numbers in arithmetic progressions

A positive integer n is called a square-full number if p ² divides n whenever p is a prime divisor of n. In this paper we study the distribution of square-full numbers in arithmetic progressions by using the properties of Riemann zeta functions and Dirichlet L-functions.     

关于完全正矩阵的几点注记(英文)

本文给出了一个 n×n非负、对称、弱对角占优矩阵 A为完全正的一个充分条件 .我们还给出了较好的算法 ,用以获得关于矩阵 A(当 A为完全正时 )的分解指数的一个上界 .     

On powersmooth numbers

A natural number n is called y-smooth (y-powersmooth, respectively) for a positive number y if every prime (prime power) dividing n is bounded from above by y. Let ψ(x, y) and ψ*(x, y) denote the quantity of y-smooth and y-powersmooth integers restricted by x, respectively. In this paper we investigate function ψ*(x, y) in general. We derive formulas for finding exact calculation of ψ*(x, y) for large x and relatively small y and give theoretical estimates for this function and for a function of the greatest powersmooth integer. This results can be used in the cryptography and number theory to estimate the convergence of factorization algorithms.     

最小1-因子覆盖集的若干结果

假设G是一个1-可扩图．G的1-因子覆盖是G的某些1-因子的集合M使得∪M∈M M=F（G）．1-因子数目最小的1．因子覆盖称为excessive factorization．一个excessive factorization中的1．因子数目称为图G的excessive index，记为x：（G）．本文我们基于G的耳朵分解和E（C）的依赖关系给出了X＇e（G）的上界．对任意正整数k≥3，我们构造出一个图G使得A（G）=3而X＇e（G）=k．进而，我们考虑了乘积图的excessive index．     

合数是绝对假素数的充要条件

利用正整数模的特征数这一新概念给出了合数是绝对假素数的充要条件。以此为据，证明了绝对假素数是奇数，它无异于1的平方因数，并且至少是三个互异的奇素数的乘积；还给出了两个绝对假素数或两个大于1的奇数的乘积是绝对假素数的充要条件。     

Irreducibility Results for Compositions of Polynomials with Integer Coefficients

We obtain explicit upper bounds for the number of irreducible factors for a class of polynomials of the form f ○ g, where f,g are polynomials with integer coefficients, in terms of the prime factorization of the leading coefficients of f and g, the degrees of f and g, and the size of coefficients of f. In particular, some irreducibility results are given for this class of compositions of polynomials.     

Irreducibility Results for Compositions of Polynomials with Integer Coefficients

We obtain explicit upper bounds for the number of irreducible factors for a class of polynomials of the form f ○ g, where f,g are polynomials with integer coefficients, in terms of the prime factorization of the leading coefficients of f and g, the degrees of f and g, and the size of coefficients of f. In particular, some irreducibility results are given for this class of compositions of polynomials.     

Algebraic Cayley graphs over finite fields

A new algebraic Cayley graph is constructed using finite fields. It provides a more flexible source of expander graphs. Its connectedness, the number of connected components, and diameter bound are studied via Weil's estimate for character sums. Furthermore, we study the algorithmic problem of computing the number of connected components and establish a link to the integer factorization problem.