Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [factoring]

The tag has no usage guidance.

8
votes
0answers
73 views

Is this paper's technique for factoring RSA 2048 with noisy qubits realistic?

A paper titled How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits has just come out which proposes a technique to factor RSA keys with moduli up to 2048 bits with a design ...
0
votes
1answer
45 views

How many iterations for Pollard's $p-1$ with $p = r^k + 1$ for prime $r$?

$p$ and $q$ are large primes. What is the lowest upper bound for the number of iterations for Pollard's $p-1$ algorithm for factoring $N = pq$, provided that $p = r^k + 1$, for a prime $r$, and $r^k + ...
-1
votes
1answer
69 views

Is there a fast way to solve $k = n \cdot g^a \mod P$? (get $a$ for unknown $n$)

Would a factor besides the normal discrete logarithm problem increase or decrease the solving time? $k = n \cdot g^a \mod P$ with given $k,g,P$ and the knowledge $P= 2 \cdot N \cdot f+1$, while $...
0
votes
1answer
28 views

Which is the fastest way to find a member of a subgroup with known size modulo prime $P$, with know factorization of $P-1$?->$x$ with $x^s \mod P = 1$

Assuming you know the factorization of used prime $P-1$ $P-1 = s \cdot f_2\cdot f_3...f_i$ Now you want to find a member of a subgroup $\mathbb{Z}_s$. This means any $x$ with $x^s \equiv 1 \mod P $ ...
4
votes
3answers
264 views

Can Shor's algorithm factor multi-prime numbers?

I know that Shor's algorithm can factor semi-primes ($N = p \times q \space, \{p, \space q \in \Bbb{P} \space \vert \space p, \space q \gt 0 \} $). Assuming that all prime numbers are so large that ...
2
votes
2answers
90 views

Compute discrete logarithm mod $n=p \times q$ knowing factorisation

I read in a document that for a given $n = p\times q$ ($p$, $q$ primes), if you know $p$ and $q$ then you can easily solve the discrete logarithm problem, i.e. for fixed $a,b$, you can find $x$ such ...
6
votes
1answer
135 views

About integer factorization

Let $N=pq$ where $p$ and $q$ are safe primes. If the adversary knows the inverse of $p$ mod $q$ and the inverse of $q$ mod $p$, can this help him factor $N$ or break the textbook RSA?
2
votes
1answer
38 views

Lenstra's ECM Algorithm - field requirement

In Lenstra's ECM algorithm, $\#E(\mathbb{F}_{p})$ is required to have small prime factors. Why is this so? I understand that the p-1 method is efficient for factoring N with small factors. The ECM ...
3
votes
0answers
57 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 ...
8
votes
3answers
3k views

What is the fastest integer factorization to break RSA?

I read on Wikipedia, the fastest Algorithm for breaking RSA is GNFS. And in one IEEE paper (MVFactor: A method to decrease processing time for factorization algorithm), I read the fastest algorithms ...
2
votes
0answers
73 views

Is it possible to check if a number is the product of two primes without factorizing it?

I have a large number which I suspect may be a private RSA key (although its size, at 613 bits, seems a bit unorthodox). I have started to run a factorization algorithm on it, and after a few hours ...
7
votes
0answers
93 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 ...
3
votes
1answer
162 views

Fermat's factorization method on weak RSA modulus

Given a public key for RSA, I have extracted the modulus which looks like this: ...
1
vote
1answer
152 views

Factoring RSA weak modulus

Given a public key for RSA, I have extracted the modulus which looks like this : ...
0
votes
0answers
74 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 ...
-1
votes
1answer
57 views

Equivalence of cryptographic problems

Are integer factorization, discrete log and ECDH problems equivalent? I know that factorization and discrete log are equivalent but are one of those two problem equivalent with ECDH? Cand someone ...
3
votes
1answer
122 views

In RSA, what is $P[x \notin \mathbb{Z}_N^*]$

In the RSA problem, picking a message $x \in \mathbb{Z}_N \setminus \mathbb{Z}_N^*$ implies factorizing $N$. Since factorization with respect to the standard RSA generator is hard assuming the RSA ...
0
votes
0answers
39 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.(...
0
votes
1answer
39 views

Can we find the exact number given remainder of the numbers with mod m?

I have around 1500 numbers. The numbers $x_i$ are calculated as $x_i$=($p*t_i$) mod m. $p$ constant and same for all the numbers while $t_i$ are chosen randomly everytime. For example the given ...
3
votes
1answer
142 views

Upper bounds on difference of RSA primes

I was wondering whether given a concrete $N = p \cdot q$ whether we can find a upper bound on $\Delta = | p - q|$ as function of $N$ e.g, $N^\delta$, and thus test whether a given $N$ is vulnerable ...
13
votes
3answers
3k views

What happens for factoring algorithms if P=NP?

If someone ever demonstrates that P=NP, will it give us a polynomial factoring algorithm, or will it only tell us that such an algorithm exists, but we still have to find it?
0
votes
0answers
57 views

What is the computational complexity of Coppersmith's bivariate algorithm?

Coppersmith's original paper Finding a Small Root of a Bivariate Integer Equation; Factoring with High Bits Known says the algorithm to find bivariate roots under certain conditions runs in ...
1
vote
1answer
226 views

RSA finding p and q integer with condition

I'm given $N=p\,q$ and told that $44\,p\approx 17\,q$ (with the value given for $N$ some 49-digit integer 8124642558124642555899928124642555899924479992447). In ...
2
votes
0answers
53 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 ...
2
votes
0answers
122 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)$...
6
votes
1answer
488 views

Algorithm to factorize $N$ given $N$, $e$, $d$

