The end of RSA, Part 1

[R. Gerbicz]

Originally Posted by charybdis

Well yes, it does help that we already know 6 factors of F12

Yes, used those known factors, but how? I mean if M|N then we know only small squared residues mod M in the range of sqrt(M), but we need these residues mod N and not mod M. Ofcourse you can regard it mod N, but that gives only the boring average N/2 and not sqrt(N) for M<N.

[R. Gerbicz]

Originally Posted by LaurV

There are 90 numbers below 100 which are not squares, so you only need to find 91 relations** to factor every N by difference of squares. No (quadratic) sieve needed, and no linear algebra. Piece of cake. Show us a factorization of RSA1024.
...
**in fact you need much less, as they also contain cubes and other odd powers (2^3, 3^3, 2^5) and you can easily combine them to eliminate multiples of 2, 3, primes, etc., and also, not all the numbers under 100 are quadratic residues. This works like the birthday paradox, except the birthdays are taken from 100, not from 365. So, maybe around 10 relations will always be enough (probabilistic) to find two with the same birthday? (no calculation done, wild ass guess). Then apply difference of squares, to factor any number, of any size.

And with linear algebra would you need primepi(100)+eps=25+eps relations ?
OK, take my challenge factor my GRSA100 [G means Gerbicz], n=p*q number with 100 digits. You can use "your" method, and even algebra, but not QS, so use only the listed residues. For non-square i numbers in R[i] you'll see a number for that (R[i]^2)==i mod n and 0<R[i]<n/2. There are 90 such entries in the table.

n=5641726904028141775845201429406221159866034862174979444379946384606770562756851889104848796957610561;

