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

Download Edit this record How to cite View on PhilPapers
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.
No keywords specified (fix it)
PhilPapers/Archive ID
Upload history
Archival date: 2018-12-17
View other versions
Added to PP index

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.