mersenneforum.org The end of RSA, Part 1
 Register FAQ Search Today's Posts Mark Forums Read

2021-02-19, 08:22   #23
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

145910 Posts

Quote:
 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.

2021-02-19, 10:36   #24
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

5B316 Posts

Quote:
 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.

Code:
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

Last fiddled with by R. Gerbicz on 2021-02-19 at 10:44 Reason: added R[100]=0

2021-02-19, 13:01   #25
charybdis

Apr 2020

2·32·13 Posts

Quote:
 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
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.

2021-02-19, 15:18   #26
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

145910 Posts

Quote:
 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.

 2021-02-19, 17:53 #27 Dr Sardonicus     Feb 2017 Nowhere 448410 Posts If I did my sums correctly, for Fermat numbers Fn with n > 1, x = (Fn- 1)/(Fn-2 - 1)*Fn-1 (mod Fn) satisfies x^2 == 2 (mod Fn).
2021-02-19, 20:18   #28
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

1,459 Posts

Quote:
 Originally Posted by Dr Sardonicus If I did my sums correctly, for Fermat numbers Fn with n > 1, x = (Fn- 1)/(Fn-2 - 1)*Fn-1 (mod Fn) satisfies x^2 == 2 (mod Fn).
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.

2021-02-20, 14:35   #29
Dr Sardonicus

Feb 2017
Nowhere

22·19·59 Posts

Quote:
 Originally Posted by R. Gerbicz 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.

2021-02-23, 11:19   #30
LaurV
Romulan Interpreter

Jun 2011
Thailand

222508 Posts

Quote:
 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).

Last fiddled with by LaurV on 2021-02-23 at 11:25

2021-02-23, 15:18   #31
Dr Sardonicus

Feb 2017
Nowhere

22×19×59 Posts

Quote:
 Originally Posted by R. Gerbicz 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
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.

2021-02-23, 17:30   #32
kriesel

"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

2·3·839 Posts

Quote:
 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.

 2021-02-28, 17:42 #33 Stargate38     "Daniel Jackson" May 2011 14285714285714285714 23·34 Posts 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post Kosmaj Riesel Prime Search 1027 2021-04-20 08:23 petrw1 PrimeNet 1 2017-09-25 23:12 wustvn Puzzles 9 2007-12-31 05:14 OmbooHankvald Software 8 2005-07-23 01:23 mfgoode Puzzles 10 2004-12-27 15:17

All times are UTC. The time now is 15:22.

Wed Apr 21 15:22:40 UTC 2021 up 13 days, 10:03, 0 users, load averages: 2.72, 2.04, 1.88