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

Download Edit this record How to cite View on PhilPapers
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)
PhilPapers/Archive ID
SERTDO-4
Revision history
Archival date: 2018-12-17
View upload history
References found in this work BETA

No references found.

Add more references

Citations of this work BETA

Add more citations

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.