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
-2 votes
1 answer
261 views

I can divide a very large integer - did I discover anything?

So I was sitting on an algorithm I thought up at school, and just decided to implement it. And it worked for what I wanted - but I don't know what this is worth. I broke apart a 2048 private key for ...
jackhammer's user avatar
0 votes
2 answers
164 views

complexity of iterative squaring in relation to factorization

I've run into a question dealing with the number of modular multiplications of O(n) bit numbers in the following situation: Given two n bit primes p,q define m=pq. ​ ​ ​ Choose some 'a' so that ​ $2&...
TheFooBarWay's user avatar
3 votes
1 answer
217 views

More Knowledge Integer Factorization

Say you have an integer that is produced by multiplying two random numbers $$x_1 = a \cdot b_1 \bmod(p-1)$$ where $a$ and $b_1$ are relatively prime to $p-1$ and $p$ being a large prime. Knowing $...
ChaosCoder's user avatar
3 votes
1 answer
216 views

What is the (classical) algorithm of choice for finding discrete logarithms in composite-moduli groups?

I've recently written an answer on how to find the factorization of a $n$ if we can find the order(s) of elements in the associated group $\mathbb Z_n^*$. This also lead me to Shor's algorithm which ...
SEJPM's user avatar
  • 46.1k
26 votes
2 answers
7k views

Why is it not possible to increase the size of RSA keys indefinitely?

According to this primer on elliptic curves by Ars Technica, when composite numbers get "too" big, they become easier to factorize with Quadratic Sieve and General Number Field Sieve. While this is ...
fast-reflexes's user avatar
-5 votes
1 answer
490 views

Factorization algorithm

I want to show that if we can compute order of element a mod n for all a and n with an efficient algorithm then there is an efficient algorithm for factoring numbers Can some one give me solution? ...
user3447371's user avatar
3 votes
0 answers
544 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 ...
William Lariviere's user avatar
1 vote
0 answers
141 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 ...
SEJPM's user avatar
  • 46.1k
-1 votes
1 answer
104 views

Why are cryptographic methods not vulnerable to randomized factoring algorithms?

Given that some public key cryptography systems are based on the difficulty of factoring large numbers, why are they not vulnerable to randomized factoring algorithms?
ramana_k's user avatar
4 votes
2 answers
2k views

Break RSA when modulus is of the form $N = pq$ with $|q^2 - p|$ small

I need some insight in how to break the following RSA problem: From an RSA encryption scheme you know that the algorithm that generated the RSA modulus $N$ always outputs moduli of the form $N = ...
user1868607's user avatar
  • 1,243
3 votes
1 answer
143 views

SNFS: Quantifying the "small" parameters?

The special number field sieve (SNFS) is an algorithm to calculate discrete logarithms and to factor numbers, given that the target has a special structure. Now, all ressources always say something ...
SEJPM's user avatar
  • 46.1k
4 votes
2 answers
1k views

o(1) in time complexity of number field sieve

It is well known that the time complexity of the number field sieve can be calculated by the formula $$\exp\big((C+o(1)) (\log n)^{1/3}(\log \log n)^{2/3}\big)$$ The constant C is known for the ...
user avatar
1 vote
0 answers
26 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 ...
user39783's user avatar
3 votes
1 answer
191 views

Proportion of RSA moduli factorable by NFS with less effort than average?

When applied to integers $N$ of comparable size, the Number Field Sieve is notoriously much faster if $N$ is known to be of the form $r^k\pm s$ with $r$ and $s$ suitably small integers, and $k$ an ...
fgrieu's user avatar
  • 142k
2 votes
0 answers
31 views

Factoring a semiprime with part of one of its factors [duplicate]

This is part of a question I asked on information security stack exchange which might be better suited here. I'm looking to implement a script in an ad-hoc scripting language with no crypto libraries,...
cardboard_box's user avatar
7 votes
2 answers
1k views

RSA: revealing the modulus factorization by choosing a bad message

