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

333 questions
Filter by
Sorted by
Tagged with
31 views

### Consequences of breaking Diffie-Hellman to factoring

According to the answer in What are the consequences of Diffie Hellman problem in P?, it appears we believe Discrete Logarithm and Diffie-Hellman are equivalent problems. We also know if Discrete ...
• 972
93 views

### A highly space-efficient embedding of prime factorization problem using the Ising model

I hope this is not off-topic for this SE, as it directly relates to the RSA problem. My background is in quantum information and computation, so please excuse me if my notation doesn't match your ...
294 views

1 vote
83 views

### Why doesn't the existence of the Quadratic Sieve algorithm imply that integer factorization is in the class SUBEXP?

SUBEXP is defined as the intersection of DTIME(2^n^c) over all c>0. The order of the Quadratic Sieve algorithm is O(exp((k+o(1))(logN)^1/2(loglogN)^1/2)). Doesn't this imply that the decision ...
• 13
168 views

### How often do hard-to-factor numbers occur?

[Computer scientist here who is not totally familiar with the factoring literature -- please forgive my ignorance.] It's well known that hard-to-factor integers, $n$, are typically semi-primes, such ...
181 views

### How to know if a random number is a probable semiprime?

Simple question : given a randomly generated number $N$ from a hash that is hard to factor, how to check if $N$ is probably a semi‑prime in a faster way than factoring it ? My problem is while it’s ...
• 240
1 vote
430 views

• 1
1 vote
82 views

### Why does sum of remainders of numbers divided by known factors, and repeating the process over and over, give factors of the two starting numbers? [closed]

While working with serial division/remainder method of finding factors, I have found that using knowns such as the known factors of a comparative number, or the difference between a number to be ...
70 views

### Integer factorization $n = pq$ with additional knowledge of $\lfloor \sqrt{p} \rfloor \oplus \lfloor \sqrt{q}\rfloor$

We know that we can factor integer $n = pq$ when we know that $p\oplus q$, where $\oplus$ means xor. If we know $\lfloor \sqrt{p} \rfloor \oplus \lfloor \sqrt{q}\rfloor$, can we factor $n$?
• 21
1 vote
108 views

### finding r-th root in $\mathbb{Z}/n\mathbb{Z}$

I was reading the paper One-way Accumulators: A Decentralized Alternative to Digital Signatures by Benaloh and de Mare [link], and in section 4.2, they say that given $z\in (\mathbb{Z}/n\mathbb{Z})^*$ ...
• 477
145 views

### Big prime factor of the prime number you feed to Diffie Hellman

They say the security of Diffie-Hellman depends on the factorization of (N-1), where N is the big prime number you feed it. More specifically, (N-1) itself has to have a big prime factor, such as (N-1)...
328 views

### Noisy Quantum Gates Spoil Shor's Factorization Attack

Update: In Lipton and Regan's blog, Scott Aaranson and Craig Gidney have commented that the results are not unexpected and also not a deal-breaker in that dealing with this type of noise is already ...
• 23.1k
1 vote
45 views

### Can some cryptographic conclusions in the prime field be applied to the Galois field？

Such as integer factorization problem and discrete logarithm problem. Assuming a large polynomial is obtained by multiplying two generated polynomials, is it NP hard to decompose it into these two ...
• 23
1k views

### How did they factor RSA 240?

Since NFS runs in essentially $n^{1/3}$ time, and RSA-240 is a composite of two 120-digit primes, shouldn't this have taken at least $10^{40}$ operations, not including any overhead? Even if you could ...
354 views

### RSA : Is there a way to compute phi(n) or N itself if we only know e, d and a ciphertext?

I am trying to solve a problem where private key exponent d, ciphertext c, and public key exponent e (65537) are known. How can I calculate φ(n) or n itself? An extended version of the problem would ...
• 33
351 views

• 361
177 views

### Take n = 4633 and B = {−1, 2, 3}. Note the b-smooth numbers as {67, 68, 69}. Find the factor of n

This question is from Quadratic Sieve Factorization Method. Didn't find the solution on the web also. And not aware of how to solve such questions.
36 views

• 519
623 views

### How fast is Factorization reduced to a Discrete Logarithm?

Given a RSA modulus $n$, which is the product of two safe primes: \begin{align*} P &= 2p + 1 \quad\quad\quad Q = 2q + 1 \\ n &= P \cdot Q = 4p q + 2 p + 2 q + 1 \end{align*} The ...
• 361
179 views

### Why if x ∉ Z*n then the gcd(x, n) != 1? RSA

I understand that if the $\gcd(x, n)\neq=1$ then the $\gcd$ is one of the $n$ prime factors, $q$ or $q$. But how is the fact that $x \not\in Z^*_n$ related to $\gcd(x, n)\neq 1$?
• 25
118 views

### How do I prove that if $\text{gcd}(m,n) \neq 1$, the result is $p$ or $q$ in RSA?

I understand that $\text{gcd}(m,n)$ needs to be $1$ so we can apply the Euler's theorem, and if it's not $1$, the result is one of the prime factors of $n$. But Why the result it is always $p$ or $q$? ...
• 25
227 views

### CTF question with hint "Quadratic method to solve ifp problem"

I totally have no idea about this Rabin decrypt problem. source code: https://github.com/shanzhuer/myctf/blob/main/crypto/rabin.py Inside there were $2^{21}$ times of encryption and decryption of ...
567 views

