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

296 questions
Filter by
Sorted by
Tagged with
7 views

### Find factors of N given RSA public key (e, N) and private key (d)

I am having some problems solving the following problem: find factors of N given RSA public key (e, N) = (11, 459703599527) and private key d = 125373708962. I calculated k = ed - 1/ N = 3, and Φ(n) = ...
214 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), ...
85 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?
62 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?
1 vote
74 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
87 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 ...
1 vote
84 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 ...
68 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 ...
407 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 ...
74 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?
1 vote
44 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$ ...
1 vote
59 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 ...
85 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 ...
1 vote
54 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 ...
161 views

434 views

### When is a large semiprime possible to factor?

Under which conditions is a large semiprime possible to factor? In particular, is the following 400-digit semiprime actually trivial to factor into primes? ...
1 vote
137 views

### Pollard's p - 1 - how do you set the bound & how do you set the base numbers

In Pollard's p-1 algorithm for factoring N, you try to find a L such that p - 1 divides L. Then you check $gcd(pow(a,L,N)- 1, N)$. If 1 < gcd < N, then you have found one of the factors. I have ...
1 vote
83 views

### Is there any relation between Decisional Composite Residuosity Assumption and Square roots in elliptic curve groups assumption?

We have DCRA and ECSQRT assumptions. ECSQRT: Square roots in elliptic curve groups over Z/nZ Definition: Let E(Z/nZ) be the elliptic curve group over Z/nZ. Given a point Q ∈ E(Z/nZ). Compute all ...
1 vote
142 views

### Why is factorial used in Pollard's $p - 1$ algorithm?

Why exactly do we use factorial for finding an $L$ which is divisible by $p - 1$? Pollard's algorithm is about B-powersmooth numbers & not B-smooth numbers. So where exactly does the factorial ...
1 vote
98 views

### Cost of factoring $u^2-v^2$ when $v\ll u$?

What's the approximate computational cost of factoring $N=u^2-v^2$ when $v\ll u$? Assume $u$ and $v$ are unknown integers, with $u$ large enough that $n$ has the size of an RSA modulus. I suspect ...
5k views

I'm working on a CTF. The challenge is to get the contents of an encrypted message given the ciphertext and the 2048-bit RSA public key. I did finally get the flag after a few hours, but I'm still not ...
1 vote
45 views

### Security game for factoring

this is probably a fairly simple request, but I have'nt been able to find it anywhere. A lot of cryptography schemes have security games associated with them. In the Book by Katz, a bunch of schemes ...
4k views

### Is it proven that breaking RSA is equivalent to factoring as of 2021?

I can't find any publication that proves this.
1k views

### Does the security of RSA come from just the carries in multiplication?

Although it's hard for me to find a reference, it's my understanding that if you calculate $N = pq$ using $GF(2)$ polynomial multiplication rather than ordinary multiplication, it is easy to factor $N$...
41 views

160 views

### How can the Number Field Sieve attack the discrete log in $\mathbb Z_p^*$ of DSA?

The Digital Signature Algorithm (DSA) uses $L$-bit prime $p$ and $N$-bit prime $q$ with $q| p-1$, i.e., $p = r\cdot q +1$ ( Schnorr group if $r>2$ and safe prime if $r=2$). In a way, the security ...
1 vote
### Does Coron and May's paper for deterministically reducing finding 𝑑 to factoring 𝑛 work with $\lambda(n)$?
Samuel Neves in his reply mentioned a method by Coron and May's 2004 paper for deterministically reduce finding 𝑑 to factoring 𝑛. As you all know, we are using $\lambda(n)$ everywhere now for RSA. ...