Tag Info

2

The $p-1$ method works, by definition, whenever the multiplicative order of $a$ modulo $p$ is a divisor of $B$. If $B$ is a multiple of $p-1$, that is, the maximum possible multiplicative order of $a$, the probability is $1$. We are concerned, then, with the case where $B$ does not contain every divisor of $p-1$. If it contains none of them, the probability ...

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

1

I can only give a very simple-minded answer. In N. David Mermin's Quantum Computer Science: An Introduction, in his explanation of RSA encryption in Section 3.3, he says Efficient period finding is of interest in this cryptographic setting not only because it leads directly to efficient factoring (as described in Section 3.10), but also because it can lead ...

1

For an RSA modulus, Shor's algorithm will (with high probability) return a large factor of the multiplicative order of some base element modulo $N$. Various adjunct classical algorithms can use this to return the factors of $N$, but equally one could directly use this output to compute an effective decryption exponent without bothering to compute the factors....

Top 50 recent answers are included