如何計算rsa私鑰的係數？

Question

我一直在試圖製作一個特定的rsa私鑰來解碼消息 我有所有的值（p，q，d，n，e，e1，e2）但我無法找到係數，因爲它說公式計算係數爲(q^-1 mod p)。但是當我以p=17和q=11爲例時，係數應該是14。但是當我用計算器計算時，coeffienct變爲(0.0909090909)。 請給我一個方法來計算係數或給我以下對的係數。

asn1=SEQUENCE:rsa_key 

[rsa_key] 
version=INTEGER:0 

modulus=INTEGER:1230186684530117755130494958384962720772853569595334792197322452151726400507263657518745202199786469389956474942774063845925192557326303453731548268507917026122142913461670429214311602221240479274737794080665351419597459856902143413 

pubExp=INTEGER:65537 

privExp=INTEGER:703813872109751212728960868893055483396831478279095442779477323396386489876250832944220079595968592852532432488202250497425262918616760886811596907743384527001944888359578241816763079495533278518938372814827410628647251148091159553 

p=INTEGER:878002287614711652531743087737814467999489 

q=INTEGER:511279233373417143396810270092798736308917 

e1=INTEGER:496787982169740923502343753899982600567297 

e2=INTEGER:80295249215525643071102598936432783036457 

coeff=INTEGER:? 

Answer 1

正如評論q指出^ -1模p是模反元素，你可以在此處詳細瞭解：https://en.wikipedia.org/wiki/Modular_multiplicative_inverse

它使用擴展歐幾里德算法進行計算，但是當模值像p原爲17然後在這種情況下，很容易由下式來計算模逆：

q^-1 mod p = (q^(p-2)) mod p（僅當p是素數）

現在的答案是：（11^15）模17 = 4177248169415651 MOD 17 = 14

還要注意的是，當gcd(p, q) != 1

我想您所查詢的係數是模塊化逆不存在：457212035379609309760218035812085381175325

它可能不正確，則可能需要調查furthur。