Calculate Euler’s Totient (φn) using the Extended Euclidean Algorithm.
Description
RSA relies on the difficulty of the factorisation of the modulus N. If the primes can be found then we can calculate the Euler totient of N and thus decrypt the ciphertext. Given N = p*q and two primes: p = 857504083339712752489993810777 q = 1029224947942998075080348647219 What is the totient of N?Solution
p = 857504083339712752489993810777 q = 1029224947942998075080348647219 N = (p-1)*(q-1)
#882564595536224140639625987657529300394956519977044270821168
Extended Mathematics
\(de - y(\phi(n)) \equiv 1 \pmod{\phi(n)}\)
$882564595536224140639625987657529300394956519977044270821168 = $ $13466661512370479891353372715527553906876367852923451955*65537 + 46333$
$65537 = 1*46333 + 19204$
$46333 = 2*19204 + 7925$
$19204 = 2*7925 + 3354$
$7925 = 2*3354 + 1217$
$3354 = 2*1217 + 920$
$1217 + 1*920 + 297$
$920 = 3*297 + 29$
$297 = 10*29 + 7$
$29 = 4*7 + 1$ (GCD: 1)
$1 = 29 - 4*7$
$= 29 - 4*(297 - 10*29) = 41*29 - 4*297$
$= 41(920-3*297) - 4*297 = 41*920 - 127*297$
$= 41*920 - 127(1217 - 1*920) = 168*920 - 127*1217$
$= 168(3354 - 2*1217) - 127*1217 = 168*3354 - 463*1217$
$= 168*3354 - 463(7925 - 2*3354) = 1094*3354 - 463*7925$
$= 1094*(19204 - 2*7925) - 463*7925 = 1094*19204 - 2651*7925$
$= 1094*19204 - 2651*(46333 - 2*19204) = 6396*19204 - 2651*46333$
$= 6396*(65537 - 1*46333) - 2651*46333 = 6396*65537 - 9047*46333$
$= 6396*65537 - 9047*(882564595536224140639625987657529300394956519977044270821168 - $ $121832886702415731577073962957377780195510499965398469843281*65537)$ $= 65537 - 9047*882564595536224140639625987657529300394956519977044270821168$
$1 = 121832886702415731577073962957377780195510499965398469843281*65537 - 9047*$ $882564595536224140639625987657529300394956519977044270821168$
\[d = 121832886702415731577073962957377780195510499965398469843281\]Verification
1 == 121832886702415731577073962957377780195510499965398469843281*65537 - 9047*882564595536224140639625987657529300394956519977044270821168
#True
