关于RSA加密方法不动点的注记

A Note on Fixed Points of a RSA System

设 n=p1 p2 … pk,其中诸 pi 是互不相同的素数 ,e是满足 (e,φ(n) ) =1的整数 ,φ(n) =(p1 - 1)… (pk- 1) .以RSA(n,e)表示以 n和 e为公开钥的 RSA公钥加密体制 .利用孙子定理 ,给出了计算 RSA(n,e)的与 n互素的 α阶不动点的方法 .以 T(n,e,α)表示这个加密体制的与 n互素的 α阶不动点的个数 ,记 S(n,e,K) =∏Kα=1T(n,e,α)1K,则log S(n,e,K ) =ω(n) log2 +1K∑p | n ∑q| p - 1 ∑rm| qlogr K (indge,rm- 1 (r - 1) )rm- 1 (r - 1) .其中 r是素数 ,g是模 rm 的一个原根 ,[x]表示 x的整数部分 .

Let n=p 1…p k, where p′ is are different primes, e be a positive integer satisfying (e,φ(n))=1, and φ(n)=(p 1-1)…(p k-1). By RSA(n,e) denote the RSA-ciphering system with n and e as its public keys. Using Sun Zi's theorem, a method to calculate the fixed point P′s of RSA(n,e), that (P,n)=1, is given. Let T(n,e,α) be the number of α-order fixed points P′s of RSA(n,e), that (P,n)=1, and S(n,e,K)=∏Kα=1T(n,e,α)1K, thenlog S(n,e,K)=ω(n)log2+1K∑p|n∑q|p-1∑rm|qlog rK(ind ge, r m-1(r-1))r m-1(r-1).where r is prime, g is a primitive root of mod rm, and [x] denote the integer part of x.