I have an RSA public key (public modulus $N$ and public exponent $e$), and the private exponent $d$ of matching private key. How can I compute $p$ and $q$, the primes factor of $N$ ?
1
vote
1answer
50 views

Counting the number of binary solutions of quadratic system

I have a quadratic system of equations related to a balanced RSA modulus $n=pq$ (i.e. $\log p\approx\log q$), and I want to give an upper bound on the number of solutions. Indeed, let $p_i,q_i$ be ...
3
votes
0answers
65 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
1answer
197 views

Why would an efficient integer factorization algorithm render RSA insecure?

I know that RSA relies on the integer factorization problem: given two primes p and q, their product p . q is easy to compute. But not feasible (i.e., polynomial-time) an algorithm is known that could ...
3
votes
3answers
2k views

Can multiplication of two primes be seen as a strong cipher?

If we were define such a cipher: A reversible function that would accept a message $M$ and an initialization vector $\text{IV}_1$ $\operatorname{map}(\text{IV}_1, M)$ which can map an input $M$ to a ...
2
votes
0answers
26 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 ...
0
votes
1answer
105 views

How to find p,q in this problem?

Suppose \begin{align*} g^r &\equiv h \pmod N, \\ h^s &\equiv g \pmod N, \end{align*} for known $g$, $h$, $r$, $s$, and $N$, but not $\phi(N)$. Then $$g^{r\cdot s - 1} \equiv 1 \pmod N,$$...
14
votes
2answers
534 views

RSA factorization for special primes $p$ and $q$

I want to factorize the modulus $n = pq$ knowing that $p$ and $q$ are not random, but constructed based on integer numbers $a$ and $b$ as following ($a$ and $b$ are not given): $$p = a^2 + b^2, \...
3
votes
1answer
177 views

ROCA Implementation, Coppersmith Algorithm does not return roots

We are currently trying to reproduce the implementation of the ROCA-Paper. Therefore we calculated $M'$ from $M$ and $Order_M'$ from $Order_M$ to reduce the search space, but when we hand these values ...
0
votes
1answer
80 views

Williams' $p+1$ in tandem with Pollard's $p-1$?

Since the success of the $p - 1$ algorithm depends on $p - 1$ having "small" prime factors, or at least smaller than a reasonable smoothness bound, and Williams' $p + 1$ method has the same constraint ...
4
votes
2answers
169 views

How ROCA get the polynomial used with coppersmith

I'm trying to understand the ROCA attack on RSA from Matus Nemec et al. but I'm stuck on how they goes from the constraint they have expressed has: $$f(x) = x ∗ M' + (65537^{a'} \mod M') \pmod p$$ To ...
4
votes
0answers
216 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 ...
2
votes
2answers
72 views

Number of bits specified in standards implementation?

Currently deployed RSA and discrete logarithm implementation uses $1024$ to $2048$ bits. Hypothetically speaking if a crypto team produces a faster algorithm that moves current factoring and discrete ...
2
votes
2answers
645 views

RSA: Is possible get p and q from this d and n?

I have this algorithm and Im searching p and q: $n=p^2 * q $ $l=(p-1)*(q-1) / \gcd (p-1,q-1)$ $d\equiv l^{-1} \pmod n$ And the values are: For $n$: ...
2
votes
2answers
556 views

Recovering 3 private keys if Eve knows that the keys are shared prime numbers and knows their public keys, How would this be done?

okay so here is the original question: Alice Bob and Carl are generating public keys for RSA, but they are lazy and decide to share some of the work of generating prime numbers. They find 3 large ...
5
votes
1answer
375 views

RSA factorization knowing N, e=65537 and g=d*(p-17)

Having known the values for $N$ a large number, $e = 65537$ and another large number $g = d \cdot (p-17)$, how can I use that info to find out $p$ and $q$? I guess that have something to do with ...
2
votes
1answer
58 views

Can we efficiently factor if we are given a Pocklington certificate of one of the prime factors?

I recently read Squeamish Ossifrage's answer on generating RSA keys from (short) randomness where they make the following comment: (You might want to keep the certificate secret too.) As the ...
3
votes
2answers
179 views

Why does TWINKLE use light instead of current?

TWINKLE is a device devised by Adi Shamir to optimize the sieving step of GNFS. It consists of a cylinder, at the bottom of which are LEDs corresponding to factor base primes which blink with ...
2
votes
1answer
304 views

Factoring RSA-129 with a personal computer today

I have read the history of the RSA-129 challenge, and now I would like to know if it would be possible to factor RSA-129 with a single "average" personal computer, today. Has someone tried to do this ...
1
vote
1answer
398 views

Finding the first few digits of p and q

Is there a way to find out the first few digits of the factors of the RSA numbers (RSA-1024 or RSA-2048)? I do not want to get all the digits but only first 4-5 digits. My question is thus more ...
4
votes
1answer
118 views

Malicious DH parameters without using composite numbers [duplicate]

I know that it's possible to generate DH parameters that lead to it being easy to attack (e.g. trivial composite numbers), but is it possible to create a malicious parameter that is not a composite ...
-1
votes
1answer
671 views

Factoring a 512-bit number?

I want to know how to factor this number only given $n$ and $e$, I have tried to factorize $n$ using Fermat's little theorem and also tried primefac module in python (running for the past 4 days) but ...
-1
votes
1answer
132 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 ...
12
votes
0answers
171 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 ...
-1
votes
1answer
282 views

Factorisation for Coprimes of Large Numbers - RSA

What is the current conventional algorithm used to calculate factors of large numbers in order to determine if they are coprimes, or if there is a way to do it without calculating factors, what would ...