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.

43 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
15
votes
0answers
258 views

Fewest qubits required for the discrete logarithm problem and integer factorization

According to a paper from 2002, the most efficient circuit to factor an $n$-bit integer requires $2n+3$ qubits and $O(n^{3}\lg(n))$ elementary quantum gates, assuming ideal qubits. Later on, according ...
11
votes
0answers
634 views

RSA factorization with special primes

Suppose that primes for RSA modulus are generated using formula: $P_i(x,y) = \operatorname{next\_prime}(x^{z_i}+y^{z_i}) = x^{z_i}+y^{z_i}+d_i$ where $x,y$ are unknown random numbers with size 128 ...
8
votes
0answers
95 views

Hardness of iterated squaring in Pailler group

The (computational) problem of iterated squaring (IS) in the RSA group is defined as follows, where $\leftarrow$ denotes sampling uniformly at random: Input: $(N,x,T)$, where $N$ is the RSA modulus, $...
8
votes
0answers
168 views

Time-memory tradeoffs in Shor's algorithm

Can a quantum computer with insufficient qubits to factor an integer of a given size make any progress in factoring it? For example, what if a quantum computer is only one qubit short of what is ...
6
votes
0answers
173 views

What are the theoretical memory requirements for these factoring algotihms?

Given an $n$ bit integer quadratic sieve takes $L(\frac12,1+o(1))$ time and number field sieve takes $L(\frac13,1.922)$ time where $L$ notation is given in https://en.wikipedia.org/wiki/L-notation. ...
6
votes
3answers
278 views

Decrypting small integers under RSA

