Integer algorithm

We define an "integer algorithm" as an algorithm that takes integer inputs and produces integer outputs.

Table of contents
- Integer multiplication Integer algorithm
- Integer factorization Integer algorithm
  - Integer factorization algorithm Integer factorization
  - NP-hard cryptosystem Integer factorization

Integer multiplication

cs.stackexchange.com/questions/16226/what-is-the-fastest-algorithm-for-multiplication-of-two-n-digit-numbers

Integer factorization

Complexity: NP-intermediate as of 2020:

expected not to be NP-complete because it would imply NP != Co-NP: cstheory.stackexchange.com/questions/167/what-are-the-consequences-of-factoring-being-np-complete#comment104849_169
expected not to be in P because "could we be that dumb that we haven't found a solution after having tried for that long?

The basis of RSA: RSA. But not proved NP-complete, which leads to:

Integer factorization algorithm

Shor's algorithm

NP-hard cryptosystem

This is natural question because both integer factorization and discrete logarithm are the basis for the most popular public-key cryptography systems as of 2020 (RSA and Diffie-Hellman key exchange respectively), and both are NP-intermediate. Why not use something more provenly hard?

cs.stackexchange.com/questions/356/why-hasnt-there-been-an-encryption-algorithm-that-is-based-on-the-known-np-hard "Why hasn't there been an encryption algorithm that is based on the known NP-Hard problems?"

 Ancestors (9)

 View article source

 Discussion (0)

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version