| সংক্ষিপ্ত: | In this paper we address two different problems related with the factorization of an RSA (Rivest–Shamir–Adleman cryptosystem) modulus <i>N</i>. First we show that factoring is equivalent, in deterministic polynomial time, to counting points on a pair of twisted Elliptic curves modulo <i>N</i>. The second problem is related with malleability. This notion was introduced in 2006 by Pailler and Villar, and deals with the question of whether or not the factorization of a given number <i>N</i> becomes substantially easier when knowing the factorization of another one <inline-formula><math display="inline"><semantics><msup><mi>N</mi><mo>′</mo></msup></semantics></math></inline-formula> relatively prime to <i>N</i>. Despite the efforts done up to now, a complete answer to this question was unknown. Here we settle the problem affirmatively. To construct a particular <inline-formula><math display="inline"><semantics><msup><mi>N</mi><mo>′</mo></msup></semantics></math></inline-formula> that helps the factorization of <i>N</i>, we use the number of points of a single elliptic curve modulo <i>N</i>. Coppersmith’s algorithm allows us to go from the factors of <inline-formula><math display="inline"><semantics><msup><mi>N</mi><mo>′</mo></msup></semantics></math></inline-formula> to the factors of <i>N</i> in polynomial time.
|
|---|