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
0
votes
0
answers
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
3
votes
0
answers
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 ...
6
votes
1
answer
294
views
Find unknown primes from two RSA modulus
Suppose that $𝑝$, $𝑞$, and $𝑟$ are $512$-bit primes and for some integer $𝑎 < 10^5$, $𝑝 + 𝑎$ is also prime. We know the moduli $𝑛_1 = 𝑝 × 𝑞$ and $𝑛_2 = ...
- 557
2
votes
1
answer
89
views
Reduction from factoring to RSA and the Oracle RSA problem
Recently I read some papers related to RSA Brown16,AM09,BNPS01 and I learned that there is a variant problem of RSA is The oracle RSA problem (or one more RSA Problem) is $m+1$ copies of the classic ...
- 311
1
vote
0
answers
47
views
Is a cryptosystem based on hardness of factorization of polynomials, as defined below valid? [closed]
I'm proposing a cryptosystem as defined below:
Private Key: $(R, A, R^{-1})$, where $R = \left(\mathbf{r_1}, \cdots, \mathbf{r_n}\right)$ is full-rank, with $n \geq 4$, even; $A = \left(a_1\mathbf{...
- 69
1
vote
1
answer
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
2
votes
3
answers
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 ...
- 121
0
votes
1
answer
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
2
answers
430
views
Factoring 350 to 400 bits long rsa number with a factor that has a known bitlength… But in less than 5 to 7 minutes and less than $100
the gnfs is the most efficient algorithm for factoring numbers formed of equal composites.
But it’s sequential/Linea Algebra parts mean (If I’m not wrong), that it requires at least 10 minutes on ...
- 240
2
votes
1
answer
769
views
How could a 1024‒bits RSA modulus be most economically factored within months today?
Of course this is a question with an answer that is due to evolve.
A 2002 paper about TWIRL stated that the cost would be around 10M\$ and an other 10M\$ to manufacture the device. A later 2007 paper ...
- 240
3
votes
2
answers
166
views
RSA given 30% MSB of p and 30%MSB of q
is factoring RSA given 30% MSB of p and 30%MSB of q possible in polynomial time?
Notice that it is known that given 50% MSB of p or q it is doable in polynomial time using Coppersmith's theorem
- 463
-2
votes
3
answers
176
views
Can a very efficient RSA factoring algorithm be worth money?
If someone had a very efficient RSA factoring algorithm, would a company or government entity be willing to purchase it? What factoring time would be considered fast, months, days, hours, minutes? ...
- 11
0
votes
0
answers
34
views
Finding square roots in $QR_{n}$ when its order has a small factor
I am stuck at a homework problem to find the square root of a quadratic residue $b$ in $Z_n$ ($n$ is not a prime). Currently, I have figured out that there exists a number $a \in Z_n$ such that $a^2 \...
- 1
1
vote
0
answers
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 ...
- 11
2
votes
0
answers
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
1
answer
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
3
votes
1
answer
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)...
- 159
7
votes
0
answers
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
1
answer
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
4
votes
1
answer
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 ...
- 43
0
votes
0
answers
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
3
votes
1
answer
351
views
Time Complexity of RSA Trial Division
I'm having trouble understanding how time complexity of trial division is exponential.
If it takes $\sqrt n$ tries to factor $n$ in the worst case scenario then time complexity is $\mathcal{O}(\sqrt n)...
- 33
1
vote
1
answer
97
views
Non probabilistic algorithm : Given secret key $d$ we can factorize $n$ assuming $e$ is small
I read in an introduction to a paper that if $e$ is small enough and we were given secret key $d$ in RSA, then there is an efficient deterministic algorithm to factorize $n$. I've searched about that ...
- 173
18
votes
3
answers
6k
views
Quantum Computing Used to Break RSA by "fixing" Schnorr's Recent Factorization Claim?
There is a claim by Chinese researchers making the rounds (Schneier's blog here) that RSA can be broken by Quantum Computers. The paper is on arXiv.
Wading through the discussion in Schneier's blog, ...
- 23.1k
2
votes
1
answer
577
views
RSA: exploiting consecutive primes
It's given 2 plaintexts $m_1$ and $m_2$, and 5 different values of $n\quad\{n_1, n_2, n_3, n_4, n_5\}$ which are generated as follows:
$n_1$ is a a product of two relatively small 128-bit $p$ and $q$ ...
- 21
1
vote
1
answer
183
views
Does it weaken a RSA modulus to publish a generator of a small subgroup?
Let $n = P\cdot Q$ be the product of two safe primes $P = 2p+1$ and $Q=2q+1$.
Let $g$ be a generator of $C_{p} \subset \mathbb{Z}_n^*$, the multiplicative subgroup of order $p$. In other words, $g^p = ...
- 361
0
votes
1
answer
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.
- 1
0
votes
0
answers
36
views
How to factor $n = p.q$, where $p,q$ are primes, knowing a multiple of $\mathrm{lcm}(p-1, q-1)$? [duplicate]
I was reading this post https://senderek.com/SDLH/ about Shamir's hash function, which is defined as follows:
Let $p,q$ be positive prime integers and let $n=p\times q$. Let $\ell = \mathrm{lcm}(p-1, ...
- 477
1
vote
0
answers
45
views
Is it secure if I disclose an element equals 1 modulo p in Zn?
Let $n = pq$, $p,q$ are two large primes, then $\mathbb{Z}_n^*\cong \mathbb{Z}_p^* \times \mathbb{Z}_q^*$. We disclose $n$ and keep $p, q$ secret. Is it secure if we disclose a random element $a$:
$a\...
- 519
7
votes
1
answer
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
2
votes
1
answer
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
0
votes
2
answers
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
0
votes
0
answers
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 ...
2
votes
1
answer
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 ...
0
votes
0
answers
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 ...
3
votes
1
answer
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
0
answers
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
2
votes
1
answer
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
9
votes
1
answer
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
2
votes
1
answer
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
2
votes
0
answers
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
2
answers
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 ...
- 425
1
vote
0
answers
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
1
answer
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
0
votes
1
answer
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
3
votes
2
answers
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 ...
- 39
2
votes
1
answer
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
1
answer
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
1
answer
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
3
votes
1
answer
152
views
Can Shor's algorithm factor over the gaussian integers?
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 ...
- 45