Skip to main content

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
6 votes
3 answers
415 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$ and that $e = 65537$. Is it hard to find $m$ under the RSA assumption (...
Sadeq Dousti's user avatar
  • 1,073
1 vote
1 answer
165 views

Algorithm for factoring a 30 decimal digit number

My professor has given me an RSA factoring problem as an assignment. The given modulus is 30 decimal digits long. I have been searching a lot about factoring algorithms. But it has been quite a ...
DumpDaCode's user avatar
0 votes
1 answer
253 views

Prime Factorization in RSA always leads to the product of two primes?

Lets prime factorize $30$: $$30 = 3 \cdot 10 = 3 \cdot 2 \cdot 5$$ We see that the number $30$ is a product of $3$ primes. But in RSA, when factorizing huge numbers, we always seem to only get two ...
Kristian Francisco Milla Niels's user avatar
0 votes
1 answer
140 views

Factorization problem

Say, $X= a\cdot b$, where $(a, b) \in Z_q^*$ and $q$ is a large prime. If $X$ is given, then what is the complexity (or hardness) of finding $a$ and $b$? Note that, either $a$ or $b$ can be reused to ...
Naz's user avatar
  • 95
0 votes
0 answers
549 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 ...
Max's user avatar
  • 101
1 vote
0 answers
52 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. ...
J. Doe's user avatar
  • 453
1 vote
0 answers
31 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π‘›βˆš))...
aayush Lak's user avatar
3 votes
1 answer
1k views

RSA: If the least significant bits of the factors are leaked, what advantage is there in factoring N?

For $N=pq$, if the first $x$ least significant bits of both $p$ and $q$ are leaked. what is the advantage in factoring $N$? Does this give an advantage beyond simply lowering the number of bits we ...
chillsauce's user avatar
2 votes
1 answer
261 views

Modification of RSA using two inverses, one for P mod (Q-1) and one for Q mode (P-1), instead of inverse d mod [(p-1)(q-1)], more or less secure?

Lets say I have the following modified RSA scheme We choose two large primes P, Q, with additional restriction that these are relatively prime to (p-1) and (q-1) We choose N = PQ as public key We ...
ackbar03's user avatar
2 votes
1 answer
1k views

Msieve & Yafu - RSA Exponents and bruteforcing

I am a layman in regards to the math behind RSA (and in general, relatively), and my goal is to bruteforce a large quantity of 512-bit RSA keys. Having searched around, I see that msieve, yafu, and an ...
Acinomatnas's user avatar
1 vote
0 answers
118 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 ...
kawsaw's user avatar
  • 115
1 vote
1 answer
268 views

Show that $\text{FACTORING} \le_P \text{SQROOT}$

I tried to prove that $\text{FACTORING} \le_P \text{SQROOT}$ in a general setting, so $n = p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k}$. THEOREM:Let $n$ be a composite ...
3nondatur's user avatar
  • 617
0 votes
1 answer
172 views

If there is an algorithm A can calculate the modular square root of input n, How to use it to get prime factors?

Suppose you are given an algorithm $A$ which takes $y \in \{0, 1, \ldots , N βˆ’ 1\}$ as input, and outputs $x \in \{0,1,\ldots,N βˆ’ 1\}$ such that $x^2 \equiv y \pmod{N}$. Design an efficient, ...
Caren Lai's user avatar
0 votes
0 answers
89 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 ...
intingfeeder's user avatar
-1 votes
1 answer
1k views

Factoring 2048 bit number is easy?

my PC found a factor for (2^2048)-1 in under a second...so does that make RSA-2048 less secure right? i used prime 95. and actually i am kinda curious how it found a factor so fast? i can even factor ...
Omer Enes's user avatar
2 votes
0 answers
181 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$ ...
user avatar
4 votes
1 answer
231 views

Estimating the probability of sucess of Pollard's p-1

I'm trying to estimate the probability that Pollard's p-1 factorization in its two-stages variant finds a factor of an RSA modulus product of $k$ random $b$-bit primes, as a function of the bounds $...
fgrieu's user avatar
  • 142k
1 vote
1 answer
1k views

How do I interpret the CADO-NFS output for discrete logarithm calculation in GF(p)?

I'm using CADO-NFS to calculate discrete logarithm in a finite field GF(p). The problem is when I type ...
Gustavo Schwantz's user avatar
3 votes
1 answer
187 views

Attacking any one in many public keys

The problem of finding private key from public key is typically studied in the one-key setup: what's the expected cost of breaking one key (e.g. by factoring a public modulus, or solving a discrete ...
fgrieu's user avatar
  • 142k
7 votes
1 answer
541 views

When is factoring semi-primes thought to be hard?

In Lattice Cryptography, problems like LWE or SIS have relatively easy to specify distributions that are thought to be average case hard. I'm curious what specific distributions on semi-primes $(p,q)$ ...
Mark Schultz-Wu's user avatar
  • 13.5k
3 votes
2 answers
1k views

