Skip to main content
New
Stack Overflow Jobs powered by Indeed: A job site that puts thousands of tech jobs at your fingertips (U.S. only). Search jobs

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.

Filter by
Sorted by
Tagged with
1 vote
0 answers
43 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{...
Yuri S VB's user avatar
1 vote
1 answer
71 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 ...
Omeglac's user avatar
  • 13
0 votes
0 answers
61 views

Difficulty of factoring large semiprime N if given a second value y = (p-1)*r, where r is a random large prime?

Lets say we have 2 public values: N and y $$ N = pq $$ $$ y = r(p-1) $$ Where p, q, and r are large primes, are different, have a large distance between them and are kept secret. I have three ...
block103's user avatar
2 votes
3 answers
162 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 ...
Hans Schmuber's user avatar
0 votes
1 answer
125 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 ...
user2284570's user avatar
1 vote
2 answers
416 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 ...
user2284570's user avatar
2 votes
1 answer
547 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 ...
user2284570's user avatar
3 votes
2 answers
122 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
Don Freecs's user avatar
-2 votes
3 answers
165 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? ...
steveK's user avatar
  • 11
0 votes
0 answers
33 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 \...
ark's user avatar
  • 1
1 vote
0 answers
57 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 ...
JohnBlack's user avatar
2 votes
0 answers
65 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$?
vfenux's user avatar
  • 21
1 vote
1 answer
105 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})^*$ ...
vxek's user avatar
  • 467
3 votes
1 answer
130 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)...
Kevin Stefanov's user avatar
7 votes
0 answers
284 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 ...
kodlu's user avatar
  • 22.6k
1 vote
1 answer
44 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 ...
ZhuJerry's user avatar
4 votes
1 answer
985 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 ...
The Yomster's user avatar
0 votes
0 answers
339 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 ...
bd55's user avatar
  • 33
3 votes
1 answer
335 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)...
ikeachairs's user avatar
1 vote
1 answer
95 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 ...
tonythestark's user avatar
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, ...
kodlu's user avatar
  • 22.6k
2 votes
1 answer
465 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$ ...
Alden Luthfi's user avatar
1 vote
1 answer
178 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 = ...
RobinLinus's user avatar
0 votes
1 answer
175 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.
alu vaja's user avatar
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, ...
vxek's user avatar
  • 467
1 vote
0 answers
44 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\...
Bob's user avatar
  • 509
7 votes
1 answer
601 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 ...
RobinLinus's user avatar
2 votes
1 answer
165 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$?
P00's user avatar
  • 25
0 votes
2 answers
106 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$? ...
P00's user avatar
  • 25
0 votes
0 answers
188 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 ...
shanzhuer's user avatar
2 votes
1 answer
562 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 ...
Alberico Lepore's user avatar
0 votes
0 answers
63 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 ...
Begoña Garcia's user avatar
3 votes
1 answer
197 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 ...
Raine's user avatar
  • 33
1 vote
0 answers
118 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 ...
Manc's user avatar
  • 59
2 votes
1 answer
702 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 ...
gram's user avatar
  • 31
9 votes
1 answer
269 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), ...
Christer's user avatar
  • 191
2 votes
1 answer
153 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?
Guest007's user avatar
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?
Turbo's user avatar
  • 910
1 vote
2 answers
130 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 ...
Dimitri Koshelev's user avatar
1 vote
0 answers
111 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 ...
J. Doe's user avatar
  • 453
1 vote
1 answer
129 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 ...
J. Doe's user avatar
  • 453
0 votes
1 answer
80 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 ...
J. Doe's user avatar
  • 453
2 votes
2 answers
513 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 ...
Lewis Baxter's user avatar
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?
Turbo's user avatar
  • 910
1 vote
1 answer
55 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$ ...
J. Doe's user avatar
  • 453
1 vote
1 answer
84 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 ...
anon's user avatar
  • 45
3 votes
1 answer
142 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 ...
anon's user avatar
  • 45
1 vote
1 answer
57 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 ...
Dominic van der Zypen's user avatar
3 votes
1 answer
274 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 ...
CryptoN00b's user avatar
2 votes
2 answers
205 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 ...
factorn's user avatar
  • 23

1
2 3 4 5
7