R=[0,\
1724787299442916282530419476907188353251548036461272822934649404908504673348028719488713834536774342,\
359684321313109739256185919500775281026592821969952494851581538281575016488386915664780394119626941,\
0,\
2449981082504500819548338992168375924202065105032128305393163805191606193571705282348368987169527380,\
2358554243531504393621070602313350737057478207045090369281690466916102713438781277432402838555167448,\
390175394657631332943856025917481268727700364232394841683611192458295897247969190984259204525778169,\
2192152305142309210784362475591844453362938789252433798510647574789761216060794450127421127884061877,\
0,\
1156110835286181739623845909824134904515693395622957967328584010777191653653375457317216979673556745,\
1530890379806876412364407519863516906937805540243017153445939858655965011243048407589357924467375299,\
719368642626219478512371839001550562053185643939904989703163076563150032976773831329560788239253882,\
993656806500668237494066248981456477379136691528494083263722321278545019542666959390188581549404327,\
41972932252078733786411392193850739254125187826020868468159586398489932340822626329878684623034449,\
1238594643127537333600674043927013116281873323596573271248617344306328230783380352951595726936031450,\
0,\
721308171746071475783857447934200070077020502839056616282064146807928209508683200216759132027583550,\
467365005699392928253942998684656100111390752791160975575998169881256542712765730638707293347287535,\
1998083943647634022258404875194871979379024509508313973060671415004953353371852013664957487743129868,\
741764739019140136748523445069469311461904652110722833593618774223558175613441324408110822618555801,\
296250730824402777550881385555530865232856817203420454763807451552264858623296474827027625973028145,\
1413014649035063840681817226569368139480491808934360476500777887552681973328857294786522903055836857,\
1912109344392966499413722898366165729719564255121533445472315682586577978890003837485217050482802195,\
924618416965132988603060224779519685751078448084798705816565450774565135879289334240043119847275665,\
0,\
2104789956563449278016408845463001757977108977340341399931270577001039738099620093021636868685773019,\
1079052963939329217768557758502325843079778465909857484554744614844725049465160746994341182358880823,\
780350789315262665887712051834962537455400728464789683367222384916591794495938381968518409051556338,\
1920962314548187414404749956485035895526466368765695047719719735751835764099472200036846720588431522,\
1498817391180309345093813578116349292650239965171901018151796862258400687339680999507207270392910239,\
629415540979092824793178050152469660417992500734821938933676248961375207209872647421369427669502711,\
1257422293743523354276476478222532253140157283670111847358651235027248130635262988850006541189486807,\
1675897025662103484083299155488804441042032848315678452133728916474433559647867318455618463422816941,\
844935067414906843320080217809005094478562707841965081384460936529515279291725159118461763647338479,\
1358678784682613683223451395478262157189834280918551961822679376033128686768679094592686643715445381,\
0,\
2087449601798123095637386117853456241805100185145629298763245773975328426368149239773626358086115211,\
1672184719946396578002518224358803248216330082804822380109724679271933513717223609249697903099745586,\
819120670054020056849840239994777044216281311370178329721066482534580146238666409661934519865839185,\
2312221670572363479247691819648269809031386791245915934657168021554383307306750914634433959347113490,\
528460105714441456949830015923922478885927616317956741939086525891617548566856121908087769342470169,\
1431372653825483478531539537432955252788510461426583821223322109609262726223070851006524971281025086,\
1145852483499087529930900447334361713547713235082158600029310353113250184833992973531166573042992191,\
2579946144414388951116386389679187345990423781688945137488066667294840540270755073926132948022859963,\
1708216343485360682799815547098906612740160452921405471799545030968048017958263957940258164550971579,\
13928167618377028939953111263300574929007618532288397910298311607019491944052338856710892379176271,\
2558534590889096592428524893313015672665040363971525365351687435809929306279180089355968686258469215,\
1438737285252438957024743678003101124106371287879809979406326153126300065953547662659121576478507764,\
0,\
2659517310841702139038305474276500553474329542043594774086645744671017758773560180766128421231349412,\
733748737533186416746940643404616944321787134236974148782098799514794216886882565215389554635353268,\
1987313613001336474988132497962912954758273383056988166527444642557090039085333918780377163098808654,\
2710411845089475403253673116020303970708986578894735414427353679704693625010836950564380236914914290,\
1433935826566371405018010377533831051306399758960291663465125016141537577559491943192359718707891783,\
1489561332222776899743998807719740654391635622500884081130760240613288291561361597904450505329551640,\
83945864504157467572822784387701478508250375652041736936319172796979864681645252659757369246068898,\
647494529600298347376213570747206994181790595140394188873237192845969140043306206010015127190649168,\
1878024301997290884980507953343855813998348425948804765689008229024329777085193141031035108054544484,\
489244794713864057868751844974220947473363707460769543944426872605972334635157265674124119403749172,\
2477189286255074667201348087854026232563746647193146542497234688612656461566760705903191453872062900,\
2550677240251362573790947558322216257122857325584483624666130851777051922595615104484157105043429367,\
996203281872260629880091547041017586256942794887971591347487664162409318538956665804993167800620672,\
1170526183972893998831568077752443806183101092697184525050833577374887691743907572952777613577334507,\
0,\
194115772909817878221267000746315555794502589821824774096551343101305562885152788772256860288964661,\
1478310094942195803782320254171742162557020260286218938737245012228688017630800988889765826967916608,\
755762084644050345543657516594772673068428776359209967986976455315601395990722916902332664032586999,\
1442616343492142951567714895868400140154041005678113232564128293615856419017366400433518264055167100,\
970087421665217050504355734630101903751222897855725085446170823722400800030530530463976889622753603,\
2258363182310470121985251088986607701828044783968639213535429926543812089936538055055864143137996841,\
505237968204243143507781511377361535697235874290149443691172953990432820515699803875232158135519869,\
934730011398785856507885997369312200222781505582321951151996339762513085425531461277414586694575070,\
2752437151274189888797602162289757003165763631591151802771415935265582403910914494220774844824601319,\
901136759035775964493211511556424598803761504184276680378812101007921785207166825187800215743527256,\
1798421606565548696280929597503876405132964109849762474257907691407875082441934578323901970598134705,\
1645559016732873731328391679016477201107985843158351498258603554596863856013147861774933821471350825,\
2608599486067529477749547436944266239395321166256667985829261125233001746648999634476879028144272290,\
561594924957049541326915503294955933418447719057942229643794434808747352197284777306200445405099872,\
1227347075664110527518409280758842432864146010054081706435269414352373708380509747948879240187711945,\
1483529478038280273497046890138938622923809304221445667187237548447116351226882648816221645237111602,\
0,\
55511896333275538255191573991142686574850770785795892692892378531374503374412642845127360416095129,\
1754752831202733386919840695284599838762026962575048777997974506975942622749485152359238373471068688,\
592501461648805555101762771111061730465713634406840909527614903104529717246592949654055251946056290,\
1322555086352826079784267766790783729865179440628149883604261236902120193480527341985415991109090268,\
2045721198097073650788028350920171343764499132137162126416766027652670460367781374427291809548481867,\
1558247225534553615696157965307476824240033277800837556494488104288693591301012862360986180251117686,\
2815697605958014094481566976267484880905051244306258491378390609501406616099137299531802990845936847,\
737481072500711764292361728102562205408606776323467874371941871459477557892232848007425492097412459,\
2173394398169596556973663699933816446318954675306105542394194352275195601796725517153197857936940326,\
2092595224606892471961611544465919482650603420787467161244534465626890705248340310131633789654111485,\
1817508215242208777017755632673889700426906351931912553435315019433614604976844214134414695992006171,\
1427326433691254285622493404404651048616377881032906631406157982337285432596799322530438815908602856,\
162469087089121134101412923772808595682249765622144089053707692770776357297867264644603275918155681,\
1063589089261490328568118839222958933392430139783226832089169477321103241398936156296817757465200062,\
1849236833930265977206120449559039371502156896169597411633130901549130271758578668480086239694551330,\
265246320666174388926650203078211162021307950424593146837352843520135873532090441270961851682367814,\
790057288044130426022533479537876153028766530878950871782653065145991587922497258211299247842199272,\
1049055764607512538751978869815670439052618241445927984042126808638875529027706666336775023555484664,\
0];

