こちらの続き。
残念ながら期待通りには暗号化できなかった。
E（公開鍵の片割れ）が間違っているのか、M（平文）が間違っているのか…

となると、N（=pq）を素因数分解するしかないだろう。
ある意味正攻法。しかし、3777ビットの整数の素因数分解…

できないよね…

やってみた。

なんと、できました！

なんと197で割り切れちゃいましたよ…

N = 765434576345637173823138479813768765238613741311236937264827654778277325473898928152422542515522536131313315113131436465191945461216494600604573790464767487277872182954748299792393745245635321521251762851642417215462185215216524128156631535133635135624373234146484945914624245144655937545243151552364728646254632586421653765268752146364216452966051582166316165298691556167867525411656512513466425667026216616514563466741256352312000214153442514256547456176523156416857441156514555136515571345216351461342355314575145551352534665275245434123524164512514854135513552515115617195661675681735681361373613725382416248275264278352381658327184562416554631567452166375415676516659156451553145235234613252553232516852127126451621572321315221367251321433642212341623226546564323221637261423214278263167424542351254254143654215461524423554259418149422453565065652624639606225635206461462565251661258214063232062267640333141325426372633225334823727365243212325634253834253324362370285630743325310023223052360452321456631647857143521514557163023223522423243624702260270285607962516432235723674724715613526215523165518237142314221623715637261634153471
p = 197
q = 3885454702262117633619992283318623173800069752848918463273236826285671702913192528692500215814835208788392462503205261244629164777748703556368394875455672524253158289110397460875095153531143764067267831734225468098792818351352914356125033173267183429565346366225811908196062158094700190584990617017079840843932145108739359214562193636366580979523104478001604899993358153136383377724144733570895561761554399068601845008838864732548224437327119361708362721708239372674403254601596726581297316473179449042346981292259622088083932311041854995550884083819872356017835291954901610130262313105257265793774688961332062173986113088083155626026317575718551429276406935915815616835833281479965204239769610419051941709909274753561530823966067113539346809307828489043772723586620930059072393011239991183590987524625656112404336119094032606874413290098591134848048998094617290485457900819606930211478468091691533311003250422037184905444838707283369174442858945815402303727174235341981145333722463502655954580509910261201175877447429043221102350371693007224586927422640965916791687900671247328298095003114346271691195524046407686404181297651074285043

このqが素数かどうかは不明。ミラー・ラビン素数判定法とかフェルマーテストとか、素数かどうかを推定することができる方法があるようだ。（「確実に素数である」というのではなくて、「おそらく素数だろう」というものらしい）

大きな数字nが素数であるかどうかの確率はほぼ1/log(n)だそうである。（ガウスの素数定理 https://tsujimotter.hatenablog.com/entry/2014/04/08/120132）
このqについて素数である確率を見積もってみると0.00038。約0.04%。おそらく素数ではないんじゃないかな？