Tag Info

1

In order to create a private, public key pair we need to know the factorization of N. If we pick N as a random composite number we are no better off then an attacker. If we can find the factors so can the attacker. If we pick p and q as random numbers we will need to factorize them in order to find the factors of N, this may be easy or hard. But in the end ...

0

If you use existing factoring functions this can be solved in minutes for 200 bit random numbers. Factoring functions from Pari/GP for example. The algorithm below is not just factoring consecutive numbers. See below. Here is the general algorithm which has been converted into a working program: Generate W, a random 200 bit number sievelimit = 250 primelimit ...

1

The best method to find such numbers that I know of would be Algorithm 3 from Marc Joye's paper RSA Moduli with a Predetermined Portion: Techniques and Applications. In this case, taking $n=200$, $n_0=150$ and $\kappa'=188$. The initial problem requirements are aggressive and it is very possible that there are 200-bit values of $W$ for which no suitable semi-...

5

We want to factor $n=900$ using that $\varphi(n)=240$, and more generally factor $n$ knowing the Euler totient $\varphi(n)$. Leaving aside trial division, we can use three techniques Taking the Greatest Common Divisor of these two givens, which if $n$ is divisible by a square, and some rare other cases, will reveal a factor of $n$, and (once the GCD itself ...

Top 50 recent answers are included