sum(i=1,100,issquare(i)==0&&(R[i]^2)%n==i&&0<R[i]&&R[i]<n/2)
%3 = 90

[charybdis]

Originally Posted by R. Gerbicz

Yes, used those known factors, but how? I mean if M|N then we know only small squared residues mod M in the range of sqrt(M), but we need these residues mod N and not mod M. Ofcourse you can regard it mod N, but that gives only the boring average N/2 and not sqrt(N) for M<N.

Say N = kM with k being the known factors and M the unfactored part. Find a such that y := a^2 mod M is around sqrt(M). We want x such that x^2 = y mod N, so we also need x^2 = y mod p for each prime factor p of k.

We can easily find lots of values of a with a^2 mod M in the right range, so we can find one such that y is a quadratic residue mod p for each p dividing k. We can quickly find square roots modulo a prime, so do this for each p. Then use CRT to solve the congruences mod each p and mod M, and we have our x.

[R. Gerbicz]

Originally Posted by charybdis

Say N = kM with k being the known factors and M the unfactored part. Find a such that y := a^2 mod M is around sqrt(M). We want x such that x^2 = y mod N, so we also need x^2 = y mod p for each prime factor p of k.

We can easily find lots of values of a with a^2 mod M in the right range, so we can find one such that y is a quadratic residue mod p for each p dividing k. We can quickly find square roots modulo a prime, so do this for each p. Then use CRT to solve the congruences mod each p and mod M, and we have our x.

Yes, that was my method.

[Dr Sardonicus]

If I did my sums correctly, for Fermat numbers F_n with n > 1,

