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
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
0.8004498481750488
0 references
0.8004015684127808
0 references
0.7518094778060913
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