Skip to main content
Cryptography

Return to Question

Language
Source Link
Ruan Sunkel
Ruan Sunkel
  • 209
  • 1
  • 6

Consider $x^e \equiv a\pmod n$, given $n$, $a$, and $e$$e>2$, with $n$ being a composite integer and unknown $x$.

Can a hypothetical function $f(a)=x$, an $eth$ root extractor, be used / adapted to factor $n$, in the same way that the multiplicative order of $x \space modulo\space n$ can be used to factor $n$ like in the classical part of Shor's algorithm?

Consider $x^e \equiv a\pmod n$, given $n$, $a$, and $e$, with $n$ being composite integer and unknown $x$.

Can a hypothetical function $f(a)=x$, an $eth$ root extractor, be used / adapted to factor $n$, in the same way that the multiplicative order of $x \space modulo\space n$ can be used to factor $n$ like in the classical part of Shor's algorithm?

Consider $x^e \equiv a\pmod n$, given $n$, $a$, and $e>2$, with $n$ being a composite integer and unknown $x$.

Can a hypothetical function $f(a)=x$, an $eth$ root extractor, be used / adapted to factor $n$, in the same way that the multiplicative order of $x \space modulo\space n$ can be used to factor $n$ like in the classical part of Shor's algorithm?

Source Link
Ruan Sunkel
Ruan Sunkel
  • 209
  • 1
  • 6

Does knowing modular eth roots help in factoring n?

Consider $x^e \equiv a\pmod n$, given $n$, $a$, and $e$, with $n$ being composite integer and unknown $x$.

Can a hypothetical function $f(a)=x$, an $eth$ root extractor, be used / adapted to factor $n$, in the same way that the multiplicative order of $x \space modulo\space n$ can be used to factor $n$ like in the classical part of Shor's algorithm?