Skip to main content
improve title and formatting
Source Link
yyyyyyy
  • 12.2k
  • 4
  • 48
  • 68

Is integer factorization (with modular arithmetic)modulo a product of primes an NP-hard problem?

For example, let, p$p$ and q are$q$ be two large prime numbers. We deduce n = p * qset $n = p \cdot q$. Now, a * b = clet (mod n)$a \cdot b = c \pmod n$. Given c$c$ and n$n$, is finding outthe factors a$a$ and b is$b$ computationally difficult?

I can alternatively ask, is integer factorization modulo a product of primes an NP-hard problem?

Is integer factorization (with modular arithmetic) a NP-hard problem?

For example, let, p and q are two large prime numbers. We deduce n = p * q. Now, a * b = c (mod n). Given c and n, finding out factors a and b is computationally difficult?

I can alternatively ask, is integer factorization a NP-hard problem?

Is factorization modulo a product of primes an NP-hard problem?

For example, let, $p$ and $q$ be two large prime numbers. We set $n = p \cdot q$. Now, let $a \cdot b = c \pmod n$. Given $c$ and $n$, is finding the factors $a$ and $b$ computationally difficult?

I can alternatively ask, is integer factorization modulo a product of primes an NP-hard problem?

Source Link

Is integer factorization (with modular arithmetic) a NP-hard problem?

For example, let, p and q are two large prime numbers. We deduce n = p * q. Now, a * b = c (mod n). Given c and n, finding out factors a and b is computationally difficult?

I can alternatively ask, is integer factorization a NP-hard problem?