@article{ART001898121},
author={Sang-Un, Lee},
title={A 2kβ Algorithm for Euler function φ(n) Decryption of RSA},
journal={Journal of The Korea Society of Computer and Information},
issn={1598-849X},
year={2014},
volume={19},
number={7},
pages={71-76}
TY - JOUR
AU - Sang-Un, Lee
TI - A 2kβ Algorithm for Euler function φ(n) Decryption of RSA
JO - Journal of The Korea Society of Computer and Information
PY - 2014
VL - 19
IS - 7
PB - The Korean Society Of Computer And Information
SP - 71
EP - 76
SN - 1598-849X
AB - There is to be virtually impossible to solve the very large digits of prime number p and q fromcomposite number n=pq using integer factorization in typical public-key cryptosystems, RSA.
When the public key e and the composite number n are known but the private key d remainsunknown in an asymmetric-key RSA, message decryption is carried out by first obtaining φ(n)=(p-1)(q-1)=n+1-(p+q) and then using a reverse function of d=e-¹(modn)). Integerfactorization from n to p,q is most widely used to produce φ(n), which has been regarded asmathematically hard. Among various integer factorization methods, the most popularly used is thecongruence of squares of a² ≡b²(modn), a=(p+q)/2, b=(q-p)/2 which is more commonly used then n/p=q trial division. Despite the availability of a number of congruence of scares methods,however, many of the RSA numbers remain unfactorable. This paper thus proposes an algorithmthat directly and immediately obtains φ(n). The proposed algorithm computes 2kβj≡2t(modn), 0≤ i ≤ γ-1,k=1,2,⋯or 2kβj=2βj for 2j≡βj(modn),2 γ-1＜n＜2γ, j=γ-1,γ,γ+1 to obtain thesolution. It has been found to be capable of finding an arbitrarily located φ(n) in a range of n-10 ⌊√2⌋＜ φ(n) ≤ n-2⌊√2⌋ much more efficiently than conventional algorithms.
KW - Euler's totient function;integer factorization;modular exponentiation;discrete logarithm;collide
DO -
UR -
ER -
Sang-Un, Lee. (2014). A 2kβ Algorithm for Euler function φ(n) Decryption of RSA. Journal of The Korea Society of Computer and Information, 19(7), 71-76.
Sang-Un, Lee. 2014, "A 2kβ Algorithm for Euler function φ(n) Decryption of RSA", Journal of The Korea Society of Computer and Information, vol.19, no.7 pp.71-76.
Sang-Un, Lee "A 2kβ Algorithm for Euler function φ(n) Decryption of RSA" Journal of The Korea Society of Computer and Information 19.7 pp.71-76 (2014) : 71.
Sang-Un, Lee. A 2kβ Algorithm for Euler function φ(n) Decryption of RSA. 2014; 19(7), 71-76.
Sang-Un, Lee. "A 2kβ Algorithm for Euler function φ(n) Decryption of RSA" Journal of The Korea Society of Computer and Information 19, no.7 (2014) : 71-76.
Sang-Un, Lee. A 2kβ Algorithm for Euler function φ(n) Decryption of RSA. Journal of The Korea Society of Computer and Information, 19(7), 71-76.
Sang-Un, Lee. A 2kβ Algorithm for Euler function φ(n) Decryption of RSA. Journal of The Korea Society of Computer and Information. 2014; 19(7) 71-76.
Sang-Un, Lee. A 2kβ Algorithm for Euler function φ(n) Decryption of RSA. 2014; 19(7), 71-76.
Sang-Un, Lee. "A 2kβ Algorithm for Euler function φ(n) Decryption of RSA" Journal of The Korea Society of Computer and Information 19, no.7 (2014) : 71-76.