x = (F_n- 1)/(F_n-2 - 1)*F_n-1 (mod F_n) satisfies

x^2 == 2 (mod F_n).

[R. Gerbicz]

Originally Posted by Dr Sardonicus

If I did my sums correctly, for Fermat numbers F_n with n > 1,

x = (F_n- 1)/(F_n-2 - 1)*F_n-1 (mod F_n) satisfies

x^2 == 2 (mod F_n).

Nice. You can negate that: x=F(n-1)/(F(n-2)-1) mod F(n)

And in general: if n=u^4+1 then for x=(u^2+1)/u:
x^2==2 mod n.

[Dr Sardonicus]

Originally Posted by R. Gerbicz

<snip>
And in general: if n=u^4+1 then for x=(u^2+1)/u:
x^2==2 mod n.

D'oh! Of course!

So we've got a square root of Mod(2, u^4 + 1) which can be re-expressed as Mod(u^3 - u, u^4 + 1)^2 = Mod(2, u^4 + 1).

Perhaps even more obvious is

Mod(x, x^2 + 1)^2 = Mod(-1, x^2 + 1).

And just so the Mersenne numbers don't feel left out, we have

Mod(2*x, 2*x^2 - 1)^2 = Mod(2, 2*x^2 - 1).

Having modulo square roots of even the smallest possible nontrivial quadratic residue is unlikely to help factor evaluations of these polynomials at integer arguments: According to the Bunyakovsky conjecture, they all assume infinitely many prime values for integer arguments, and the Bateman-Horn conjecture gives asymptotic estimates.

[LaurV]

Originally Posted by R. Gerbicz

OK, take my challenge <...>

Ha ha, that's dirty. Bad Robert!

You can easily get any relation and multiply it with constants to have all dependent, which won't be the case in real life, when you would get them "random" (therefore you can find some independent).

[Dr Sardonicus]

Originally Posted by R. Gerbicz

<snip>
OK, take my challenge factor my GRSA100 [G means Gerbicz], n=p*q number with 100 digits. You can use "your" method, and even algebra, but not QS, so use only the listed residues. For non-square i numbers in R[i] you'll see a number for that (R[i]^2)==i mod n and 0<R[i]<n/2. There are 90 such entries in the table.
<snip>

Heh-heh. This means that each of the 25 primes less than 100 is a quadratic residue (mod p) and (mod q). We know that the smaller factor (say p) is less than 10^50 which is about 2^166. There are somewhere on the order of 2^159 primes less that 2^166. By considering only primes having the 25 primes less than 100 as a quadratic residue you reduce the number of candidates by a factor of 2^25. So you're down to around 2^134 candidates.

Once upon a time, long long ago, the numbers under consideration were small enough that this approach was actually useful. Primes with a given quadratic residue in a limited range could be encoded in Hollerith cards, which were called "factor stencils." Each stencil excluded about half the primes in its range, so stacking 10 stencils corresponding to known residues for primes in that range would reduce the number of candidates in that range by a factor of roughly 1024.

A Hollerith card had 80 columns of 10, so one card could accommodate a range of 800 primes.

Alas, I just checked the link I gave some time ago from which I downloaded Albert Beiler's book Recreations in the Theory of Numbers which described these things, and got the dreaded Error 404.

[kriesel]

Originally Posted by Dr Sardonicus

A Hollerith card had 80 columns of 10, so one card could accommodate a range of 800 primes.

Sure, only 10 was used in base 10 data, but ordinary programs' character sets used all 12 rows https://en.wikipedia.org/wiki/Punche...151286161).jpg
Some of the engineers using the 24-bit Harris Datacraft DC6024 at UW-Madison in the 1970s punched their program output in binary using all 12 rows/column, two columns/24-bit word for subsequent use. There were fully punched reliability test cards for card readers.

[Stargate38]

Since RMLabrador's formula seems to be too slow/useless, I've posted the factors to the DB number I linked to in post #19.