I started reading the book Cryptanalysis of RSA and its variants by M. Jason Hinek and I stumbled upon a phrase that intrigued me: plaintext messages that are relatively prime to the modulus (i.e....
Vlad Calin's user avatar
4 votes
0 answers
91 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{...
GermaneDork's user avatar
1 vote
1 answer
419 views

justification for method to factorize n knowing RSA private exponent d

I know that knowing the private exponent $d$ corresponding to the private key $k_{pub}\langle n,e\rangle$ it is possible to efficiently factorize n. The procedure starts stating that: $ed -1 = s(p-1)...
ela's user avatar
  • 357
2 votes
2 answers
1k views

Prime factorization of 700 decimal digits number

I'm a newbie to encryption. If I create a number 'n' as a product of two prime numbers 'p' and 'q' with the following specifications: 'p' is a fully random prime with 300 decimal digits in length. 'q'...
Jan Lonner's user avatar
19 votes
1 answer
1k views

Quantum complexity of LWE

As per my understanding, LWE is quantum secure because there is no known quantum algorithm to solve LWE in polynomial time. Due to the reductions given by Regev et al., if there is any algorithm that ...
Rick's user avatar
  • 1,265
3 votes
0 answers
254 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 ...
SEJPM's user avatar
  • 46.1k
0 votes
1 answer
155 views

factorization of an integer $N$ that is in special format

Suppose $p_0$ and $q_0$ are known prime numbers and define $p_i$ and $q_i$ as follows: $$p_{i+1} = next\_prime(p_i^2 + q_i^2), \qquad i \ge 0$$ and $$q_{i+1} = next\_prime(2p_iq_i), \qquad i \ge 0$$ ...
Lisbeth's user avatar
  • 497
2 votes
1 answer
215 views

Highest prime factor that is Safe for a particular scheme

My question is how many bits of prime number is secure so that it cannot be factored from very large number? Until today how large prime factor is found in large number? Quantum computing find ...
vivek's user avatar
  • 197
1 vote
3 answers
3k views

Factoring an RSA modulus given high bits of a factor

I have {e,N,C} and part of p; can I get q from this example : ...
Dcoder's user avatar
  • 149
1 vote
1 answer
199 views

Factorization of RSA modulus using a qubic residue

Suppose that someone uses RSA with $n = pq$, exponent $3$, also $3$ divides $\varphi(n) = (p-1)(q-1)$ and $2$ different roots $y$ and $z$ of the equation: $$x \equiv c \ (mod \ n)$$ are known (for ...
brick's user avatar
  • 111
12 votes
3 answers
2k views

In the Quadratic Sieve, why restrict the factor base?

In the Quadratic Sieve, when factoring a number $N$, many descriptions and most implementations select as the factor base the set of small primes $p_j$ less than some bound $B$ restricted to having ...
fgrieu's user avatar
  • 142k
2 votes
1 answer
954 views

Sieving the sequence $x^2-n$ to recognize b-smooth numbers

I am currently programming the quadratic sieve and have several literature books / papers and will take an example out of [1] for my question: [1] An Introduction to Mathemtaical Cryptography by J. ...
Burak's user avatar
  • 183
6 votes
1 answer
2k 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 ...
Hamm's user avatar
  • 169
-2 votes
1 answer
307 views

Decrypting an RSA message given $a^2 \equiv 1 \pmod n$

I need help with a practice problem for an upcoming test. I've learned the answer to the problem is "well done", but don't know how to get there. Any help is greatly appreciated. Suppose that the ...
Steve's user avatar
  • 1
6 votes
1 answer
775 views

Understanding the Hidden Subgroup Problem specific to Integer Factorization

I've been reading about the Hidden Subgroup Problem (HSP), specifically trying to understand how it is related to the integer factorization problem. I've read What exactly is the impact of the hidden ...
Anthony Kraft's user avatar
0 votes
1 answer
555 views

In RSA. Why is $\phi(n)$ kept secret and $n$ is public?

I mean, $n$ can also be easily used to find the factors $p$ and $q$ right?
Kp23's user avatar
  • 17
4 votes
1 answer
101 views

How to prove that an integer is hard to factorize when sampled from a known distribution

Suppose that an $n$-bit integer $c$ has been randomly drawn from a distribution $\chi$, whose description is known. Is there a general method to check if this particular sampling helps factorize $n$? ...
Tal-Botvinnik's user avatar
4 votes
2 answers
659 views

Integer factorization still hard with Hamming weight hypothesis?

Consider the following problem: Factorize a $n$-bit integer $c$ knowing that it is the product of two integers with known Hamming weight $h$. Is there a way to prove that this is still hard? I have ...
Tal-Botvinnik's user avatar
3 votes
1 answer
205 views

Is there any IND-CPA secure stream cipher with a "standard" hardness assumption?

I've read our recent question: "One-time pad using RSA and Diffie-Hellman functions" which asks about the security of a particular way to convert RSA and discrete exponentiation into a stream cipher. ...
SEJPM's user avatar
  • 46.1k
2 votes
1 answer
199 views

What is the advantage of Pseudosquare?

Pseudosquares ,which are not square but Jacobi symbol are still 1, are used in some cryptographic algorithm. What is the advantage of them over the exact squares? If we used squares instead of ...
1214's user avatar
  • 21
3 votes
1 answer
4k views

Factoring large $N$ given oracle to find square roots modulo $N$

When $p$ and $q$ are distinct odd primes and $N = pq$, the points in $\mathbb Z_N^\ast$ have either zero or four square roots. A quarter of the points have four square roots; the rest have no square ...
Tom Corless's user avatar
5 votes
2 answers
1k views

Public key crypto without modular arithmetic?

This comment from Reddit math, in response to a statement about how people can communicate secrets to each other with a third party listening, has a very small, simple example of public key ...
mikemaccana's user avatar
0 votes
2 answers
205 views

How can prime factor of $q-1$ divide prime $q$?

In this paper - "A Subexponential Algorithm for the Discrete Logarithm Problem", author mentions (page 56), For each $p_l^{e_l} | q$ proceed.... $p_l^{e_l}$ is one of the prime factors of ...
Anurag's user avatar
  • 151
0 votes
1 answer
157 views

What is base of $\log$ in Subexponential Algo for DLP?

I am currently going through this paper - "A Subexponential Algorithm for the Discrete Logarithm Problem" by Leonard Adleman. On page 56, author mentions that Dixon's algorithm - Asymptotically Fast ...
Anurag's user avatar
  • 151
2 votes
2 answers
747 views

Collision free one way function

I was playing with a function that I think is collision free and uninvertible assuming the hardness of integer factorization. I am unfortunately not as skilled at math as I would like to be, and do ...
Ella Rose's user avatar
  • 19.7k
6 votes
2 answers
266 views

Effect of $L_n[1/4,c]$ integer factorization on RSA-2048

Using the L-notation, integer factorization of an integer $n$ has the best known complexity of $L_n[1/3,c]$ using general number field sieve. Would discovery of an algorithm with complexity $L_n[1/4,c]...
mhp's user avatar
  • 173
5 votes
1 answer
692 views

Proof of RSA security dependent on public key exponent

I am writing a (high-school) paper on the public key exponent's (in textbook RSA - no padding is discussed!) significance in terms of time and security. The time part is done; as for the security part,...
user9750060's user avatar
3 votes
2 answers
613 views

RSA and difference between factors

As I understand, for RSA $n = p \cdot q$. For the key to be safe enough from getting factored, $p$ and $q$ have to be far from each other. How far do they have to be? For example, if I have two $1024$-...
Momo's user avatar
  • 33
2 votes
2 answers
674 views

How can I factorize a 350 bit (106 decimal digits) number in two prime factors?

I have this large number: 1728098743723095094470726818328193358068864405124007684733613106475812450278961107574624070107782941006379 which is the multiplication of two unknown large prime numbers. I ...
poker's user avatar
  • 41
0 votes
1 answer
204 views

Checking for factor base

In algorithms like Dixon's factorization a factor base is used, which contains all primes below a bound. Then calculates $x^2 \mod n$, and then checks it is in factor base or not. Suppose $P$ is ...
hanugm's user avatar
  • 499
1 vote
1 answer
3k views

Time complexity of trial division

Suppose $n=pq$, where $p,q$ are prime numbers. Let $p ( \le q)$ be the smallest prime, then we know that $p \le \sqrt{n}$. In trail division, we check $n \mod i$ for the values of $i$ from 2 to $\...
hanugm's user avatar
  • 499
4 votes
1 answer
153 views

Adding two RSA private key

We've constructed a new private RSA key from two known private RSA keys $Priv_1$ and $Priv_2$ as follows: $$p = next\underline{}prime\left(\frac{Priv_1(p) + Priv_2(p)}{2}\right)$$ and $$q = next\...
Lisbeth's user avatar
  • 497
2 votes
1 answer
262 views

Factors of the group order to secure against Pohlig-Hellman

I am looking into the security of Diffie-Hellman and the discrete log in general. To make sure an attacker can not use Pohlig-Hellman to solve the discrete log quickly we need to make sure that the ...
Controlk's user avatar
0 votes
1 answer
73 views

Algorithm for factoring a number $n$ of a specific form given $n$ and $\varphi(n)$

Given the natural number $n$, which is in the form $p^2 \cdot q^2$ with $p$,$q$ prime numbers. Also $\varphi(n)$ is given. Describe a fast algorithm (polynomial time) that calculates $p$ and $q$. ...
Paris Lamp's user avatar
8 votes
1 answer
328 views

Blinding to mask private key operations

Blinding is often used to mask private key operations when the underlying problem is integer factorization. For example, it's used in both RSA and Rabin-Williams signature schemes. This presumes ...
user avatar

1
3 4
5
6 7