# 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**

(categorize this paper)

**PhilPapers/Archive ID**

SERTDO-4

**Revision history**

Archival date: 2018-12-17

View upload history

View upload history

References found in this work BETA

No references found.

Citations of this work BETA

Independence of the Grossone-Based Infinity Methodology From Non-Standard Analysis and Comments Upon Logical Fallacies in Some Texts Asserting the Opposite.Yaroslav Sergeyev - 2019 -

*Foundations of Science*24 (1):153-170.**Added to PP index**

2018-12-17

**Total views**

31 ( #46,510 of 50,149 )

**Recent downloads (6 months)**

10 ( #41,049 of 50,149 )

How can I increase my downloads?

**Downloads since first upload**

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