Let $(n,e)$ be an RSA public key. Suppose $c = m^e \pmod n$, where $c>1$ is a very small integer. For concreteness, say $c=2$ or $c=4$. Is it hard to find $m$ under the RSA assumption (or any of ...
5
votes
0answers
136 views

Variant of Pollard rho using small factors of p - 1

Given an integer $N$ to factor which is divisible by some prime $p$, suppose you know (or guess) that $p - 1$ has a few small factors, e.g. $3, 2^2, 5$. Define $B$ as a product of small prime powers ...
5
votes
0answers
1k views

How does the Number Field Sieve find the target number for Diffie-Hellman?

I have read some papers relating to the Number Field Sieve, but I could not figure out how this algorithm helps in Logjam, or even what is meant by the number field. What is this? What is meant by ...
4
votes
0answers
230 views

Is the matrix step of GNFS still the hardest part?

When the factorization of RSA-768 was announced in December 2009: the sieving took about 24 months and the matrix step took 119 days (4 months). So sieving took about 6 times as long. This is despite ...
4
votes
0answers
83 views

Computing cost for a trillionaire to compute GNFS in RFC 3766

RFC 3766, Section 4.1 discusses picking $n$ to achieve some target cost for employing the GNFS, i.e., $T$ is known and $N$ is unknown in the below equation: $$T = \kappa \cdot \exp{\left(c \cdot (\ln{...
4
votes
0answers
155 views

Are analog quantum computers a threat to RSA and DLP?

We already know that D-WAVE's "quantum computers" can't really run the Shor's algorithm, because the way they're built doesn't qualify them as universal quantum computers. Now researchers actually ...
3
votes
0answers
57 views

Multi-users RSA problem

Rivest and Kalisky's RSA problem considers various notions on security of the RSA One-Way Trapdoor Permutation. They do it only from the perspective of a single user. What's the state of the art in ...
3
votes
0answers
61 views

Subexponential algorithms that apply only one of factoring and discrete logarithm?

Shor (quantum polynomial), Number Field Sieve (subexponential), Pollard rho (square root) all have both factoring and discrete logarithm over $\mathbb F_p^*$ variants. What are the subexponential ...
3
votes
0answers
82 views

Bounds on failure probability for universal exponent method?

The following definition is from Trappe and Washington, "Introduction to Cryptography with Coding Theory". Given a number $n$ and an integer $r > 0$ such that $a^r \equiv 1 \pmod{n}$ for all ...
3
votes
0answers
113 views

Reduction from integer factoring to computational Diffie Hellman

The computational Diffie Hellman (CDH) problem for ${\mathbb{Z}}^*_p$ is given a prime $p$, a generator $g$ of ${\mathbb{Z}}^*_p$, and a pair $(g^i, g^j)$ to compute $g^{ij}$. The value $g$ is called ...
3
votes
0answers
106 views

RSALib prime generation - derive number of primes

I'm working on factorizing a ~450 bit key that I know has been generated with RSALib and thus is vulnerable to ROCA. Now reading the original paper, I can see that the primes are generated in the ...
3
votes
0answers
441 views

RSA - factorizing $N$ to get $p$ and $q$

I need to decrypt a message encrypted using RSA. I only know the public keys $n$ and $e$. I need to get the private key $p$ and $q$ in order to get the decryption exponent $d$. Now to do so, I know ...
2
votes
0answers
38 views

Possibility of computing a and b values from the ciphertext?

Using paillier encryption, $N$ is the product of two large prime numbers, $s$ is sampled randomly from $Z_{N^2}$ we get $ C \leftarrow g^ms^N \bmod N^2 $ where $g=1+N$, By multiplying the cipher $c$ ...
2
votes
0answers
91 views

Recursive RSA encryption

I have a ciphertext $C$ encrypted with public key $pub_C$, which contains ciphertext $B$ and $pub_B$, $$C= E_{pub_C}(B\mathbin\|pub_B)$$ Ciphertext $B$ is encrypted with $pub_B$ and contains $pub_A$ ...
2
votes
0answers
148 views

Efficient way of knowing large factors of $\phi(n)$ given small prime factors and $n$

Knowing large prime factor$(r > n^{1/4})$ of $\phi(n)$ can easily factorize n and hence learn $\phi(n)$. If we have knowledge on all small prime factors $(2< r_i << n^{1/4})$ of $\phi(n)$...
2
votes
0answers
29 views

What are SNFS-safe limits for an RSA moduli optimized for simple modular reduction?

I consider $n$-bit RSA moduli $N$ having high-order bits starting by with $k$ bits at 1, then $k$ bits at 0, then $m-2k$ bits at ...
2
votes
0answers
63 views

Are there special techniques to factor numbers of this form?

Suppose $N=p^2rq$ where $p,r,q$ are primes and $r,q$ have equal bits with roughly $(\frac14-\epsilon)\log_2N$ bits while $p$ has roughly $(\frac14+\epsilon)\log_2N$ bits is there a special technique ...
2
votes
0answers
38 views

Are there UFDs where the factorization problem is difficult but finding irreducibles is cheap?

Factorization of integers is hard, but finding irreducibles is expensive. Is there a ring where factorization is assumed hard but finding irreducibles is much cheaper than over $\Bbb Z$? It could ...
1
vote
0answers
75 views

Where is factoring if discrete logarithm is broken?

Assume given $g^X\equiv h\bmod p$ where $g$ is of order $\frac{\lambda(p)}2$ where $\lambda(p)$ is Carmichael Lambda function applied to prime $p$ (so $2$ is invertible in exponent) we can compute $X$ ...
1
vote
0answers
38 views

How large a product out of 3 close-by factors need to be to avoid factorization?

For encryption a prime $P = 2 \cdot Q \cdot R \cdot S +1$ was used. An adversary want to solve the discrete log problem $m \equiv g^i \bmod P$. For this he want to use the Pholig-Hellmann algorithm. ...
1
vote
0answers
25 views

Help with next step in the Quadratic Sieve

So I am at the same step as someone from math.stackexchange but he never recieved an answer so I will copy-paste his question here: Say, for N = 90283, I compute bound 𝐡=𝑒(12+π‘œ(1))(ln(𝑛)ln(lnπ‘›βˆš))...
1
vote
0answers
36 views

If they exist a relation between decisional Diffie-Hellman assumption and composite decisional residuosity assumption

From the cryptographic hardness assumptions, we have DDH and CDR assumptions. It is known that the composite decisional residuosity assumption is related to a factoring problem, while the DDH is ...
1
vote
0answers
115 views

Lower bound for the size of prime factors?

We all know classic RSA and that we should pick moduli of at least 2048-bit length to get decent (112 bit) security. Now there's also multi-prime RSA, which can yield significant speed-ups using the ...
1
vote
0answers
22 views

Use of elapsed execution time as a variable input

Given that, with a significant number of decimals, it may be difficult to predict elapsed execution time of a piece of code, despite having knowledge of exact hardware and software specifications; is ...
1
vote
0answers
138 views

Is the half-homomorphic property of RSA a problem for blind RSA signatures?

For blind RSA signatures, is it problematic that RSA is half-homomorph? Take a scenario where blind RSA signatures are used for something like a voting procedure or this proposal: Lots of people, ...
1
vote
0answers
378 views

Determine the iteration times using Pollard's rho Method for factoring

Let's say, we have a large number $n=181937053$ and $f(x)=x^2+1$. And also we know that $n=12391 \times 14683$. The problem is that ,using Pollard rho method, can we find the algorithm iteration ...
1
vote
0answers
122 views

Generating Polynomials for the MPQS

I'm going to try and eventually factor RSA-100, but my current QS needs a lot of improvement, so I'm going to try and switch over to the MPQS. I'm a bit confused as to how the MPQS works, which is ...
1
vote
0answers
250 views

Quadratic Sieve Bottleneck, Multiple Polynomials an option?

After my failed attempt at trying to implement the ECM, I started working on the quadratic sieve. It works, but the bottleneck is finding smooth values over the factor base. The way I implemented it ...
0
votes
0answers
38 views

Generalization of Bezout Identity for Polynomials

Let $i \in \{1,\ldots, n\}$, $f_i(x)$ be a univariate polynomial, and $g(x) = \mathsf{GCD}(f_1(x), \ldots,f_n(x))$. According to Bezout identity, there exists $a_i(x)$ such that: $$\sum_{i \in [n]}a_i(...
0
votes
0answers
49 views

How do I retrieve a number which has been multiplied with a random number?

I have a 1024-bit number $n$ obtained by multiplying two 512-bit randomly generated prime numbers $p$ and $q$. Then there's $\phi = (p-1)(q-1)$, which is another 1024-bit number. I do not have $\phi$ ...
0
votes
0answers
41 views

Point-halving/solving quartic equations over the elliptic curve E(Z_N)/ring Z_N where N = pq

I am wondering whether there are any results/whether there is any knowledge about the following problem: Given a univariate polynomial (say, a quartic) equation defined over $\mathbb{Z}_N$, is it ...
0
votes
0answers
58 views

Trivariate Coppersmith Implementation

Bivariate Coppersmith is standard package in math software with number theory support. Bauer and Antoine Joux introduced trivariate Coppersmith in https://www.iacr.org/archive/eurocrypt2007/45150361/...
0
votes
0answers
155 views

Brute force integer factorization - back of the envelope calculation

RSA-240, an integer with 240 decimal digits from the original RSA Factoring Challenge, has recently been factorized. According to the researchers, the factorization took a total of 900 core-years on ...
0
votes
0answers
44 views

Given a deterministic oracle that calculates square roots modulo n, factor n

When $n = pq$ where $p$ and $q$ are primes, we can generate random numbers until we get $a$ and $b$ such that $a^2 \equiv b^2 \pmod n$. This implies $n$ has some common factor with $a^2-b^2$, and then ...
0
votes
0answers
81 views

Yukel's Sieve - Factorization of Numbers into a Square Sieve

https://www.youtube.com/watch?v=liTTGeitpGQ https://www.youtube.com/watch?v=2nOwgiweyqc https://www.youtube.com/watch?v=rGwFsOG27DQ I came across these videos explaining a pattern that is found in ...
0
votes
0answers
62 views

RSA: security of LSB in The Generic Model of Computation

In this paper Maurer and Aggarwal showed that in generic model of computation breaking RSA is equivalent to factoring. It is also known that the LSB of an encrypted message is as hard as breaking RSA.(...
-1
votes
0answers
32 views

Applications utilizing either $\mathsf{RSA}$ or Diffie-Hellman but not together

What are the applications which utilize Only $\mathsf{RSA}$ but not Diffie-Hellman (applications which can be rendered useless by breaking $\mathsf{RSA}$ alone)? Only Diffie-Hellman but not $\mathsf{...
-1
votes
1answer
154 views

Integer Factorisation

If I have a set of numbers of the form $\{ {kp+r}:k\geq0\}$ with p a prime or product of primes k large in $\in Z^+$ and r fixed, is it computationally feasible to find a factorisation for any one ...