So, as the title says, I found a way to generate near-collision moduli for arbitrary length moduli (1024, 2048, and even more), such that:
* N' / N are extremely close, close enough that the 50% most significant digits (yes) match
* The error N' - N is merely d / 2 digits long where d is number of digits of N
* The pair (P', Q') can be configured to match real world RSA standards, which is that P / Q should be 0.9 to 1.1 - AFAIK
* Polynomial time (under 10 minutes for 1024 bit modulus), and scales really well
Enough of the talk, here's a real world pair that I generated in C# using RSA class:
9825011933685332495569610785255381048421293669700949309396084348847980430426126260835358814931246295178749032557035569391915447653445155569710460885612502
10255344290431374537470222471291793084929597699052364248405892509907919879489421588916526559180947120156304313632119953078654657289306232887789064706476508
And here're the near collision results - at the moment I don't validate if `P'` and `Q'` are prime, but it's not hard anyway:
N^1/4: 100189182481809092361038528426361855261341770320190432895320201734826789699584
N: 100758880037539993243724184664987459354584768053616700399165210572913406871604174369845663082141081387031081468508417789258901087884667017312085333292271088243924148488484732128851135020315434206217665659822019814296078276798809845484746651632831686805098565229979142434100277552114462764795194816235854103016
N'^1/4: 100189182481809092361038528426361855261341770320190432895320201734826789699584
N': 100758880037539993243724184664987459354584768053616700399165210572913406871604174369845663082141081387031081468508417789258901087884667017312085333292271088242656936583441982526338014580119536834100304286657571463701652431584251093828599390042036754190173316676273490132972618314167059478645891981237442215250
Diff: 1267211905042749602513120440195897372117361373164448350594425845214558751656147261590794932614925248553705652301127659237947403286149302834998411887766
N'/N: 0.999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999987423322841911092829039360248244177958444815705470307853645924667015327862586812880561907516147905858834579769858937929894953950060896878924633588941312
Pair': (P'=9957837029722840161300251878824161474051186514433042970582024173929093400499943819826668605315793232526802630713777333059597339726752927478578416961618819, Q'=10118550819499046286031831603468734648033009283666096046839380411952598266804616117607111064389510710342114307780085950119314768947096400208911521950679750)
P'/Q': 0.9841169162814797
Pair: (9825011933685332495569610785255381048421293669700949309396084348847980430426126260835358814931246295178749032557035569391915447653445155569710460885612502, 10255344290431374537470222471291793084929597699052364248405892509907919879489421588916526559180947120156304313632119953078654657289306232887789064706476508)
Time Taken: 648 sec