# Questions tagged [factoring]

The decomposition of an integer number to the product of other integers. Algorithms such as RSA are based on the premise that no practical way has been found was to factorize large integers when they have been produced by multiplying two large primes.

266 questions
Filter by
Sorted by
Tagged with
0answers
23 views

### Is there any relation between Decisional Composite Residuosity Assumption and Square roots in elliptic curve groups assumption?

We have DCRA and ECSQRT assumptions. ECSQRT: Square roots in elliptic curve groups over Z/nZ Definition: Let E(Z/nZ) be the elliptic curve group over Z/nZ. Given a point Q ∈ E(Z/nZ). Compute all ...
1answer
70 views

### Why is factorial used in Pollard's $p - 1$ algorithm?

Why exactly do we use factorial for finding an $L$ which is divisible by $p - 1$? Pollard's algorithm is about B-powersmooth numbers & not B-smooth numbers. So where exactly does the factorial ...
1answer
92 views

### Cost of factoring $u^2-v^2$ when $v\ll u$?

What's the approximate computational cost of factoring $N=u^2-v^2$ when $v\ll u$? Assume $u$ and $v$ are unknown integers, with $u$ large enough that $n$ has the size of an RSA modulus. I suspect ...
1answer
5k views

### How was this 2048 bit number factored so fast?

I'm working on a CTF. The challenge is to get the contents of an encrypted message given the ciphertext and the 2048-bit RSA public key. I did finally get the flag after a few hours, but I'm still not ...
0answers
36 views

### Security game for factoring

this is probably a fairly simple request, but I have'nt been able to find it anywhere. A lot of cryptography schemes have security games associated with them. In the Book by Katz, a bunch of schemes ...
2answers
3k views

### Is it proven that breaking RSA is equivalent to factoring as of 2021?

I can't find any publication that proves this.
1answer
1k views

### Does the security of RSA come from just the carries in multiplication?

Although it's hard for me to find a reference, it's my understanding that if you calculate $N = pq$ using $GF(2)$ polynomial multiplication rather than ordinary multiplication, it is easy to factor $N$...
1answer
38 views

0answers
62 views

### Multi-users RSA problem

Rivest and Kalisky's RSA problem considers various notions on security of the RSA One-Way Trapdoor Permutation. They do it only from the perspective of a single user. What's the state of the art in ...
1answer
62 views

### Computational trapdoor where the problem is tractable for both parties but easier for one

Usually the sort of trapdoors which are talked about are designed such as to make the computation intractable for one party and tractable for the other. But what if one party merely has a big ...
1answer
67 views

### With composite $n_1$ = $p_1q_1$, and a separate $n_2 = p_1q_2$, can the primes be calculated more efficiently than factorization?

Supposing that the (3 total) primes are kept secret? Does the reuse of $p_1$ allow an attacker to compromise $n_1$ and $n_2$ if the attacker guesses that both were generated with a shared prime ...
1answer
140 views

### Can Eve break this public key cryptosystem if she can solve DLP or DHP?

The PKC is in this way: Alice and Bob fix a publicly known prime $p$, and all of the other numbers used are private (unless sent). Alice takes her message $m$, chooses a random exponent $a$, and ...
0answers
101 views

1answer
466 views

### Factoring 2048 bit number is easy?

my PC found a factor for (2^2048)-1 in under a second...so does that make RSA-2048 less secure right? i used prime 95. and actually i am kinda curious how it found a factor so fast? i can even factor ...