# 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.

244 questions
Filter by
Sorted by
Tagged with
82 views

### How Does Prime Factorization Break ECDSA?

I have heard that ECDSA will be broken in the not-to-distant future (roughly 15-25 years) by Quantum Computers running Shor's Algorithm. However, to my understanding, the only purpose of Shor's ...
89 views

### Is phi-hiding assumption as hard as integer factorization?

Phi-hiding assumption can be simply stated as (wrt hardness) It is difficult to find small factors of $\varphi(m)$ where $m$ is a number whose factorization is unknown and $\varphi$ is Euler's ...
120 views

198 views

### Purpose of using a=2 in Pollard p-1 factorization method

The Pollard p-1 factorization method states if $\gcd(2^{B!}-1,n)=p$ where $p>1$ and $B$ bounds the prime factors of $p$, then $p$ is a prime factor of $n$. Shouldn't it be $\gcd(a^{B!}-1,n)$ for ...
69k views

### How big an RSA key is considered secure today?

I think 1024 bit RSA keys were considered secure ~5 years ago, but I assume that's not true anymore. Can 2048 or 4096 keys still be relied upon, or have we gained too much computing power in the ...
55 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 ...
61 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 ...
89 views

13k views

### Why has the RSA factoring challenge been withdrawn?

Wikipedia states that RSA challenge has been withdrawn. Does it mean that an efficient factoring algorithm is "just around the corner"? or are there some other reasons? If the challenge was still ...
95 views

### Prime Factorization in RSA always leads to the product of two primes?

Lets prime factorize $30$: $$30 = 3 \cdot 10 = 3 \cdot 2 \cdot 5$$ We see that the number $30$ is a product of $3$ primes. But in RSA, when factorizing huge numbers, we always seem to only get two ...
2k views

### In the Quadratic Sieve, why restrict the factor base?

In the Quadratic Sieve, when factoring a number $N$, many descriptions and most implementations select as the factor base the set of small primes $p_j$ less than some bound $B$ restricted to having ...
86 views

### Algorithm for factoring a 30 decimal digit number

My professor has given me an RSA factoring problem as an assignment. The given modulus is 30 decimal digits long. I have been searching a lot about factoring algorithms. But it has been quite a ...
33 views

### Point-halving/solving quartic equations over the elliptic curve E(Z_N)/ring Z_N where N = pq

I am wondering whether there are any results/whether there is any knowledge about the following problem: Given a univariate polynomial (say, a quartic) equation defined over $\mathbb{Z}_N$, is it ...
48 views

### Trivariate Coppersmith Implementation

Bivariate Coppersmith is standard package in math software with number theory support. Bauer and Antoine Joux introduced trivariate Coppersmith in https://www.iacr.org/archive/eurocrypt2007/45150361/...
507 views

### Distributed integer factorization?

I'm looking around for publicly published work on factorization of large numbers using distributed systems of any kind. So far I've come across the PDF "Mapreduce for integer factorization" by Javier ...
360 views

### RSA. Would someone kindly help me understand what d and c are in this factorization exercise?

What are $d$ and $c$ in this factorization exercise? What order must $d$ and $c$ have for $p$ and $N$? If $N=pq$, $(p+q-4) =0 \bmod 8$, and $p \geq (p+q)/4$ $$N=66390187$$ $$(3*N-1)/8=24896320$$ ...
1k views

2k views

### Is there an algorithm for factoring N, which is just as simple as this one, but faster?

I found a simple algorithm for factoring semiprime numbers, you can read about it in Factoring Semiprimes and Possible Implications for RSA (paywall-free). It basically works like this: You reverse ...