Some considerations concerning the selection of RSA moduli (Q4037473)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 177597
Language Label Description Also known as
default for all languages
No label defined
    English
    Some considerations concerning the selection of RSA moduli
    scientific article; zbMATH DE number 177597

      Statements

      Some Considerations concerning the Selection of RSA Moduli (English)
      0 references
      Some considerations concerning the selection of RSA moduli (English)
      0 references
      0 references
      18 May 1993
      0 references
      cryptography
      0 references
      factorization
      0 references
      RSA modulus
      0 references
      Fibonacci number
      0 references
      divisor
      0 references
      Euler's phi-function
      0 references
      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.]
      0 references

      Identifiers