# The difficulty of prime factorization is a consequence of the positional numeral system

*International Journal of Unconventional Computing*12 (5-6):453–463 (2016)

**Abstract**

The importance of the prime factorization problem is very well known
(e.g., many security protocols are based on the impossibility of a fast factorization
of integers on traditional computers). It is necessary from a number k
to establish two primes a and b giving k = a · b. Usually, k is written in a positional
numeral system. However, there exists a variety of numeral systems
that can be used to represent numbers. Is it true that the prime factorization is
difficult in any numeral system? In this paper, a numeral system with partial
carrying is described. It is shown that this system contains numerals allowing
one to reduce the problem of prime factorization to solving [K/2] − 1
systems of equations, where K is the number of digits in k (the concept of
digit in this system is more complex than the traditional one) and [u] is the
integer part of u. Thus, it is shown that the difficulty of prime factorization is
not in the problem itself but in the fact that the positional numeral system is
used traditionally to represent numbers participating in the prime factorization.
Obviously, this does not mean that P=NP since it is not known whether
it is possible to re-write a number given in the traditional positional numeral
system to the new one in a polynomial time.

**Keywords**

No keywords specified (fix it)

**Categories**

**PhilPapers/Archive ID**

SERTDO-4

**Upload history**

Archival date: 2018-12-17

View other versions

View other versions

**Added to PP index**

2018-12-17

**Total views**

64 ( #49,754 of 2,439,319 )

**Recent downloads (6 months)**

16 ( #38,075 of 2,439,319 )

How can I increase my downloads?

**Downloads since first upload**

*This graph includes both downloads from PhilArchive and clicks on external links on PhilPapers.*