In this paper, we construct deterministic factorization algorithms for natural numbers N under the assumption that the prime power decomposition of Euler’s totient function φ( N) is known. Their runtime complexities depend on the number ω( N) of distinct prime divisors of N, and we present efficient methods for relatively small values of ω( N) as well as for its large values. One of our main goals is to establish an asymptotic expression with explicit remainder term O( x/ A) for the number of positive integers N ≤ x composed of s distinct prime factors that can be factored nontrivially in deterministic time t = t( x), provided that the prime power decomposition of φ( N) is known. We obtain it for A = A( x) = x 1– ɛ , where ɛ = ɛ( s) > 0 is sufficiently small and t = t( x) is a polynomial in log x of degree d = d( ɛ). An analogous bound is deduced under the assumption of the oracle providing the decomposition of orders of elements in [Formula: see text].

E. Bach showed that factorization of an integer n can be reduced in probabilistic polynomial time to the problem of computing exponents of elements in ℤn* (in particular the group order of ℤn*). It is also known that factorization of square-free integer n can be reduced to the problem of computing the group order of an elliptic curve E/ℤn. In this paper we describe the analogous reduction for computing the orders of Jacobians over ℤn of hyperelliptic curves C over ℤn using the Mumford representation of divisor classes and Cantor’s algorithm for addition. These reductions are based on the group structure of the Jacobian. We also propose other reduction of factorization to the problem of determining the number of points |C(ℤn)|, which makes use of elementary properties of twists of hyperelliptic curves.

University in Poland, 4-6 July 2017.It was inaugurated in 2000 at the 14th Czech and Slovak International Conference on Number Theory in Liptovski Jan, Slovak Republic, with a special crypto session and since then has been organized in a selected Central European country every year.The aim of the CECC is to gather people involved in cryptology.The talks cover a wide range of topics including symmetric or asymmetric algorithms and protocols, as well as practical and theoretical aspects of computer security and computational number theory.This edition gathered over 50 persons from Europe and all the world.11 articles related to applied cryptography were published in the Int.J. Electronics and Telecom.v. 64 n. 2, (2018) and nine more theoretical papers were submitted for the special conference volume of Fundamenta Informaticae.They were then subjected to a 3 round review process by the journal experts.Ultimately, 5 papers were selected to be published in this special conference volume.The issues of these works include the following topics: encryptions, hashing, randomness, curves and compression.We wish to express our deep appreciation to the authors for their contributions and to the reviewers for their careful, insightful and constructive reviews.

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.

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.

In the paper we investigate the set of odd, squarefree positive integers n that can be factored completely in polynomial time O(log 6+ ɛ n), given the prime decomposition of orders ord n b 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(log 6+ ɛ n), is at most ( η − 2) −1 x(log x) − c( η−2) , for some c > 0 and arbitrary ɛ > 0.