mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2021-02-19, 08:22   #23
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

2·7·103 Posts
Default

Quote:
Originally Posted by charybdis View Post
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 is offline   Reply With Quote
Old 2021-02-19, 10:36   #24
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

26428 Posts
Default

Quote:
Originally Posted by LaurV View Post
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
R. Gerbicz is offline   Reply With Quote
Old 2021-02-19, 13:01   #25
charybdis
 
Apr 2020

2·5·19 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
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.
charybdis is offline   Reply With Quote
Old 2021-02-19, 15:18   #26
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

2·7·103 Posts
Default

Quote:
Originally Posted by charybdis View Post
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.
R. Gerbicz is offline   Reply With Quote
Old 2021-02-19, 17:53   #27
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

25·33·5 Posts
Default

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).
Dr Sardonicus is offline   Reply With Quote
Old 2021-02-19, 20:18   #28
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

2×7×103 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
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.
R. Gerbicz is offline   Reply With Quote
Old 2021-02-20, 14:35   #29
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

25×33×5 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
<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.
Dr Sardonicus is offline   Reply With Quote
Old 2021-02-23, 11:19   #30
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

243816 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
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
LaurV is offline   Reply With Quote
Old 2021-02-23, 15:18   #31
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

25·33·5 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
<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.
Dr Sardonicus is offline   Reply With Quote
Old 2021-02-23, 17:30   #32
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

7·701 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
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.
kriesel is online now   Reply With Quote
Old 2021-02-28, 17:42   #33
Stargate38
 
Stargate38's Avatar
 
"Daniel Jackson"
May 2011
14285714285714285714

22·7·23 Posts
Default

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.
Stargate38 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Riesel Primes k*2^n-1, k<300 [Part II] Kosmaj Riesel Prime Search 1021 2021-02-25 10:42
I'm sure this is an ID-10-T error on my part petrw1 PrimeNet 1 2017-09-25 23:12
Numbers in Tables : Part 2 wustvn Puzzles 9 2007-12-31 05:14
Two PC's looking for part-time work OmbooHankvald Software 8 2005-07-23 01:23
Circles part 2 mfgoode Puzzles 10 2004-12-27 15:17

All times are UTC. The time now is 20:24.

Sun Feb 28 20:24:05 UTC 2021 up 87 days, 16:35, 0 users, load averages: 3.76, 3.31, 3.24

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.