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.
321
questions
0
votes
0
answers
29
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
48
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
1
vote
0
answers
58
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$?
- 11
1
vote
1
answer
103
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})^*$ ...
- 445
3
votes
1
answer
96
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)...
- 139
7
votes
0
answers
193
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 ...
- 21.2k
1
vote
1
answer
42
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
966
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
315
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
290
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
92
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
5k
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, ...
- 21.2k
2
votes
1
answer
310
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
160
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 = ...
- 339
0
votes
1
answer
138
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
34
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, ...
- 445
1
vote
0
answers
43
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\...
- 499
5
votes
1
answer
544
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 ...
- 339
2
votes
1
answer
109
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
92
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
154
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
553
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
61
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
184
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
106
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
406
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
259
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
146
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
74
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?
- 908
1
vote
2
answers
121
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 ...
- 395
1
vote
0
answers
107
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 ...
- 573
1
vote
1
answer
118
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 ...
- 573
0
votes
1
answer
76
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 ...
- 573
2
votes
2
answers
492
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 ...
- 29
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?
- 908
1
vote
1
answer
52
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$ ...
- 573
1
vote
1
answer
79
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
133
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
1
vote
1
answer
56
views
Is $\mathbb{Z}_2[x]$-irreducibility in ${\bf P}$?
A fast alternative to conventional multiplication is the carry-less product. It works exactly in the same way as the multiplication on the countable set of binary polynomials $\mathbb{Z}_2[x]$. We can ...
3
votes
1
answer
232
views
Probability of choosing a base successfully in Pollard p-1 factorization method
In a problem about pollard p-1 factorization method, where $n=pq$.
We choose some random base $a$ , and an exponent $B$, where hopefully $p-1$ has small prime factors, and if so we hope to estimate $p ...
- 33
2
votes
2
answers
194
views
How much work to find such $n$?
Let $W$ be a random $200$ bit number. How much work would it take to find a semiprime $n=p_1\cdot p_2$ such that $p_1,p_2 > 2^{50} $ and $|W-n|<2^{12}$?
More generally, let $W_b$ be a random ...
- 23
1
vote
2
answers
329
views
Using Shor's algorithm to access RSA messages without factoring
Most of the time people forgot that the real aim of the adversary against encryption is accessing the message. For example, in the RSA case, we talk about the factoring of the modulus to reach the ...
- 47.6k
0
votes
1
answer
557
views
Rabin Cryptosystem: Chosen-Ciphertext Attack
I read in literature that Rabin Cryptosystem can be broken using chosen-ciphertext attack. It is described that after chosen ciphertext is decrypted attacker can factorize public key $n$ by using ...
1
vote
1
answer
357
views
What are those RSA Challenges, DES Challenges and RSA Factoring Challenges
Can someone explain the differences between the DES challenge, the RSA challenges, and the RSA factoring challenge? What were the aims?
I think the factoring challenge was to encourage research, the ...
- 11
2
votes
1
answer
695
views
Factoring a RSA modulus given parts of a Factor
e,N,c and around 2/3 of p are given and I need to get the whole p to decrypt c.
...
- 23
1
vote
1
answer
89
views
The significance of the field of the factor in Lenstra’s ECM
I am going through Lenstra's Elliptic Curve Factorisation from Silverman's Mathematical Cryptography book.
I have understood the algorithm itself, but unable to understand a specific point the book ...
- 2,169
1
vote
1
answer
223
views
RSA factorization knowing the form of p and q
I'm wondering if knowing the form of both factors (p and q) of a RSA modulus N is a significant help for factoring or not.
For instance:
p of the form 4k+3, so (p-3)%4 = 0
and q of the form 4k+7, so (...
- 11
2
votes
0
answers
80
views
What would be the safety requirements for the primes in $n=p \cdot q$ regarding the factorization?
Let it be $p, q \in \mathbb{P}$ with $p,q \in [2^{b-1}, 2^b]$ for some $b \in \mathbb{N}$ and $p \cdot q = n \in \mathbb{N}$. What would be the distance between $p$ and $q$ (as a function of b) so ...
- 53
2
votes
1
answer
248
views
Factoring RSA if prime p is used as the private exponent
I've got two 1024 bits primes $p,q$, and $n = p \cdot q$.
Now I know the result of $ c^{p} \bmod n = x$, also the value of $c$ is given, I wonder if it is possible to factorize $n$.
- 59
2
votes
1
answer
477
views
Quadratic Sieve: Is there a thumb rule for deciding how many numbers to sieve?
In the Quadratic Sieve algorithm, we first decide on a B & then look for B-smooth prime factors by sieving using a quadratic polynomial.
I can find a few formulas which help figure out how to ...
- 2,169