What is the efficiency of the new Crown Sterling semiprime factoring method?

In their press release a company called Crown Sterling describes they are working a paper that includes four different geometric and arithmetic methods for public key (semiprime) factorization and ...
maqp's user avatar
  • 61
1 vote
2 answers
789 views

Purpose of using a=2 in Pollard p-1 factorization method

The Pollard p-1 factorization method states if $\gcd(2^{B!}-1,n)=p$ where $p>1$ and $B$ bounds the prime factors of $p$, then $p$ is a prime factor of $n$. Shouldn't it be $\gcd(a^{B!}-1,n)$ for ...
pal's user avatar
  • 13
2 votes
1 answer
612 views

Pollard's $(p - 1)$ factorization method runtime

Wondering if anyone knows a good reference for Pollard's $p-1$ algorithm's runtime? I was looking on the Wikipedia page and the runtime cited there is $\mathcal{O}(B\cdot \log B\cdot \log^2 n)$. ...
Dead_Ling0's user avatar
3 votes
1 answer
137 views

General factoring and one-way functions

Let a function $f$ be one-way, if there exists a probabilistic polynomial time algorithm to find the preimage of $y = f(x)$ for uniformly chosen $x$ with non-negligible probability. Define the ...
Deepak K's user avatar
4 votes
1 answer
1k views

Elliptic Curve Discrete Log in a Composite Ring

Elliptic curves are usually defined over prime rings (fields), but what if we chose a ring of composite order? Let $n = pq$ for $p,q$ large primes. Say I have elliptic curve $y^2 = x^3 + ax + b$ over ...
abrahimladha's user avatar
3 votes
0 answers
93 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 ...
Turbo's user avatar
  • 930
6 votes
1 answer
246 views

What is the best strategy to avoid getting even orders in Shor's algorithm?

I do understand Shor's algorithm wants the order of an element to be even so that it can use the factoring identity and find a non-trivial factor. But is there a relationship between safe primes and ...
user45491's user avatar
  • 409
5 votes
0 answers
233 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 ...
Seawaves32's user avatar
0 votes
1 answer
72 views

Factorization of the public value $N$ from the RSA cryptosystem

It is mentioned here that the public value $N=p*q$ of the RSA cryptosystem can be factorized if one of the factors is reused. Thus, if $N_1=p*q_1$ and $N_2=p*q_2$ and only $N_1$ and $N_2$ are known, ...
user avatar
0 votes
1 answer
1k views

What does it imply if in RSA pow(m, e, n) is same as the m

So, Let's assume we have n which is made up of 2 strong primes which cannot be factored & e which is textbook value of e ...
Stefan's user avatar
  • 11
13 votes
0 answers
857 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 ...
Kamil Pliszka's user avatar
6 votes
1 answer
113 views

Finding the period of a function with a single output qubit - impact on RSA

In this paper,May and Schlieper claim that one can find the period of a function $f()$ by embedding $h \circ f = h(f(x))$ for input $x$. This would have the immediate consequence of reducing the ...
Marc Ilunga's user avatar
  • 3,338
16 votes
1 answer
21k views

How long does it take to crack RSA 1024 with a PC?

Using an Intel Core i5 CPU, how long does it take to crack RSA using a key size of 1024 bit (generated using a secure key pair generation function)? Suppose for instance that we have thousands of ...
R1w's user avatar
  • 1,960
16 votes
1 answer
1k 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 ...
forest's user avatar
  • 15.3k
0 votes
1 answer
176 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 + ...
oleiba's user avatar
  • 377
-1 votes
1 answer
100 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 $...
J. Doe's user avatar
  • 453
0 votes
1 answer
74 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 $ ...
J. Doe's user avatar
  • 453
9 votes
3 answers
986 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 ...
AleksanderCH's user avatar
  • 6,462
2 votes
2 answers
1k 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 ...
Léo Colisson's user avatar
6 votes
1 answer
801 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?
Xiaopeng Zhao's user avatar
2 votes
1 answer
147 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 ...
edlothia's user avatar
  • 115
3 votes
0 answers
117 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 ...
Gregory J. Puleo's user avatar
9 votes
3 answers
10k 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 ...
user56036's user avatar
  • 101
6 votes
3 answers
2k 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 ...
Robert T. Tusk's user avatar
8 votes
0 answers
225 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 ...
forest's user avatar
  • 15.3k
3 votes
1 answer
1k views

Fermat's factorization method on weak RSA modulus

Given a public key for RSA, I have extracted the modulus which looks like this: ...
Mzem's user avatar
  • 75
2 votes
1 answer
937 views

Factoring RSA weak modulus

Given a public key for RSA, I have extracted the modulus which looks like this : ...
Mzem's user avatar
  • 75
0 votes
0 answers
88 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 ...
sagetrail midlandsteam's user avatar
-1 votes
1 answer
207 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 ...
mip's user avatar
  • 327
3 votes
1 answer
208 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 ...
user1868607's user avatar
  • 1,243

1 2
3
4 5
…
7