### A probable attack for RSA (factorization): how to improve it?

A probable attack for RSA (factorization): how to improve it? $N=8*G+3$ can be factored if there is a non-trivial negative $k$ such that $\frac{(N*(9+24*k)-3)}{8}=-6*m^2$ [to exclude the two trivial ...
65 views

### What kind of special numbers are not suitable as RSA keys?

I have read that some integers are not appropriate to be chosen as the modulus in an RSA cryptosystem. Some of these numbers are those that, given a modulus $n=pq$, then $p-1$ or $q-1$ do not have ...
206 views

### Is Fermat's Factorization Method used in any practical application?

Is there any use for Fermat's Factorization Method in the world of cryptography? I see that several algorithms are based on it, such as the quadratic sieve and general number field sieve. I understand ...
• 33
1 vote
126 views

### How to factorize RSA modulus while given two Public Exponents and the difference between two Private Exponents?

The RSA modulus is the product of two $2048$-bit primes. And the two Public Exponents are both $16$-bit. I also got the difference between two Private Exponents $\left | d_1-d_2 \right |.$ Is there ...
• 59
842 views

### Breaking RSA with P,Q LSB bits

Let's say we have a certain amount of LSB bits of P and Q and we want to fully reconstruct them given N=P*Q. I know this problem was studied in literature by Coppersmith and that Lattice methods are ...
• 31
284 views

### Does a 2047-bit factoring oracle affect 2048-bit RSA security?

I started wondering. RSA relies on prime factorisation being hard. So if a 2047-bit oracle machine existed that could instantly factor any 2047-bit number (and you can't look inside at how it works), ...
• 191
158 views

### Is there a discrete log challenge?

RSA challenge is well-known and it has a wiki page. Is there a discrete log for $\mathbb F_p$ where $p$ is Sophie-Germain prime?
• 21
76 views

### Historical key sizes for RSA and discrete log [closed]

What is the historical pattern for key size increases for rsa vs discrete log? What are the current and future projected sizes for these?
• 972
1 vote
131 views

### Factorization of the product of two specific primes

Help me please. Consider specific primes $p = x^{d} + 1$ and $q = x^{e} + 1$ for some $x, d, e \in \mathbb{N}$. Can their product $n = pq$ be factorized faster than the product of general primes ? In ...
1 vote
115 views

### Question about sequence length/count/security of $x\mapsto x^\alpha \mod (N=Q\cdot R)$, with $Q=2q_1q_2+1$ and $R=2r_1r_2+1$ and $\alpha = 2q_2r_2$

Given a number $N$ with $$N=Q\cdot R$$ $$Q=2\cdot q_1 \cdot q_2+1$$ $$R=2\cdot r_1\cdot r_2+1$$ with different primes $P,Q,q_1,q_2,r_1,r_2$. If we now choose an exponent $\alpha$ containing prime ...
• 453
1 vote
132 views

### Which impact on security (factorization) has a common prime factor among prime factors? $N=P\cdot Q$ with $P=2\cdot F\cdot p+1$, $Q=2\cdot F\cdot q+1$

Which impact on security (factorization) has a common prime factor among the prime factors $P$,$Q$ of a number $N$ $$N=P\cdot Q$$ $$P=2\cdot F\cdot p+1$$ $$Q=2\cdot F\cdot q+1$$ with $F,q,p$ different ...
• 453
81 views

### Given $N$ with $d$ prime factors. Can the number of unique values $x^d \mod N$ calculated for $d>2$? Does the total amount decrease at some point?

Given a number $N$ with $d$ unique prime factors. Can the number of unique values $v$ with $$v \equiv x^d \mod N$$ $$x\in[0,N-1]$$ $$N = \prod_{i=1}^{d} p_i$$ be calculated for $d>2$? (Q1) Does ...
• 453
555 views

### A novel method for hiding data using prime numbers?

Has the following method of hiding data been proposed or studied? What is the efficiency or security of this method? What applications could use this method? Data is to be hidden in a number that is ...
82 views

### Are there applications which cannot be done with only factoring trapdoor?

Suppose we only have to use factoring as trapdoor function and we are disallowed to use other trapdoors, are there applications currently deployed which cannot be done?
• 972
1 vote
57 views

### How secure is a projection to a subspace with much lower member size for $x\mapsto x^a$ mod $N = PQ$, $P=2p+1$, $Q=2qr+1$, to target space $r=2abc+1$?

A cyclic sequence can be produced with $$s_{i+1} = s_i^a \mod N$$ with $N = P \cdot Q$ and $P = 2\cdot p+1$ and $Q = 2\cdot q\cdot r+1$ and $r = 2\cdot u \cdot v \cdot w +1$ with $P,Q,p,q,r,u,v,w$ ...
• 453
1 vote
88 views

### Can Shor's algorithm factor over finite fields/rings/groups?

Shor's algorithm can (efficiently) solve equations of the form: $$n = pq$$ and $$n = x^{2} + y^{2}$$ This question is simple: Can Shor's algorithm solve these equations in polynomial time when they ...
• 45
This is related to this question about solving the following expression: $$x^{2} + y^{2}$$ This can be factored over the gaussian integers as $$(x + iy)(x - iy)$$ If one could factor a sum of two ...