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

331 questions
Filter by
Sorted by
Tagged with
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 ...
164 views

• 185
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 ...
• 46.1k
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 ...
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? ...
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 ...
1 vote
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 ...
• 46.1k
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?
• 99