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 functions A(x), C(x) and D(x) have the polynomial growth (of log x) at infinity.
2
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
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 Φ under the Extended Riemann Hypothesis. We show, unconditionally, that such a deterministic polynomial reduction exists for a large class of integers.
3
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
In the paper we investigate the set of odd, squarefree positive integers n that can be factored completely in polynomial timeO(log6+ε n), given the prime decomposition of orders ordnb for b ≤ logη n, (η > 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(log6+εn), is at most (η - 2)-1x(log x)-c(η-2), for some c > 0 and arbitrary ε > 0.
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.