Some considerations concerning the selection of RSA moduli
An RSA modulus is a number of the form \(n=pq\) for \(p\) and \(q\) large primes. Two conditions are developed in the paper which the modulus must satisfy to prevent its factors from being found by simple algorithms. The first condition requires that a prime \(p\) selected as a factor must have a large index \(u_p\), where \(F_{u_p}\) is the smallest Fibonacci number which contains \(p\) as a divisor. Otherwise it is shown the iteration \(c\leftarrow c^{-1}+1\bmod n\), repeated until the gcd of \(c\) and \(n\) is greater than one, will yield a factor. For the second condition, let \(\varphi(n)\) denote Euler's phi-function and define \(\varphi^{\{j\}}=\varphi(\varphi^{\{j-1\}} (n))\), \(j=1,2,\ldots\). Define the power of two distance (ptd) of a number as \(\mathrm{ptd}(n)=\min\bigl\{j\mid\varphi^{\{j\}}(n)=2^i\), \(i=1,2,\ldots\bigr\}\). Then it is shown a prime \(j\) selected as a factor should have a sufficiently large value of \(\mathrm{ptd}(n)\). [For the entire collection see Zbl 0756.00008.]
This page was built for publication: Some considerations concerning the selection of RSA moduli
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4037473)
