On the oracle complexity of factoring integers

The problem of factoring integers in polynomial time with the help of an infinitely powerful oracle who answers arbitrary questions with yes or no is considered. The goal is to minimize the number of oracle questions. LetN be a given compositen-bit integer to be factored, wheren = log₂ N. The trivial method of asking for the bits of the smallest prime factor ofN requiresn/2 questions in the worst case. A non-trivial algorithm of Rivest and Shamir requires onlyn/3 questions for the special case whereN is the product of twon/2-bit primes. In this paper, a polynomial-time oracle factoring algorithm for general integers is presented which, for any >0, asks at most n oracle questions for sufficiently largeN, thus solving an open problem posed by Rivest and Shamir. Based on a plausible conjecture related to Lenstra's conjecture on the running time of the elliptic curve factoring algorithm, it is shown that the algorithm fails with probability at mostN ^–/2 for all sufficiently largeN.     

On multiplicativity of the Bernstein operator

For continuous functions f and g, we prove that the Bernstein operator B_n is multiplicative for all n≥1 and all x∈2[0,1] if and only if at least one of the functions f and g is a constant function. Some other variants of multiplicativity are also considered.     

Primality testing and factoring

We show that any efficient deterministic algorithm for finding square roots modulo a prime can be turned into an efficient Monte Carlo primality test which has a very small error probability if factoring is hard.We apply our general construction to a well-known square root algorithm and give explicit bounds for the error probability of the resulting primality test (or the running of the corresponding factoring algorithm.     

快速倒序算子的研究

为了有效地处理建筑块,Bagley最先提出了应用倒序算子来对定义建筑块的基因进行适应性聚集。但是Bagley和Frantz的研究都表明,倒序算子太慢,作用不明显。针对TSP问题,郭涛提出一个“带导向的”倒序算子,取得了很好的效果。为了设计更快速的倒序算子,提出结合粒子群优化的方法改进郭涛算法,更好地利用当前最优解指导倒序,同时对个体施加倒序运算后立即评估,如有改进马上保存,从而巩固所获取的建筑块,不至于因为后面的错误而导致前功尽弃。实验结果证明了新算法的可行性。     

Optimal Algorithm for Algebraic Factoring

This paper presents on optimized method for factoring multivariate polynomials over algebraic extension fields defined by an irreducible ascending set. The basic idea is to convert multivariate polynomials to univariate polynomials and algebraic extension fields to algebraic number fields by suitable integer substituteions.Then factorize the univariate polynomials over the algebraic number fields.Finally,construct mulativariate factors of the original polynomial by Hensel lemma and TRUEFACTOR test.Some examples with timing are included.     

On the implication operator in fuzzy logic

We investigate the different possible ways of translating an implication proposition in approximate reasoning. We study a general class of these operators.     

Human factoring a text editor manual

This article describes how we rewrote a manual for a text editor following human-factors guidelines and revised it according to the results of developmental testing. The new manual was then evaluated with secretaries who were given either the original or the rewritten manual and asked to do two editing tasks. We measured the quality of the finished text; the number of different commands used; the amount and type of assistance requested; and attitudes towards the manuals, program and tasks. There were significant differences between the two groups of users on the performance measures and on attitudes towards the manuals in favour of the new manual. We propose a model of user-documentation interaction and suggest a methodology for preparing computer documentation.     

Proxy signature schemes based on factoring

The proxy signature schemes allow proxy signers to sign messages on behalf of an original signer, a company or an organization. However, most of existing proxy signature schemes are based on the discrete logarithm problem. In this paper, the author would like to propose two efficient proxy signature schemes based on the factoring problem, which combine the RSA signature scheme and the Guillou-Quisquater signature scheme. One is a proxy-unprotected signature scheme that is more efficient. No matter how many proxy signers cooperatively sign a message, the computation load for verifiers would remain almost constant. The other is a proxy-protected signature scheme that is more secure. Finally, to protect the privacy of proxy signers, the author proposes a proxy-protected signature scheme with anonymous proxy signers.     

On the WOWA operator and its interpolation function

The weighted ordered weighted averaging (WOWA) operator is one of the existing aggregation methods that can be used to fuse numerical data. The application of this operator to a set of data requires an interpolation function. In this paper, we present a few results about the sensitivity of the operator according to the interpolation method used. © 2009 Wiley Periodicals, Inc.     

一种强素数因子分解的量子算法

深入分析了RSA模数N的强素数因子的特殊结构,进一步确定了2对N的阶δN（2）与Euler函数?准（N）之间的关系,提出了新的分解由强素数因子乘积构成的RSA模N的量子算法,简化了因子分解的过程,提高了运算效率。     

Computing Frobenius maps and factoring polynomials

A new probabilistic algorithm for factoring univariate polynomials over finite fields is presented. To factor a polynomial of degreen overF _q , the number of arithmetic operations inF _q isO((n ²+nlogq). (logn)² loglogn). The main technical innovation is a new way to compute Frobenius and trace maps in the ring of polynomials modulo the polynomial to be factored.     

Nondeterministic polynomial time factoring in the tile assembly model

Formalized study of self-assembly has led to the definition of the tile assembly model, Previously I presented ways to compute arithmetic functions, such as addition and multiplication, in the tile assembly model: a highly distributed parallel model of computation that may be implemented using molecules or a large computer network such as the Internet. Here, I present tile assembly model systems that factor numbers nondeterministically using Θ(1)$\Theta \left(1\right)$ distinct components. The computation takes advantage of nondeterminism, but theoretically, each of the nondeterministic paths is executed in parallel, yielding the solution in time linear in the size of the input, with high probability. I describe mechanisms for finding the successful solutions among the many parallel executions and explore bounds on the probability of such a nondeterministic system succeeding and prove that the probability can be made arbitrarily close to 1.     

On the fixed points of the iterated pseudopalindromic closure operator

First introduced in the study of the Sturmian words by de Luca in 1997, iterated palindromic closure was generalized to pseudopalindromes by de Luca and De Luca in 2006. This operator allows one to construct words with infinitely many pseudopalindromic prefixes, called pseudostandard words. We provide here several combinatorial properties of the fixed points under iterated pseudopalindromic closure.     

Computing the SKT reliability of acyclic directed networks using factoring method

1IntroductionReliabilitymeasuresofnetworksareimportantparametersinbothdesignandoperationofsystemslikepowernetworks,communicationnetworks,andcomputernetworks.Inthesenetworks,acyclicdirectednetworks(AD-networks)areverycommon.Inthispaper,westudythesource-to-K-terminal(SKT)reliabilityproblemofAD-networks.Givenadirectednetworkwithunreliablenodesandedges,KbeingasubsetofnodesandsKthespecifiedsource,SKTreliabilityistheprobabilitythatthereexistoperatingpathsfromthesourcestoeachnodeinsetK-{s}.SKT…