Talk:Kunerth's algorithm

Square Root of 67 mod 67*f+RSA260 is taken[edit]

Dropping into Mathematica

In[1]:= RSA260 = \
2211282552952966643528108525502623092761208950247001539441374831912882\
2941402001986512729726569746599085900330031400051170742204560859276357\
9537571859542988389587092292384910067030341246205457845664136645406842\
14361293017694020846391065875914794251435144458199

Out[1]= 22112825529529666435281085255026230927612089502470015394413748\
3191288229414020019865127297265697465990859003300314000511707422045608\
5927635795375718595429883895870922923849100670303412462054578456641366\
4540684214361293017694020846391065875914794251435144458199

Ensure F term make C+F a square in Associated Quadratic

In[4]:= f = (Floor[bb^(1/2)] + 1)^2 - bb

Out[4]= 61680487993617575466423211001635452497867860629177112238643415\
1536338262777021476003752497731780456662275070549172392086402843049

Create Quadratic

In[5]:= Expand[((67 z + 25)^2 + (f 67 + RSA260))/67]

Out[5]= 33004217208253233485494157097054076011361327615626888648378728\
8345206312558238835619592980993578307449043288507931344047324510516450\
5254225922019813202664210455889910867157854962940197688303572761354816\
50763031441980751727213603623335755264318574943643805121 + 50 z + 
 67 z^2

proceed with algorithm

In[43]:= y14 = 
 Mod[alpha (67 PowerMod[625, -1, (f 67 + RSA260)]) + 
   beta, (f 67 + RSA260)]

Out[43]= 1415220833889898651857989456321678779367173728158080985242479\
8924242446682497281271368147025004637823414976211220096032749275010946\
9381712791946325774058734024268628937046348559896791469316269255010985\
41461225897986427940404144662922132883373729786377668512709

verify that Out[43] is square root of 67 mod 67*f+RSA260

In[44]:= Mod[y14^2, (f 67 + RSA260)]

Out[44]= 67

show that resulting modulus is not a prime

In[45]:= PrimeQ[f 67 + RSA260]

Out[45]= False

Taking The Square Root of 67*Y Mod RSA260[edit]

The expansion of the quadratic is quite fluid. We can easily set the following quadratic be a square and find the square root

$((67z+25)^{2}+X*RSA260)/(Y*67)$

where ${\sqrt {-RSA260}}{\bmod {67}}\equiv 25$

Thus we can find ultimately the ${\sqrt {Y*67}}{\bmod {RSA260}}$

Dropping into Mathematica we see

RSA260 = 2211282552952966643528108525502623092761208950247001539441374\
8319128822941402001986512729726569746599085900330031400051170742204560\
8592763579537571859542988389587092292384910067030341246205457845664136\
64540684214361293017694020846391065875914794251435144458199

Find nearest square above RSA260

bb = (Floor[RSA260^(1/2)] + 1)^2 - RSA260

= 54819458867339771990053357616221050115768171809225729400503710\
80118837515862925645017501652267319433494304753217083279905934901357

Find the X and Y of ((67 z+25)^2+X*RSA260)/(67*Y)

In[3]:= Solve[(( 25)^2 + x RSA260)/(y 67) == bb + RSA260, {x, 
  y}, Integers]

Out[3]= {{x -> 
   ConditionalExpression[
    917120890958410008482087841589586151217626232826371030111673791229\
3875357204494206813995960346123827602284689018796275566146945366585628\
1877724015699174823011835439795839630828791036440083780601718315985200\
7245661902885039480713346440762676258074691033908734633 + 
     14815593104784876511638327120867574721500099966654910314257211373\
8163113707393413309635289168017302213875532211210380342843972770594486\
1890394078203792295518238914554134625648570915673332951429933911829087\
041860578379242887409798752319832151835794599852317090252 C[
      1], (C[1] \[Element] Integers && 
       C[1] >= 0) || (C[1] \[Element] Integers && C[1] <= -1)], 
  y -> ConditionalExpression[
    136883715068419404251057886804415843465317348183040452255473700183\
4906769732014060718506859753152810089893237166984518741215961994673434\
6749437530606163468264001007707898891720094062622580782849825576639468\
896242063048056914759495383197503850593653212202196296 + 
     22112825529529666435281085255026230927612089502470015394413748319\
1288229414020019865127297265697465990859003300314000511707422045608592\
7635795375718595429883895870922923849100670303412462054578456641366454\
0684214361293017694020846391065875914794251435144458199 C[
      1], (C[1] \[Element] Integers && 
       C[1] >= 0) || (C[1] \[Element] Integers && C[1] <= -1)]}}

Make the new quadratic 

In[4]:= Expand[((67 z + 25)^2 + 
    917120890958410008482087841589586151217626232826371030111673791229\
3875357204494206813995960346123827602284689018796275566146945366585628\
1877724015699174823011835439795839630828791036440083780601718315985200\
7245661902885039480713346440762676258074691033908734633 RSA260)/(67 \
1368837150684194042510578868044158434653173481830404522554737001834906\
7697320140607185068597531528100898932371669845187412159619946734346749\
4375306061634682640010077078988917200940626225807828498255766394688962\
42063048056914759495383197503850593653212202196296)]

Out[4]= 22112825529529666435281085255026230927612089502470015394413748\
3191288229414020019865127297265697465990859003300314000511707422045663\
4122224468773438495963460058081424081530818762560706467091686468525118\
0403609859378794669961340279885370629131877531341079359556 + (25 z)/
  68441857534209702125528943402207921732658674091520226127736850091745\
3384866007030359253429876576405044946618583492259370607980997336717337\
4718765303081734132000503853949445860047031311290391424912788319734448\
121031524028457379747691598751925296826606101098148 + (67 z^2)/
  13688371506841940425105788680441584346531734818304045225547370018349\
0676973201406071850685975315281008989323716698451874121596199467343467\
4943753060616346826400100770789889172009406262258078284982557663946889\
6242063048056914759495383197503850593653212202196296

Don't worry about the fractions to Z^{2} and Z, since Z is zero

set W and V

v = 25

= 25

w = 
 221128255295296664352810852550262309276120895024700153944137483191288\
2294140200198651272972656974659908590033003140005117074220456634122224\
4687734384959634600580814240815308187625607064670916864685251180403609\
859378794669961340279885370629131877531341079359556^(1/2)

= 47024276208709120795061378748873252735571493245640595713707096\
29848608672008763225036307999162383887826987432678940935201933498834

Solve for alpha and beta

In[8]:= Solve[a == w (v + w b), {a, b}, Integers]

Out[8]= {{a -> 
   ConditionalExpression[
    117560690521772801987653446872183131838928733114101489284267740746\
215216800219080625907699979059597195674685816973523380048337470850 + 
     22112825529529666435281085255026230927612089502470015394413748319\
1288229414020019865127297265697465990859003300314000511707422045663412\
2224468773438495963460058081424081530818762560706467091686468525118040\
3609859378794669961340279885370629131877531341079359556 C[1], 
    C[1] \[Element] Integers], 
  b -> ConditionalExpression[C[1], C[1] \[Element] Integers]}}

set alpha and beta 

alpha = 11756069052177280198765344687218313183892873311410148928426774\
0746215216800219080625907699979059597195674685816973523380048337470850\

beta = 0

In[11]:= Timing[
 xx = Factor[
   alpha^2 x^2 + (2 alpha beta - 
       917120890958410008482087841589586151217626232826371030111673791\
2293875357204494206813995960346123827602284689018796275566146945366585\
6281877724015699174823011835439795839630828791036440083780601718315985\
2007245661902885039480713346440762676258074691033908734633 RSA260) x \
+ (beta^2 - 
      67 1368837150684194042510578868044158434653173481830404522554737\
0018349067697320140607185068597531528100898932371669845187412159619946\
7343467494375306061634682640010077078988917200940626225807828498255766\
39468896242063048056914759495383197503850593653212202196296)]]

Out[11]= {0.001808, \
(-91712089095841000848208784158958615121762623282637103011167379122938\
7535720449420681399596034612382760228468901879627556614694536431201232\
2123145506129523736880675164292257452463021957129124509383136348444160\
48218224219813288886190674232757989774765217547151832 + 625 x) (1 + 
    221128255295296664352810852550262309276120895024700153944137483191\
2882294140200198651272972656974659908590033003140005117074220456634122\
2244687734384959634600580814240815308187625607064670916864685251180403\
609859378794669961340279885370629131877531341079359556 x)}

make square root of Y*67 mod X*RSA260

In[12]:= y20 = 
 Mod[alpha (-1 PowerMod[
       221128255295296664352810852550262309276120895024700153944137483\
1912882294140200198651272972656974659908590033003140005117074220456634\
1222244687734384959634600580814240815308187625607064670916864685251180\
403609859378794669961340279885370629131877531341079359556, -1, 
       917120890958410008482087841589586151217626232826371030111673791\
2293875357204494206813995960346123827602284689018796275566146945366585\
6281877724015699174823011835439795839630828791036440083780601718315985\
2007245661902885039480713346440762676258074691033908734633 RSA260]) + 
   beta, 9171208909584100084820878415895861512176262328263710301116737\
9122938753572044942068139959603461238276022846890187962755661469453665\
8562818777240156991748230118354397958396308287910364400837806017183159\
852007245661902885039480713346440762676258074691033908734633 RSA260]

Out[12]= 1135687518070006846887464059143685218548224789823900288712062\
0161349230186311372609095609924686501885032258079250035399140494699580\
4282128173250630469829918963238326756881815299910190655332367589825870\
0152887712366916712677369184923841399860759273069677450787072142484552\
7826122846536736649568463943702815871332771256125696257928782086877055\
6128632769667392696780362313599985334892513732085200490148901318534771\
9136356155445220411201535935080066343567341587283621854313017633376135\
5086629145306692049420010258738365460786


ensure square root has been found

Mod[y20^2, 
  91712089095841000848208784158958615121762623282637103011167379122938\
7535720449420681399596034612382760228468901879627556614694536658562818\
7772401569917482301183543979583963082879103644008378060171831598520072\
45661902885039480713346440762676258074691033908734633 RSA260] == 
 67 136883715068419404251057886804415843465317348183040452255473700183\
4906769732014060718506859753152810089893237166984518741215961994673434\
6749437530606163468264001007707898891720094062622580782849825576639468\
896242063048056914759495383197503850593653212202196296

= True

now reduce modulus to RSA260

Mod[y20^2, RSA260] == 
 Mod[67 13688371506841940425105788680441584346531734818304045225547370\
0183490676973201406071850685975315281008989323716698451874121596199467\
3434674943753060616346826400100770789889172009406262258078284982557663\
9468896242063048056914759495383197503850593653212202196296, RSA260]

= True


show square root

Mod[y20, RSA260]

= 1347984549432556028783466692801644423562572831345407611132640\
8461433033037038763662887179059324590157900214282015315896277432597863\
4445457453370674239475817222859934247260381018593945056022964392877868\
89939930371632801365916099130785038894308954176871426817131

show square

Mod[y20^2, RSA260]

= 1049504424769368463556334613351068318553056322510039894071011\
0145105795122967339234377677245252772197706555370592225458614264149435\
9709015362105059888261212907604380304476139714777966034700737710906745\
98247995429411206087834031488640531845483210456376624365673

show square is 67*Y mod RSA260

Mod[
 67 136883715068419404251057886804415843465317348183040452255473700183\
4906769732014060718506859753152810089893237166984518741215961994673434\
6749437530606163468264001007707898891720094062622580782849825576639468\
896242063048056914759495383197503850593653212202196296, RSA260]

= 1049504424769368463556334613351068318553056322510039894071011\
0145105795122967339234377677245252772197706555370592225458614264149435\
9709015362105059888261212907604380304476139714777966034700737710906745\
98247995429411206087834031488640531845483210456376624365673

Thus the square root mod RSA260 of

1049504424769368463556334613351068318553056322510039894071011\
0145105795122967339234377677245252772197706555370592225458614264149435\
9709015362105059888261212907604380304476139714777966034700737710906745\
98247995429411206087834031488640531845483210456376624365673

is found to be

1347984549432556028783466692801644423562572831345407611132640\
8461433033037038763662887179059324590157900214282015315896277432597863\
4445457453370674239475817222859934247260381018593945056022964392877868\
89939930371632801365916099130785038894308954176871426817131

Thus a hard modular square root of a still to be factored (as of this date) RSA number has been found, although I am still unable to find ${\sqrt {67}}{\bmod {RSA260}}$ .

I believe this is the first time someone has been able to find a modular square root of a square of a modulus that is an rsa number that hasn't been factored yet.

Endo999 (talk) 14:06, 22 December 2021 (UTC)[reply]

This took around 1 second on a Raspberry PI 4

Endo999 (talk) 20:19, 5 May 2022 (UTC)[reply]

Root Of A Modular Square Found, But Cannot Pick It[edit]

So it is possible to take the modular square root of a square mod RSA260, but you cannot pick the number. You set the SQUARE term (which is the first item in the quadratic) and then solve via Mathematica such as

In[35]:= Solve[((25)^2 + x RSA260)/(y) == (Floor[RSA260^(1/2)] + 
     1)^2, {x, y}, Integers]

Out[35]= {{x -> 
   ConditionalExpression[
    104950442476936846355633461335106831855305632251003989407101101451\
0579512296733923437767724525277219770655537059222545861426414943857270\
6745043047208403211494541014084968672595260474749330214565087861455459\
241427372303571065761871140566881851095906049654992837 + 
     22112825529529666435281085255026230927612089502470015394413748319\
1288229414020019865127297265697465990859003300314000511707422045663412\
2224468773438495963460058081424081530818762560706467091686468525118040\
3609859378794669961340279885370629131877531341079359556 C[
      1], (C[1] \[Element] Integers && 
       C[1] >= 0) || (C[1] \[Element] Integers && C[1] <= -1)], 
  y -> ConditionalExpression[
    104950442476936846355633461335106831855305632251003989407101101451\
0579512296733923437767724525277219770655537059222545861426414943597090\
1536210505988826121290760438030447613971477796603470073771090674598247\
995429411206087834031488640531845483210456376624365673 + 
     22112825529529666435281085255026230927612089502470015394413748319\
1288229414020019865127297265697465990859003300314000511707422045608592\
7635795375718595429883895870922923849100670303412462054578456641366454\
0684214361293017694020846391065875914794251435144458199 C[
      1], (C[1] \[Element] Integers && 
       C[1] >= 0) || (C[1] \[Element] Integers && C[1] <= -1)]}}

Thus the square in this case is 

In[37]:= y4 = \
1049504424769368463556334613351068318553056322510039894071011014510579\
5122967339234377677245252772197706555370592225458614264149435970901536\
2105059888261212907604380304476139714777966034700737710906745982479954\
29411206087834031488640531845483210456376624365673

Out[37]= 1049504424769368463556334613351068318553056322510039894071011\
0145105795122967339234377677245252772197706555370592225458614264149435\
9709015362105059888261212907604380304476139714777966034700737710906745\
98247995429411206087834031488640531845483210456376624365673

and the root is 

In[42]:= y45 = 
 Mod[alpha (-1 PowerMod[
       221128255295296664352810852550262309276120895024700153944137483\
1912882294140200198651272972656974659908590033003140005117074220456634\
1222244687734384959634600580814240815308187625607064670916864685251180\
403609859378794669961340279885370629131877531341079359556 , -1, 
       RSA260]) + beta, RSA260]

Out[42]= 1347984549432556028783466692801644423562572831345407611132640\
8461433033037038763662887179059324590157900214282015315896277432597863\
4445457453370674239475817222859934247260381018593945056022964392877868\
89939930371632801365916099130785038894308954176871426817131

In[43]:= Mod[y45^2, RSA260] == Mod[y4, RSA260]

Out[43]= True

It doesn't seem possible to set the Y term though, so a bridge has been found, not a general square root algorithm.

Square Root of 5 mod X*RSA260+1[edit]

Kunerth's method is quite exciting since it doesn't have to factor the modulus. Follow the mathematica below and see how the square root of 5 mod x*RSA260+1 is found within seconds on a Raspberry PI 4 palmtop.

The use of the Pythagorean Theorum to solve the quadratic shows what is in the notes in the Mathematica below. that for the modulus RSA260 and square of 5 that

RSA260^4+18*RSA260^2+1

seems to be the modulus. So if you factor N-1 and it has the factorisation of X^4+18*X^2 then you should be able to use Kunerth (see code below) to find the square root of 5 quickly of modulus x^4+18x^2+1.

I haven't proven this but I'd say at this point that

If N is the modulus, C is the square and D is the natural square just below C that

take the factorisation of N-(C-D)=Y

if Y equals (C-D)x^4+(4*C-2*(C-D))*x^2

then Kunerth with the Pythagorean Method below should be able to take the square root of C mod N quickly.

using the Pythagorean method and Kunerth shown below.

Using the Pythagorean Theorum Solve the quadratic

In[11]:= w = 
 Expand[((2 (RSA260^2 - 1^2 ))^2 + 1 (RSA260^2 - 1^2)^2 + 
      5 (((2 1 RSA260)^2)))/(5)]^(1/2)

Out[11]= 4889770528994189727851565631690024017165005555729269682395332\
5863566645342454412925398180236065314500376295946985354254181805038742\
4723625429992521654787837491618048319631364040388191253484698255313698\
7424736875836220039610457304524305120045165665398590929500984074537021\
3332671406165455614268623279672955402907322055976895600593186605328911\
5169593626456219480475197831634106662908018989638508845064827782102219\
8331778793835658611538459312186788747890608185252992497633380107893907\
21301760772016869260727399301258323602

set v

In[12]:= v = 2 (RSA260^2 - 1^2)

Out[12]= 9779541057988379455703131263380048034330011111458539364790665\
1727133290684908825850796360472130629000752591893970708508363610077484\
9447250859985043309575674983236096639262728080776382506969396510627397\
4849473751672440079220914609048610240090331330797181859001968149074042\
6665342812330911228537246559345910805814644111953791201186373210657823\
0339187252912438960950395663268213325816037979277017690129655564204439\
6663557587671317223076918624373577495781216370505984995266760215787814\
42603521544033738521454798602516647200

make the modulus a variable.  (Please note that probably the modular square root 
of 5 can be solved for any modulus that is x^4+18x^2+1  by this method, no matter 
how big)


In[13]:= mod =  (RSA260^2 - 1^2)^2 + 5 (((2 1 RSA260)^2))

Out[13]= 2390985582622011804596626598395673467700135963629555889132984\
5992580385378407468442673330055684425335333246848835333293215726575872\
1355685125318060112890318777229278719348539134043483869594721596706402\
4651101060452794751171383943446773743600355859434238217228786384923053\
5389751388452988050713762957991442433151288721501791712710759860571865\
5790897032492359755314922463372956523242589287663244150824214352062397\
1538543656788644287421389533958059991841118958363279465471977198209879\
2469088087239949376049602423582807491703992476167184773046653404954534\
8594032808685422438526157752221902651776609480274917656256432838107178\
4959761186928798048189304205947855234339204482167029856642017237764576\
9783217378669834197799692670939878034230039774474178421414940663330766\
6517128460930159144372737789700813274692324363089889374327026605350455\
5763358876399563570064243443818628546720647588356443002938261756026433\
0727573629317789549844076859516283862514294434927309207692660437108140\
4188164670644817863924855879204361453559753554627758324307483432020

solve for alpha and beta

In[14]:= Solve[a == (w (v + w b)), {a, b}, Integers]

Out[14]= {{a -> 
   ConditionalExpression[
    239098558262201180459662659839567346770013596362955588913298459925\
8038537840746844267333005568442533533324684883533329321572657587213556\
8512531806011289031877722927871934853913404348386959472159670640246511\
0106045279475117138394344677374360035585943423821722878638492305353897\
5138845298805071376295799144243315128872150179171271075986057186557908\
9703249235975531492246337295652324258928766324415082421435206239715385\
4365678864428742138953395805999184111895836327946547197719820987924690\
8808723994937604960242358280749072603837036834682747634027861653005597\
0279757396389916136708704918932270811859768983802020921977520710323678\
6721622028968457922672100313014834070015120946235831840757383830417024\
4099616286480128906527345493065906279576655208696051007963932173351863\
3127907115717622366374703427899345923324023616471839243552476899116514\
0508519837719685358562078470982142940369226140343661144042344482927482\
9661162765989427987241984992810374716271261961734525530268753001878176\
58685649551103709068064778326238119416169413210338282316959996 + 
     23909855826220118045966265983956734677001359636295558891329845992\
5803853784074684426733300556844253353332468488353332932157265758721355\
6851253180601128903187772292787193485391340434838695947215967064024651\
1010604527947511713839434467737436003558594342382172287863849230535389\
7513884529880507137629579914424331512887215017917127107598605718655790\
8970324923597553149224633729565232425892876632441508242143520623971538\
5436567886442874213895339580599918411189583632794654719771982098792469\
0880872399493760496024235828074909216291915281144165904029038841310166\
5687997962556070343252200837319885218167742068539474186623877871182886\
2460103619913573012422179920751655404010174009758579831295066235587318\
5962726642586805911907529519201340962445681365052526910518441235401452\
4907154429575698534785555675858497058514648069096495793537408852840473\
7958434386144714957171853914935664876524714804113498768046899611500344\
1520151656858253927133077831992555005890570811557177427742374456431091\
759882648604455752225627663533281207483646456119935487350254404 C[1], 
    C[1] \[Element] Integers], 
  b -> ConditionalExpression[-1 + C[1], C[1] \[Element] Integers]}}

set alpha

In[15]:= alpha = \
2390985582622011804596626598395673467700135963629555889132984599258038\
5378407468442673330055684425335333246848835333293215726575872135568512\
5318060112890318777229278719348539134043483869594721596706402465110106\
0452794751171383943446773743600355859434238217228786384923053538975138\
8452988050713762957991442433151288721501791712710759860571865579089703\
2492359755314922463372956523242589287663244150824214352062397153854365\
6788644287421389533958059991841118958363279465471977198209879246908808\
7239949376049602423582807490726038370368346827476340278616530055970279\
7573963899161367087049189322708118597689838020209219775207103236786721\
6220289684579226721003130148340700151209462358318407573838304170244099\
6162864801289065273454930659062795766552086960510079639321733518633127\
9071157176223663747034278993459233240236164718392435524768991165140508\
5198377196853585620784709821429403692261403436611440423444829274829661\
1627659894279872419849928103747162712619617345255302687530018781765868\
5649551103709068064778326238119416169413210338282316959996

Out[15]= 2390985582622011804596626598395673467700135963629555889132984\
5992580385378407468442673330055684425335333246848835333293215726575872\
1355685125318060112890318777229278719348539134043483869594721596706402\
4651101060452794751171383943446773743600355859434238217228786384923053\
5389751388452988050713762957991442433151288721501791712710759860571865\
5790897032492359755314922463372956523242589287663244150824214352062397\
1538543656788644287421389533958059991841118958363279465471977198209879\
2469088087239949376049602423582807490726038370368346827476340278616530\
0559702797573963899161367087049189322708118597689838020209219775207103\
2367867216220289684579226721003130148340700151209462358318407573838304\
1702440996162864801289065273454930659062795766552086960510079639321733\
5186331279071157176223663747034278993459233240236164718392435524768991\
1651405085198377196853585620784709821429403692261403436611440423444829\
2748296611627659894279872419849928103747162712619617345255302687530018\
7817658685649551103709068064778326238119416169413210338282316959996

set beta

In[7]:= beta = -1

Out[7]= -1

find x value via factoring 

In[16]:= Timing[
 xxx1 = Factor[(alpha^2 x^2 + (2 alpha beta - (mod)) x + (beta^2 -  ( 
        5)))]]

Out[16]= {0.016567, 
 4 (-1 + 5977463956555029511491566495989183669250339909073889722832461\
4981450963446018671106683325139211063338333117122088333233039316439680\
3389212813295150282225796943073196798371347835108709673986803991766006\
1627752651131986877928459858616934359000889648585595543071965962307633\
8474378471132470126784407394978606082878221803754479281776899651429663\
9477242581230899388287306158432391308106473219158110377060535880155992\
8846359141971610718553473834895149979602797395908198663679942995524698\
1172720218099873440124006058957018726326118873021448095905694133372322\
7382091988379180478221022385036616642236051052932055232499442906567720\
4623721055196470029643028060035462827852498212544872146634214102632624\
0215714299153677304967349484894852960073367412419171670822768586299817\
2300429606748391956484622346252430343031537539163549468013793271631745\
7072535817395349805528635140444815190927887282605988808365190392321271\
2881103020224084907917578829791642379984340920395197431919577844035986\
135889372162624437916477625473279798757837173092575185269320916401 x) \
(1 + 23909855826220118045966265983956734677001359636295558891329845992\
5803853784074684426733300556844253353332468488353332932157265758721355\
6851253180601128903187772292787193485391340434838695947215967064024651\
1010604527947511713839434467737436003558594342382172287863849230535389\
7513884529880507137629579914424331512887215017917127107598605718655790\
8970324923597553149224633729565232425892876632441508242143520623971538\
5436567886442874213895339580599918411189583632794654719771982098792469\
0880872399493760496024235828074909216291915281144165904029038841310166\
5687997962556070343252200837319885218167742068539474186623877871182886\
2460103619913573012422179920751655404010174009758579831295066235587318\
5962726642586805911907529519201340962445681365052526910518441235401452\
4907154429575698534785555675858497058514648069096495793537408852840473\
7958434386144714957171853914935664876524714804113498768046899611500344\
1520151656858253927133077831992555005890570811557177427742374456431091\
759882648604455752225627663533281207483646456119935487350254404 x)}

find the root of 5 mod (modulus/4)

In[17]:= y20 = 
 Mod[alpha (-1 PowerMod[
       239098558262201180459662659839567346770013596362955588913298459\
9258038537840746844267333005568442533533324684883533329321572657587213\
5568512531806011289031877722927871934853913404348386959472159670640246\
5110106045279475117138394344677374360035585943423821722878638492305353\
8975138845298805071376295799144243315128872150179171271075986057186557\
9089703249235975531492246337295652324258928766324415082421435206239715\
3854365678864428742138953395805999184111895836327946547197719820987924\
6908808723994937604960242358280749092162919152811441659040290388413101\
6656879979625560703432522008373198852181677420685394741866238778711828\
8624601036199135730124221799207516554040101740097585798312950662355873\
1859627266425868059119075295192013409624456813650525269105184412354014\
5249071544295756985347855556758584970585146480690964957935374088528404\
7379584343861447149571718539149356648765247148041134987680468996115003\
4415201516568582539271330778319925550058905708115571774277423744564310\
91759882648604455752225627663533281207483646456119935487350254404, -1,
        mod/4]) + beta, mod/4]

Out[17]= 2988731978277514755745783247994591834625169954536944861416230\
7490725481723009335553341662569605531669166558561044166616519658219840\
1694606406647575141112898471536598399185673917554354836993401995883003\
0813876325565993438964229929308467179500444824292797771535982981153816\
9237189235566235063392203697489303041439110901877239640888449825714831\
9738621290615449694143653079216195654053236609579055188530267940077996\
4423179570985805359276736917447574989801398697954099331839971497762349\
0586360109049936720062003029478509364752234858433835709504605896985419\
1746832262245710365578296023423967480854323210666782024826442680496482\
5273688229999561105687889943052909678673818644078483258092972755196505\
3239118771150663921813444263360465964683455219082984459381783457164587\
4562760223895074176484556492459333378519541844219077299900607141760752\
5218192819399602759231636532652525524062214972457433699463679861605741\
8156876663858503144250621629353649297988759508947597992420495265082440\
728151908643043067493304332580870621887973411643651640363750009905

verify root of 5 has been found

In[19]:= Mod[y20^2, mod/4]

Out[19]= 5

show modulus is 1 off a multiple of RSA260

In[20]:= GCD[mod - 1, RSA260]

Out[20]= 2211282552952966643528108525502623092761208950247001539441374\
8319128822941402001986512729726569746599085900330031400051170742204560\
8592763579537571859542988389587092292384910067030341246205457845664136\
64540684214361293017694020846391065875914794251435144458199

Endo999 (talk) 03:05, 14 May 2022 (UTC)[reply]

Thanks[edit]

Thanks to the Mathematica computing system. It's been a breeze to work with Kunerth's method with Mathematica. Thanks to Mr. Steven Wolfram and his team at Mathematica. The work shown here has been done on the Raspberry PI 4 version of Mathematica. Endo999 (talk) 13:13, 14 May 2022 (UTC)[reply]

square root of 5 mod x*RSA270+1 is[edit]

Using the formula given above that any modulus of x^4+18x^2+1 will allow Kunerth's method to retrieve the modular square root of 5, here is the modular square root of 5 mod RSA270^4+18*RSA270^2+1

y20=3690988383204217038340117823294923049536581371008848663572890424218803\
1964866337293558291692329649440716480840745652081850014939348009387038\
2781750055011851486957246774263586532586946695470177166272544874044059\
9073637443348609744280450917500743522346228334630070062204837799687691\
8979579392137458719472234654521409245163585278762047542492940883636308\
3678950219585711529988865922879855140362335939123011995218675993425843\
3271082460543624565920975768082361934527646650410830443351245929703307\
6287030748722050298768260679895617537321926364807588422393592601067756\
5549095656672346035967606247938975172957634984222136270967969963570105\
6553751939601616527321203518370764097038022075629587155481954685331444\
4094066742732712236528258372338715068772988089009842280873698339792902\
5160882616217173344613023417439569667402744047420335248014401881280214\
5519185246374158133468389128849889359291370585485195400027702946545599\
5777185658332199608310262912041769488861310563165769670482764013832200\
5386500144368219885210862528421435063594967227053060657583055697144495\
171977259983373194369016225


verify that square root of 5 mod x*RSA270+1 has been 
found

In[27]:= Mod[y20^2, RSA270^4 + 18 RSA270^2 + 1]

Out[27]= 5

Endo999 (talk) 05:55, 17 May 2022 (UTC)[reply]

Square root of 5 mod RSA260^2+RSA260-1[edit]

The square root of 5 mod RSA260^2+RSA260-1 is shown below.

Factor the modulus to reveal the factors
In[1]:= Factor[Expand[4 (R^2 + 1)^2 - 5 (2 1 R)^2]]

See that (-1+R+R^2) is a factor, we will show the root of 5 for this modulus
Out[1]= 4 (-1 - R + R^2) (-1 + R + R^2)

In[2]:= RSA260 = \
2211282552952966643528108525502623092761208950247001539441374831912882\
2941402001986512729726569746599085900330031400051170742204560859276357\
9537571859542988389587092292384910067030341246205457845664136645406842\
14361293017694020846391065875914794251435144458199

Out[2]= 22112825529529666435281085255026230927612089502470015394413748\
3191288229414020019865127297265697465990859003300314000511707422045608\
5927635795375718595429883895870922923849100670303412462054578456641366\
4540684214361293017694020846391065875914794251435144458199

In[16]:= w = (((((RSA260^2 + 1)^2) + (2 (RSA260^2 + 1))^2 - 
       5 (2 1 RSA260)^2))/5)^(1/2)

Out[16]= 4889770528994189727851565631690024017165005555729269682395332\
5863566645342454412925398180236065314500376295946985354254181805038742\
4723625429992521654787837491618048319631364040388191253484698255313698\
7424736875836220039610457304524305120045165665398590929500984074537021\
3332671406165455614268623279672955402907322055976895600593186605328911\
5169593626456219480475197831634106662908018989638508845064827782102219\
8331778793835658611538459312186788747890608185252992497633380107893907\
21301760772016869260727399301258323600

In[15]:= v = RSA260^2 + 1

Out[15]= 4889770528994189727851565631690024017165005555729269682395332\
5863566645342454412925398180236065314500376295946985354254181805038742\
4723625429992521654787837491618048319631364040388191253484698255313698\
7424736875836220039610457304524305120045165665398590929500984074537021\
3332671406165455614268623279672955402907322055976895600593186605328911\
5169593626456219480475197831634106662908018989638508845064827782102219\
8331778793835658611538459312186788747890608185252992497633380107893907\
21301760772016869260727399301258323602

In[11]:= mod = (2 (RSA260^2 + 1))^2 - 5 (2 1 RSA260)^2

Out[11]= 9563942330488047218386506393582693870800543854518223556531938\
3970321541513629873770693320222737701341332987395341333172862906303488\
5422740501272240451561275108917114877394156536173935478378886386825609\
8604404241811179004685535773787094974401423437736952868915145539692214\
1559005553811952202855051831965769732605154886007166850843039442287462\
3163588129969439021259689853491826092970357150652976603296857408249588\
6154174627154577149685558135832239967364475833453117861887908792839516\
9876352348959797504198409694331229962708562660313619720791298489198519\
2631945188073563888772510215162214625018776214242336153627436488248397\
8953090070739457065594891387023575576163099738646335933608908362567962\
1193608708150065325854135614322733161217734264623929549859346352485127\
4479165679912828311264840179603809117590314736373913942382823882959671\
7783229582553271512772210918532055540659365989826605833180397427262996\
3397331042972613646006648791466441263235224506016931008533739200204450\
7996533545599151062793114696228097909389597200609931755924234545596

In[17]:= alpha = v w

Out[17]= 2390985582622011804596626598395673467700135963629555889132984\
5992580385378407468442673330055684425335333246848835333293215726575872\
1355685125318060112890318777229278719348539134043483869594721596706402\
4651101060452794751171383943446773743600355859434238217228786384923053\
5389751388452988050713762957991442433151288721501791712710759860571865\
5790897032492359755314922463372956523242589287663244150824214352062397\
1538543656788644287421389533958059991841118958363279465471977198209879\
2469088087239949376049602423582807490823833780948230622033371591250330\
5363135798685109753097846153566460655614967685948345983813941081497110\
7627056613291140520940234469497602656940550584305219108150768540230931\
4510518634413561740940128013203425396579520167344296106600565741722636\
8319410997257057373038571151300932421582542352521537183985894632827137\
6062600464318495834174651403088101693958528081870907393244122556702989\
6546224313396672859836292863816563679623875884850386531499038462487830\
9454709284149077779730646846220929759663449907934665136884833607200

In[18]:= beta = 0

Out[18]= 0

In[19]:= Timing[
 xx = Factor[alpha^2 x^2 + (2 alpha beta - mod) x + (beta^2 - ((5)))]]

Out[19]= {0.016756, (1 + 
    239098558262201180459662659839567346770013596362955588913298459925\
8038537840746844267333005568442533533324684883533329321572657587213556\
8512531806011289031877722927871934853913404348386959472159670640246511\
0106045279475117138394344677374360035585943423821722878638492305353897\
5138845298805071376295799144243315128872150179171271075986057186557908\
9703249235975531492246337295652324258928766324415082421435206239715385\
4365678864428742138953395805999184111895836327946547197719820987924690\
8808723994937604960242358280749072603837036834682747634027861653005597\
0279757396389916136708704918932270811859768983802020921977520710323678\
6721622028968457922672100313014834070015120946235831840757383830417024\
4099616286480128906527345493065906279576655208696051007963932173351863\
3127907115717622366374703427899345923324023616471839243552476899116514\
0508519837719685358562078470982142940369226140343661144042344482927482\
9661162765989427987241984992810374716271261961734525530268753001878176\
58685649551103709068064778326238119416169413210338282316960000 x) (-5 \
+ 23909855826220118045966265983956734677001359636295558891329845992580\
3853784074684426733300556844253353332468488353332932157265758721355685\
1253180601128903187772292787193485391340434838695947215967064024651101\
0604527947511713839434467737436003558594342382172287863849230535389751\
3884529880507137629579914424331512887215017917127107598605718655790897\
0324923597553149224633729565232425892876632441508242143520623971538543\
6567886442874213895339580599918411189583632794654719771982098792469088\
0872399493760496024235828074909216291915281144165904029038841310166568\
7997962556070343252200837319885218167742068539474186623877871182886246\
0103619913573012422179920751655404010174009758579831295066235587318596\
2726642586805911907529519201340962445681365052526910518441235401452490\
7154429575698534785555675858497058514648069096495793537408852840473795\
8434386144714957171853914935664876524714804113498768046899611500344152\
0151656858253927133077831992555005890570811557177427742374456431091759\
882648604455752225627663533281207483646456119935487350254404 x)}


In[23]:= y25 = 
 Mod[alpha (-1 PowerMod[
       239098558262201180459662659839567346770013596362955588913298459\
9258038537840746844267333005568442533533324684883533329321572657587213\
5568512531806011289031877722927871934853913404348386959472159670640246\
5110106045279475117138394344677374360035585943423821722878638492305353\
8975138845298805071376295799144243315128872150179171271075986057186557\
9089703249235975531492246337295652324258928766324415082421435206239715\
3854365678864428742138953395805999184111895836327946547197719820987924\
6908808723994937604960242358280749072603837036834682747634027861653005\
5970279757396389916136708704918932270811859768983802020921977520710323\
6786721622028968457922672100313014834070015120946235831840757383830417\
0244099616286480128906527345493065906279576655208696051007963932173351\
8633127907115717622366374703427899345923324023616471839243552476899116\
5140508519837719685358562078470982142940369226140343661144042344482927\
4829661162765989427987241984992810374716271261961734525530268753001878\
17658685649551103709068064778326238119416169413210338282316960000, \
-1, (-1 + RSA260 + RSA260^2)]) + beta , (-1 + RSA260^2 + RSA260)]

Out[23]= 4422565105905933287056217051005246185522417900494003078882749\
6638257645882804003973025459453139493198171800660062800102341484409121\
7185527159075143719085976779174184584769820134060682492410915691328273\
29081368428722586035388041692782131751829588502870288916399

In[24]:= Mod[y25^2, -1 + RSA260 + RSA260^2]

Out[24]= 5

Endo999 (talk) 06:09, 20 September 2022 (UTC)[reply]

root of 5 mod (x^4-3x^2+1) squared is equal to 5+4(x^4-3x^2+1)[edit]

taken from the Kunerth definition of the w variable

In[23]:= Factor[Expand[(2 (x^2 + 1))^2 - 5 (2 1 x)^2]]

Out[23]= 4 (-1 - x + x^2) (-1 + x + x^2)

In[1]:= Expand[(x^2 - x - 1) (x^2 + x - 1)]

Out[1]= 1 - 3 x^2 + x^4

In[1]:= Solve[(x^4 - 3 x^2 + 1) == 0, {x}, Modulus -> 89 29]

Out[1]= {{x -> 168}, {x -> 169}, {x -> 614}, {x -> 632}, {x -> 
   633}, {x -> 702}, {x -> 1078}, {x -> 1166}, {x -> 1415}, {x -> 
   1503}, {x -> 1879}, {x -> 1948}, {x -> 1949}, {x -> 1967}, {x -> 
   2412}, {x -> 2413}}

Note the relationship between the answer above 168 and 337, the root of 5 mod 89*29

In[5]:= Mod[(2 168 + 1)^2, 89 29]

Out[5]= 5

take the root of 5 for this multiple of 89*29

In[1]:= PowerMod[5, 1/2, (168)^4 - 3 (168)^2 + 1]

Out[1]= 56445

Note that the quotient of the square is always 4, no matter what the modulus is
(as long as it equals x^4-3x^2+1===0 mod p*q)

In[6]:= N[56445^2/((168)^4 - 3 (168)^2 + 1)]

Out[6]= 4.

The two points of the above Mathematica,

1) 2*x+1 is the root of 5 mod p*q

2) the root squared of the root of 5 mod (x^4-3x^2+1) shows a quotient of four

seems to work no matter what the p*q modulus is.

This means if you know the root of 5 mod p*q then you can know the root of 5 mod (x^4-3x^2+1) where (x^4-3x^2+1)===0 mod p*q.

This means that you can find the root of 5 for mod (x^4-3x^2+1). When the original modulus is a prime, p, then the new modulus for which the root of 5 is found is therefore y*p, so the root of y is also found, which is (x^4-3^x2+1)/p. This is shown for a 1000 bit prime in the next section.

Cipolla and Tonelli both find the roots of 5 for $p^{y}$ but not for $y*p$ .

The following two tables summarise the nature of the primes for which n*n+1 mod Y*P can be found.

Prime	Polynomial for Modulus
5	((2 (x^2 + 1))^2 - 5 (2 1 x)^2)/4
17	((4 (x^2 + 1))^2 - 17 (2 1 x)^2)/4
37	((6 (x^2 + 1))^2 - 37 (2 1 x)^2)/4
101	((10 (x^2 + 1))^2 - 101 (2 1 x)^2)/4

Prime	Definition	Def of X	Quotient Multiplier
5	2*2+1	(rootof5-1)/2	4
17	4*4+1	(rootof17-1)/4	16
37	6*6+1	(rootof37-1)/6	36
101	10*10+1	(rootof101-1)/10	100

Congruent Squares Can Be Had[edit]

Since $y=\pm ({\sqrt {x}}\pm b^{2})*({\sqrt {x-1}})^{-1}*b$ solves the equation it's easy to create two natural squares (both congruent to x) for the polynomial that makes up the new modulus of z*p (or z*p*q). This gives up to 4 different congruent squares(this only applies when b=1 in the above equation). Unfortunately, these two do not factor the modulus. This is the solution for the polynomial: $(x-1)(y^{2}+b^{2})^{2}-x(2*b*y)^{2}$ . The solution for the polynomial $(1)(y^{2}+1)^{2}-x(2*1y)^{2}$ is $y=\pm {\sqrt {x}}\pm {\sqrt {x-1}}$ .

It is possible to quickly find the square roots of two modular squares 1 apart, even for RSA numbers. Consult here for how to do this.

These two types of polynomials can be used as the definition of a modulus for the Kunerth method.

Examples showing unlimited congruent squares generated by the Kunerth method are shown here^[1].

Showing this with a large prime modulus[edit]

We will show that knowing the root of 5 mod p where p is a 1000 bit prime can make knowing the root of 5 mod(x^4-3 x^2+1) easy when x is the (rootof5-1)/2.

In[4]:= p = NextPrime[2^1000 + 1, 3]

Out[4]= 10715086071862673209484250490600018105614048117055336074437503\
8837035105112493612249319837881569585812759467291755314682518714528569\
2314043598457757469857480393456777482423098542107460506237114187795418\
2153046474983581941267398767559165543946077062914571196477686542167660\
429831652624386837205668074719

In[5]:= r5p = PowerMod[5, 1/2, NextPrime[2^1000 + 1, 3]]

Out[5]= 42130598235734700400412863678358400343851829547637867333716817\
8958752526454143408751791721631733642988693659529746447756284068354472\
9257728658437929345467149708089989426050768748178317699688401942080486\
0786622076634145117791469050888307772631985482470951248377653103007701\
43407447960378245283882437800

In[6]:= r5a = Mod[(r5p - 1) PowerMod[2, -1, p], p]

Out[6]= 74640729477180716247627684292179290699996155359095614039045928\
3664551788789539765622495050223714750558144166223649797290735606820082\
6199082321507752022020976821328882125140877084626461381029771910017334\
1158543413234982265232728363239981606046378055808331606577259262342152\
86619550292382541244775256259

In[9]:= Mod[r5a^4 - 3 r5a^2 + 1, p]

Out[9]= 0

In[10]:= np = r5a^4 - 3 r5a^2 + 1

Out[10]= \
3103869838918094728884305995599976746373014716905007833273463661659975\
7874489453218577997915701531597502839203811906752595136260883862051195\
0658532357495564886020678883564860716187031269171482659261544788426532\
0530173905940599236646422938784819182242004349923496333627042180751321\
1975805647007865761874801550350638442367369367979682891989299371296604\
9036724928519156687566200631838797781418115462658676686205077129284117\
6045796269373062308220483058587895436470192379188556261616694027357712\
6767391763106589376996923833640639310742418038147928733141777246369946\
0744757335940195420952098015156697270852511421434049776171310300583051\
3639892880989235785628870836915056657154042060429444645393006482631065\
5220513401556019838834534472239253169617995837629758167239666420993770\
9281375585236710279230584056173386527732972000884312106585215710776656\
3978273511398769247955581181381472395212574006308066870622897481731283\
3510819097373182273322546812327204205142254204478344459167307435979740\
6252690006632099504504051458836008843497360416156187511842595352038793\
4543044754351424425877001272963004568523466224175032773792526289116620\
0568336967114120165672550441659487736918062146518195311333334118971437\
64555494331319

In[11]:= n5root = (4 np + 5)^(1/2)

Out[11]= \
1114247699377134855726317142179837991669774193500027654225864197927618\
7646938837316951141336216915442127166483212586214421913115995296844607\
3946658155463253315027850184444739515341546021953572982444114714925658\
0519870859653135390989665115182357512121444199702727957702373225396420\
7216365056061158130605226296647748179164483946460250464229475581745544\
0036374343860347460160207493425647713512071331927925811700396550562457\
3846126215346561195211149928753609216034043894350314242828278541445301\
7773780965470434846252578303623858451376965385995516573524516571330514\
2198625602789862461515560148629318237350159

In[17]:= Mod[n5root^2, np]

Out[17]= 5

In[18]:= Mod[n5root^2, p]

Out[18]= 5

In[19]:= Mod[n5root^2, np/p]

Out[19]= 5

show that np/p is a large composite number that can't be factored

In[22]:= np/p

Out[22]= \
2896728797231704193216809955936005179085860357124327763928880605469952\
9890127008436789926639374159700090035187081671639709475400680850173904\
0058210935814740529974851954492933178526173822540769424561928057025308\
1257357592242862948979902547430700868992340623025119956027913426964695\
8275605565192054755733867646312586793389844610210453703079127599181132\
3778275022514076127981575818233734927751691268453164338584834775401646\
9904577932281754673944241802200714626359063831683748837550009899452654\
4352368244112477441025374597126682484717899443437339805422403580723893\
3002641386756501799284720230157622349756874028010246670229789729282372\
3986813886707581994241628069211456142529347675422400609607277288095115\
1341531104295685383087888884085673305395919840016723826438909922393694\
6141812381089445179866616739862690808926728095173508565815687725169736\
666681638317401920585688059230128574752301883525710237230351401

In[23]:= PrimeQ[np/p]

Out[23]= False

square root of 13 mod 1+11 RSA270^2+RSA270^4[edit]

The square root of 13 mod 1+11 RSA270^2+RSA270^4 is (and this is partial confirmation of the formula given above

If N is the modulus, C is the square and D is the natural :square just below C that

take the factorisation of N-(C-D)=Y

if Y equals (C-D)x^4+(4*C-2*(C-D))*x^2

then Kunerth with the Pythagorean Method below should be :able to take the square root of C mod N quickly.

using the Pythagorean method and Kunerth shown below.

y21=1968527137708915753781396172423958959752843397871385953905541559583361\
7047928713223231088902575813035048789781731014443653341300985605006420\
4150266696006320793043864946273912817379704904250761155345357266156831\
9505939969785925196949573822667063211917988445136037366509246826500102\
3455775675806644650385191815744751597420578815339758689329568471272697\
7962106783779046149327395158869256074859912500865606397449960529827116\
4411243978956599768491187076310593031748078213552442903120664495841764\
0686416399318426826009739029277662686571694061227815713974218476677730\
9160116220693559552200738391668049489625480467424903184317395220271193\
9203555943986135421168957559877095295978323201888953681859832544993604\
5225543394561502975804440555356733543797736990654096227907634817991350\
7981534740325879183669889182467390198771279775847210108538722098532307\
5655374868923845139515003637195406420774970715619765466278800746719990\
1376858572442673550342594754331808347104358909323725678874383676044877\
0364455695150440655288154991280286896110473371117639497577702180738743\
9225451232988061301295313997

In[40]:= Mod[y21^2, (4 + 44 RSA270^2 + 4 RSA270^4)/4]

Out[40]= 13

Endo999 (talk) 06:06, 17 May 2022 (UTC)[reply]

Taking the root of 5 mod p*q which is (x^4+18 x^2+1)[edit]

In order to challenge Rabin's cryptosystem, which is claimed to be as hard as factoring, I am going to show a p*q modulus that is x^4+18x^2+1 where Kunerth can take 1 modular square root of 5 but not two. Therefore Kunerth cannot easily factor p*q but can take the modular square root of 5.

In[16]:= mod = (2^25 + 46)^2 (18 + (2^25 + 46)^2) + 1

set x in x^4+18x^2+1
In[12]:= x = 2^25 + 46

Out[12]= 33554478

Out[16]= 1267657551566006890149842314969

show modulus is a p*q
In[17]:= FactorInteger[mod]

Out[17]= {{109, 1}, {11629885794183549450915984541, 1}}

make the w variable (using the Pythagorean Theorum)

In[19]:= w = 
 Expand[((2 (x^2 - 1^2))^2 + 1 (x^2 - 1^2)^2 + 
      5 (((2 1 x)^2)))/(5)]^(1/2)


Out[19]= 1125902993852485

make the v variable

In[21]:= v = 2 (x^2 - 1)

Out[21]= 2251805987704966

make the modulus 

In[22]:= mod = (x^2 - 1^2)^2 + 5 (((2 1 x)^2))

Out[22]= 1267657551566006890149842314969

solve for alpha and beta 

In[23]:= Solve[a == (w (v + w b)), {a, b}, Integers]

Out[23]= {{a -> 
   ConditionalExpression[
    1267657551565984372089965265285 + 
     1267657551565988875701940675225 C[1], C[1] \[Element] Integers], 
  b -> ConditionalExpression[-1 + C[1], C[1] \[Element] Integers]}}

set beta

In[24]:= beta = -1

Out[24]= -1

set alpha

In[25]:= alpha = 1267657551565984372089965265285

Out[25]= 1267657551565984372089965265285

factor for x1 variable

In[27]:= Timing[
 xxx1 = Factor[(alpha^2 x1^2 + (2 alpha beta - (mod)) x1 + (beta^2 - \
(5)))]]

Out[27]= {0.001683, (-4 + 1267657551565979868477989855361 x1) (1 + 
    1267657551565988875701940675225 x1)}

get the square root of 5

In[28]:= y23 = 
 Mod[alpha (-1 PowerMod[1267657551565988875701940675225, -1, mod]) + 
   beta, mod]

Out[28]= 950743163674505449088130199350

verify root of 5 has been found

In[29]:= Mod[y23^2, mod]

Out[29]= 5

As such if Rabin's cipher is 5 mod P*Q where P*Q is X^4+18x^2+1 then the plaintext can be found, breaking the cipher but the modulus has not been factored.  I don't know how to get the other root either.

Endo999 (talk) 06:22, 6 June 2022 (UTC)[reply]

A modulus with 3 mod 4 primes shown as an example[edit]

The actual Rabin cipher specifies 3 mod 4 semiprimes. I show the root of 7 mod a modulus that has several 3 mod 4 primes.


In[7]:= x = 2^25 + 790

Out[7]= 33555222

In[8]:= w = (((2 (x^2 - 1))^2 + 3 (x^2 - 1)^2 + 7 (2 1 x)^2)/7)^(1/2)

Out[8]= 1125952923469285

In[9]:= v = 2 (x^2 - 1)

Out[9]= 2251905846938566

In[10]:= mod = 3 (x^2 - 1)^2 + 7 (2 1 x)^2

Out[10]= 3803309957607106707727790742219

Notice how the modulus has mostly 3 mod 4 primes.

In[11]:= FactorInteger[mod]

Out[11]= {{3, 1}, {7, 1}, {71707, 1}, {1180987, 1}, {907027753, 
  1}, {2357844607, 1}}

In[12]:= Solve[a == w (v + w b), {a, b}, Integers]

Out[12]= {{a -> 
   ConditionalExpression[
    1267769985869025060348644534085 + 
     1267769985869029564160338411225 C[1], C[1] \[Element] Integers], 
  b -> ConditionalExpression[-1 + C[1], C[1] \[Element] Integers]}}

In[13]:= alpha = 1267769985869025060348644534085

Out[13]= 1267769985869025060348644534085

In[14]:= beta = -1

Out[14]= -1

In[16]:= Timing[
 xx = Factor[alpha^2 x1^2 + (2 alpha beta - mod) x1 + (beta^2 - (7))]]

Out[16]= {0.002433, 
 3 (-2 + 422589995289673518845650218987 x1) (1 + 
    1267769985869029564160338411225 x1)}

In[17]:= y20 = 
 Mod[alpha (-1 PowerMod[1267769985869029564160338411225, -1, mod]) + 
   beta, mod]

Out[17]= 2852482468205330875260535658630

In[18]:= Mod[y20^2, mod]

Out[18]= 7

thus the cipher of 7 has had its root taken without factoring the modulus.  the second root of 7 has not been
found.

This modulus has several 3 mod 4 primes and Kunerth will take the modular square root of 7 for this modulus.

Taking the root of 2 mod (1+RSA260^4)[edit]

Working with modulus (1+RSA260^4) where the I term is RSA260^2

Thus a bridge between squares and roots is known via the Complex Square Root formula when using coefficients of Pythagorean Squares only returns natural square coefficients(see two Australian Innovation Patents 2017101124 and 2017101121) Thus roots can be found of modular squares instantly if the polar coefficients of the square are twice Pythagorean triples.

To briefly explain,

1) take a Pythagorean Triple, such as 3,4,5

2) double 3, and 4 to make 8 and 6. These are the polar coefficients of the square, thus 8+6*I is the square

3) take the root of 4+5 (which is 3). This is the real coefficient of the root, root of 5-4 is 1, this is the imaginary coefficient of the root

4) Thus 3+1*I is the root.

5) Once you know the modular imaginary number you can make a bridge between square and root for any Pythagorean Triple.

In[36]:= Mod[8 + 6 RSA260^2, (1 + RSA260^4)] ==
 Mod[(3 + 1 RSA260^2)^2, (1 + RSA260^4)]

Out[36]= True

With I known, the root of 2 is found via Leonard Dickson's formula for (x^4+1)===0

E=(1+I)/(root of 2), E_1=E*I

(Theory of Algebraic Equations-p 43(1903))

get the square root of 2 mod (1+RSA260^4)

considering that RSA260^2 is I for this modulus
(See Dickson's quote above for the source for this equation)

In[15]:= x6 =
 Reduce[(1 + RSA260^2) == x RSA260, {x}, Modulus -> RSA260^4 + 1]

Out[15]= x == \
2390985582622011804596626598395673467700135963629555889132984599258038\
5378407468442673330055684425335333246848835333293215726575872135568512\
5318060112890318777229278719348539134043483869594721596706402465110106\
0452794751171383943446773743600355859434238217228678258280466454474506\
7047769769903628871465840267290863853610037337134588190023227271092598\
5562318397716277610476863026778615232203106043273058626818827630384175\
9479841322242544292233604728629381109020566613070567544288470636075157\
5795994034265171336190833826812096818624770027548542741892092041279704\
3877187671645165702086770947823616335358481804813828489302226736083919\
8037064379650707007910654350339367136086946104320051390020952377229881\
9786493773024231171608856573158644157537927320149589850044116033963226\
7387534225217176326179777658723207656613354776250973890776137426683101\
1159663177479992648516657821624546868880590666965892418956501837057699\
8523003495518762124028306405552801995847971288509008824915391663323682\
2140993187141745318730151746076326575176657135023818410802

show the root of 2 has been found

In[19]:= Mod[
 239098558262201180459662659839567346770013596362955588913298459925803\
8537840746844267333005568442533533324684883533329321572657587213556851\
2531806011289031877722927871934853913404348386959472159670640246511010\
6045279475117138394344677374360035585943423821722867825828046645447450\
6704776976990362887146584026729086385361003733713458819002322727109259\
8556231839771627761047686302677861523220310604327305862681882763038417\
5947984132224254429223360472862938110902056661307056754428847063607515\
7579599403426517133619083382681209681862477002754854274189209204127970\
4387718767164516570208677094782361633535848180481382848930222673608391\
9803706437965070700791065435033936713608694610432005139002095237722988\
1978649377302423117160885657315864415753792732014958985004411603396322\
6738753422521717632617977765872320765661335477625097389077613742668310\
1115966317747999264851665782162454686888059066696589241895650183705769\
9852300349551876212402830640555280199584797128850900882491539166332368\
22140993187141745318730151746076326575176657135023818410802^2, (1 +
   RSA260^4)]

Out[19]= 2

get an answer for x^4+1 mod (1+RSA260^4) === 0

In[16]:= x7 =
 Mod[RSA260^2 (1 + RSA260^2) PowerMod[
    239098558262201180459662659839567346770013596362955588913298459925\
8038537840746844267333005568442533533324684883533329321572657587213556\
8512531806011289031877722927871934853913404348386959472159670640246511\
0106045279475117138394344677374360035585943423821722867825828046645447\
4506704776976990362887146584026729086385361003733713458819002322727109\
2598556231839771627761047686302677861523220310604327305862681882763038\
4175947984132224254429223360472862938110902056661307056754428847063607\
5157579599403426517133619083382681209681862477002754854274189209204127\
9704387718767164516570208677094782361633535848180481382848930222673608\
3919803706437965070700791065435033936713608694610432005139002095237722\
9881978649377302423117160885657315864415753792732014958985004411603396\
3226738753422521717632617977765872320765661335477625097389077613742668\
3101115966317747999264851665782162454686888059066696589241895650183705\
7699852300349551876212402830640555280199584797128850900882491539166332\
36822140993187141745318730151746076326575176657135023818410802, -1, \
(1 + RSA260^4)/2], ( 1 + RSA260^4)/2]

Out[16]= 1081266425870845006321405218280810134086525602165860424867891\
7543755761716705486383079971046930041357598644852896093496463974055460\
1381075511557252435695234701897308802965178845241724455263211737849342\
7128524014096539214086108336511443955341784431087391973664011736962323\
4605944848288493582384950338754807922081452680451479689707791351350589\
8641790001125921948840266217415254076141289527461586948306601183448218\
2730038307171502099790738219814627067967915896841594568823420876009806\
3687864509758916785207979778729869523169934220354650821198140419950934\
4133353470102445210155739906936350120886108678774436571169599678678981\
1757295785441382581952396103400801305159693249335218141169941996812851\
5159132934420996270177387886126548768806950194545184798859978189208672\
802253296159654599

In[25]:= Mod[1 + x7^4, 1 + RSA260^4]

Out[25]= 0

Endo999 (talk) 21:35, 25 August 2022 (UTC)[reply]

We show here that with the square root of 2 mod 1+RSA260^4 known we can take roots of polar coefficients of Pythagorean Triples.

We saw how 8+6*I was the square and 3+1*I was the root. Now we see how (4+3*I) is the square and (3+1*I)/(root of 2) is the root.


this is the root of 2

In[9]:= x = \
2390985582622011804596626598395673467700135963629555889132984599258038\
5378407468442673330055684425335333246848835333293215726575872135568512\
5318060112890318777229278719348539134043483869594721596706402465110106\
0452794751171383943446773743600355859434238217228678258280466454474506\
7047769769903628871465840267290863853610037337134588190023227271092598\
5562318397716277610476863026778615232203106043273058626818827630384175\
9479841322242544292233604728629381109020566613070567544288470636075157\
5795994034265171336190833826812096818624770027548542741892092041279704\
3877187671645165702086770947823616335358481804813828489302226736083919\
8037064379650707007910654350339367136086946104320051390020952377229881\
9786493773024231171608856573158644157537927320149589850044116033963226\
7387534225217176326179777658723207656613354776250973890776137426683101\
1159663177479992648516657821624546868880590666965892418956501837057699\
8523003495518762124028306405552801995847971288509008824915391663323682\
2140993187141745318730151746076326575176657135023818410802

Out[9]= 23909855826220118045966265983956734677001359636295558891329845\
9925803853784074684426733300556844253353332468488353332932157265758721\
3556851253180601128903187772292787193485391340434838695947215967064024\
6511010604527947511713839434467737436003558594342382172286782582804664\
5447450670477697699036288714658402672908638536100373371345881900232272\
7109259855623183977162776104768630267786152322031060432730586268188276\
3038417594798413222425442922336047286293811090205666130705675442884706\
3607515757959940342651713361908338268120968186247700275485427418920920\
4127970438771876716451657020867709478236163353584818048138284893022267\
3608391980370643796507070079106543503393671360869461043200513900209523\
7722988197864937730242311716088565731586441575379273201495898500441160\
3396322673875342252171763261797776587232076566133547762509738907761374\
2668310111596631774799926485166578216245468688805906669658924189565018\
3705769985230034955187621240283064055528019958479712885090088249153916\
633236822140993187141745318730151746076326575176657135023818410802


show this is the root of 2

In[10]:= Mod[x^2, 1 + RSA260^4]

Out[10]= 2

Now show bridge between square and root

In[13]:= Mod[4 + 3 RSA260^2, (1 + RSA260^4)/2] == 
 Mod[((3 + 1 RSA260^2) PowerMod[x, -1, ( 1 + RSA260^4)/2])^2, ( 
    1 + RSA260^4)/2]

Out[13]= True

where RSA260^2 is I

Endo999 (talk) 20:01, 19 September 2022 (UTC)[reply]

The Root of (RSA260+1)/2 mod ((RSA260+1)/2)(1+RSA260^2)^2[edit]


Get the square of PowerMod[2,-1,RSA260] in the modulus of ((1+RSA260)/2)(1+RSA260^2)^2
show the root of this in modulus ((1+RSA260)/2)(1+RSA260^2)^2

Show what the modulus is algebraicly

In[6]:= Factor[
 Expand[2 (((R + 1)/2) (R^2 - 1)^2 + ((R + 1)/2) (2 1 R)^2)]]

Out[6]= (1 + RSA260) (1 + RSA260^2)^2


In[1]:= RSA260 = \
2211282552952966643528108525502623092761208950247001539441374831912882\
2941402001986512729726569746599085900330031400051170742204560859276357\
9537571859542988389587092292384910067030341246205457845664136645406842\
14361293017694020846391065875914794251435144458199


Out[1]= 22112825529529666435281085255026230927612089502470015394413748\
3191288229414020019865127297265697465990859003300314000511707422045608\
5927635795375718595429883895870922923849100670303412462054578456641366\
4540684214361293017694020846391065875914794251435144458199

In[2]:= w = (((RSA260^2 - 1)^2 + 
      Floor[RSA260/2] (RSA260^2 - 1)^2 + (Floor[RSA260/2] + 
         1) (2 1 RSA260)^2)/(Floor[RSA260/2] + 1))^(1/2)

Out[2]= 48897705289941897278515656316900240171650055557292696823953325\
8635666453424544129253981802360653145003762959469853542541818050387424\
7236254299925216547878374916180483196313640403881912534846982553136987\
4247368758362200396104573045243051200451656653985909295009840745370213\
3326714061654556142686232796729554029073220559768956005931866053289115\
1695936264562194804751978316341066629080189896385088450648277821022198\
3317787938356586115384593121867887478906081852529924976333801078939072\
1301760772016869260727399301258323602


In[3]:= v = RSA260^2 - 1

Out[3]= 48897705289941897278515656316900240171650055557292696823953325\
8635666453424544129253981802360653145003762959469853542541818050387424\
7236254299925216547878374916180483196313640403881912534846982553136987\
4247368758362200396104573045243051200451656653985909295009840745370213\
3326714061654556142686232796729554029073220559768956005931866053289115\
1695936264562194804751978316341066629080189896385088450648277821022198\
3317787938356586115384593121867887478906081852529924976333801078939072\
1301760772016869260727399301258323600


show how the modulus is related to RSA260

In[24]:= Mod[-2 mod, RSA260]

Out[24]= 1


In[4]:= mod = (Floor[
     RSA260/2]) (RSA260^2 - 1)^2 + (Floor[(RSA260/2)] + 
     1) (2 1 RSA260)^2

Out[4]= 26435723516070693100189756964804120024776648566924453782352227\
7211795394121417578932806020869967734682188876541159690922459425400330\
9986748787710594103841451179831467979072549624154858195724428497259940\
4391103037814547220868968673295799269196230781319012594209718448733722\
4760520508775914416742055540215382930131797526660579775614532469807143\
7186530838360502099530304019990933842108524873839278615523961151874684\
4909425809698334574926510303147427984039013125518098205595077675506504\
1454989956159868245576878718966899528975424172732334093874460993535088\
8599150331122375793326975354334931955085621103067197681422156161934502\
1199989700747383133923611092115451530355492550044483178015701030209920\
8921109948861654305838902562737986540144757112591497458858888352400935\
0407756344451816048452471461214916112373546097888613035620235064956940\
4613339768137308087453315249886394327840865483340627056794941207885893\
1683570542993626039466617291606361627412692812143903429426718085372103\
5867211651900757793532956548660752428558580750840250073684397802941830\
8511188811093694104098555018460656877915716721750825637265351783886200\
5089787771712625288677127010894479146752069195253840741485518144992336\
1367720804067817721840348194134798685417015872695424034656719812720722\
748888900292925280793257601095066848054996400


In[5]:= x11 = Solve[a == w (v + w b), {a, b}, Integers]

Out[5]= {{a -> 
   ConditionalExpression[
    239098558262201180459662659839567346770013596362955588913298459925\
8038537840746844267333005568442533533324684883533329321572657587213556\
8512531806011289031877722927871934853913404348386959472159670640246511\
0106045279475117138394344677374360035585943423821722878638492305353897\
5138845298805071376295799144243315128872150179171271075986057186557908\
9703249235975531492246337295652324258928766324415082421435206239715385\
4365678864428742138953395805999184111895836327946547197719820987924690\
8808723994937604960242358280749082383378094823062203337159125033053631\
3579868510975309784615356646065561496768594834598381394108149711076270\
5661329114052094023446949760265694055058430521910815076854023093145105\
1863441356174094012801320342539657952016734429610660056574172263683194\
1099725705737303857115130093242158254235252153718398589463282713760626\
0046431849583417465140308810169395852808187090739324412255670298965462\
2431339667285983629286381656367962387588485038653149903846248783094547\
09284149077779730646846220929759663449907934665136884833607200 + 
     23909855826220118045966265983956734677001359636295558891329845992\
5803853784074684426733300556844253353332468488353332932157265758721355\
6851253180601128903187772292787193485391340434838695947215967064024651\
1010604527947511713839434467737436003558594342382172287863849230535389\
7513884529880507137629579914424331512887215017917127107598605718655790\
8970324923597553149224633729565232425892876632441508242143520623971538\
5436567886442874213895339580599918411189583632794654719771982098792469\
0880872399493760496024235828074909216291915281144165904029038841310166\
5687997962556070343252200837319885218167742068539474186623877871182886\
2460103619913573012422179920751655404010174009758579831295066235587318\
5962726642586805911907529519201340962445681365052526910518441235401452\
4907154429575698534785555675858497058514648069096495793537408852840473\
7958434386144714957171853914935664876524714804113498768046899611500344\
1520151656858253927133077831992555005890570811557177427742374456431091\
759882648604455752225627663533281207483646456119935487350254404 C[1], 
    C[1] \[Element] Integers], 
  b -> ConditionalExpression[C[1], C[1] \[Element] Integers]}}


In[6]:= alpha = a /. x11 /. C[1] -> 0

Out[6]= {2390985582622011804596626598395673467700135963629555889132984\
5992580385378407468442673330055684425335333246848835333293215726575872\
1355685125318060112890318777229278719348539134043483869594721596706402\
4651101060452794751171383943446773743600355859434238217228786384923053\
5389751388452988050713762957991442433151288721501791712710759860571865\
5790897032492359755314922463372956523242589287663244150824214352062397\
1538543656788644287421389533958059991841118958363279465471977198209879\
2469088087239949376049602423582807490823833780948230622033371591250330\
5363135798685109753097846153566460655614967685948345983813941081497110\
7627056613291140520940234469497602656940550584305219108150768540230931\
4510518634413561740940128013203425396579520167344296106600565741722636\
8319410997257057373038571151300932421582542352521537183985894632827137\
6062600464318495834174651403088101693958528081870907393244122556702989\
6546224313396672859836292863816563679623875884850386531499038462487830\
9454709284149077779730646846220929759663449907934665136884833607200}

In[7]:= beta = b /. x11 /. C[1] -> 0

Out[7]= {0}

In[8]:= Timing[
 xx = Factor[
   alpha^2 x^2 + (2 alpha beta - 
       mod) x + (beta^2 - ((Floor[RSA260/2] + 1)))]]

Out[8]= {0.01033, \
{110564127647648332176405426275131154638060447512350076972068741595644\
1147070100099325636486328487329954295016501570002558537110228042963817\
8976878592977149419479354614619245503351517062310272892283206832270342\
107180646508847010423195532937957397125717572229100 (-1 + 
     21625328517416900126428104365616202681730512043317208497357835087\
5115234334109727661599420938600827151972897057921869929279481109202762\
1510231145048713904694037946176059303576904834489105264234756986854257\
0480281930784281722166730228879106835688621747839473279256785140670373\
9441262638608267650972445085046983089688818364421080826758536129212203\
9439550387809976052732454334373014462180471746794241046025164633407892\
5782907333402733086683619910034389961807309434406429093250276188205284\
2681146568095613828264777415531460988278822459756560975953602795309923\
4987638237604385391803435271975466760682517268394958721388380363711294\
9592377814223481525533669279783257630786410356098789722654346057740612\
9973632350018706640058943255166425091562242735389525056302129269945612\
05119513745600 x) (1 + 
     23909855826220118045966265983956734677001359636295558891329845992\
5803853784074684426733300556844253353332468488353332932157265758721355\
6851253180601128903187772292787193485391340434838695947215967064024651\
1010604527947511713839434467737436003558594342382172287863849230535389\
7513884529880507137629579914424331512887215017917127107598605718655790\
8970324923597553149224633729565232425892876632441508242143520623971538\
5436567886442874213895339580599918411189583632794654719771982098792469\
0880872399493760496024235828074909216291915281144165904029038841310166\
5687997962556070343252200837319885218167742068539474186623877871182886\
2460103619913573012422179920751655404010174009758579831295066235587318\
5962726642586805911907529519201340962445681365052526910518441235401452\
4907154429575698534785555675858497058514648069096495793537408852840473\
7958434386144714957171853914935664876524714804113498768046899611500344\
1520151656858253927133077831992555005890570811557177427742374456431091\
759882648604455752225627663533281207483646456119935487350254404 x)}}


this is the root

In[9]:= y201 = 
 Mod[alpha (-1 PowerMod[
       239098558262201180459662659839567346770013596362955588913298459\
9258038537840746844267333005568442533533324684883533329321572657587213\
5568512531806011289031877722927871934853913404348386959472159670640246\
5110106045279475117138394344677374360035585943423821722878638492305353\
8975138845298805071376295799144243315128872150179171271075986057186557\
9089703249235975531492246337295652324258928766324415082421435206239715\
3854365678864428742138953395805999184111895836327946547197719820987924\
6908808723994937604960242358280749092162919152811441659040290388413101\
6656879979625560703432522008373198852181677420685394741866238778711828\
8624601036199135730124221799207516554040101740097585798312950662355873\
1859627266425868059119075295192013409624456813650525269105184412354014\
5249071544295756985347855556758584970585146480690964957935374088528404\
7379584343861447149571718539149356648765247148041134987680468996115003\
4415201516568582539271330778319925550058905708115571774277423744564310\
91759882648604455752225627663533281207483646456119935487350254404 , \
-1, mod/16]) + beta, mod/16]

Out[9]= {2703166064677112515803513045702025335216314005414651062169729\
3859389404291763715957699927617325103393996612132240233741159935138650\
3452688778893131089238086754743272007412947113104311138158029344623356\
7821310035241348035215270841278609888354461077718479934159907098142583\
7967430157829826033456371555635630872886211102295552635103344817016151\
5254929943798476247006591556791796626807772558968349280130753145579175\
9865722863416675341635835452488754298745225913679300803636656284523525\
6605335143321011951728533097176941432734098980455117902298399626624544\
8950754059254824048943696116824953374492155414757875006326502034875418\
2068864062926803520561793989089611086180726894271661768194686407876463\
0799761874666855067252839436229599224208251745430393794863993095538317\
17276357511447300}


show an interesting relation between the square and the root mod (1+RSA260^4)

In[10]:= Mod[PowerMod[y201, 2, (1 + RSA260^4)], RSA260] == 
 Mod[PowerMod[y201, 1, (1 + RSA260^4)], RSA260]

Out[10]= True


show the square is equal to 1/2 mod RSA260

In[11]:= Mod[y201^2, mod/16]

Out[11]= {\
1105641276476483321764054262751311546380604475123500769720687415956441\
1470701000993256364863284873299542950165015700025585371102280429638178\
9768785929771494194793546146192455033515170623102728922832068322703421\
07180646508847010423195532937957397125717572229100}


In[12]:= PowerMod[2, -1, RSA260]

Out[12]= 1105641276476483321764054262751311546380604475123500769720687\
4159564411470701000993256364863284873299542950165015700025585371102280\
4296381789768785929771494194793546146192455033515170623102728922832068\
32270342107180646508847010423195532937957397125717572229100

Endo999 (talk) 19:07, 26 August 2022 (UTC)[reply]

Nontrivial Factorisation of (-1+RSA260^2)/3 found using Kunerth[edit]

The following work will show two non trivial factors of 
(-1+RSA260^2)/3

They are 

get two factors, in this case the trivial factorisation
is (RSA260-1)(RSA260+1), and in our case the factor of 100 has been taken off both factors. 

In[53]:= p = GCD[ui2 - 1, (-1 + RSA260^2)]

Out[53]= {\
2211282552952966643528108525502623092761208950247001539441374831912882\
2941402001986512729726569746599085900330031400051170742204560859276357\
9537571859542988389587092292384910067030341246205457845664136645406842\
143612930176940208463910658759147942514351444582}


In[54]:= q = GCD[ui2 + 1, (-1 + RSA260^2)]

Out[54]= {\
7370941843176555478427028418342076975870696500823338464804582773042940\
9804673339955042432421899155330286334433438000170569140681869530921193\
1791906198476627965290307641283033556767804154018192818880455484689473\
812043100589800694879702195863826475047838148606600}

show that these two numbers equate to modulus
In[57]:= p q == (-1 + RSA260^2)/3

Out[57]= {\
1629923509664729909283855210563341339055001851909756560798444195452221\
5114151470975132726745355104833458765315661784751393935012914157454180\
9997507218262612497206016106543788013462730417828232751771232914157895\
8612073346536819101508101706681721888466196976500328024845673777755713\
5388485204756207759890985134302440685325631866864395535109637172319787\
5485406493491732610544702220969339663212836281688275927367406611059293\
1278552870512819770728929582630202728417664165877793369297969071005869\
24005623086909133100419441200} == \
1629923509664729909283855210563341339055001851909756560798444195452221\
5114151470975132726745355104833458765315661784751393935012914157454180\
9997507218262612497206016106543788013462730417828232751771232914157895\
8612073346536819101508101706681721888466196976500328024845673777755713\
5388485204756207759890985134302440685325631866864395535109637172319787\
5485406493491732610544702220969339663212836281688275927367406611059293\
1278552870512819770728929582630202728417664165877793369297969071005869\
24005623086909133100419441200


Now show the Kunerth work




Use Complex numbers in the denominator  square is 8+6 I) 
root is 3+ I


In[9]:= w10 = ((((8 + 6 I + (8 + 6 I) (  RSA260^2 - 1))))/(8 + 
      6 I))^(1/2)

Out[9]= 22112825529529666435281085255026230927612089502470015394413748\
3191288229414020019865127297265697465990859003300314000511707422045608\
5927635795375718595429883895870922923849100670303412462054578456641366\
4540684214361293017694020846391065875914794251435144458199

In[10]:= v10 = 3 + I

Out[10]= 3 + I


In[11]:= mod = (8 + 6 I) (RSA260^2 - 1)

Out[11]= 3911816423195351782281252505352019213732004444583415745916266\
0690853316273963530340318544188852251600301036757588283403345444030993\
9778900343994017323830269993294438655705091232310553002787758604250958\
9939789500668976031688365843619444096036132532318872743600787259629617\
0666137124932364491414898623738364322325857644781516480474549284263129\
2135674901164975584380158265307285330326415191710807076051862225681775\
8665423035068526889230767449749430998312486548202393998106704086315125\
770414086176134954085819194410066588800 + 
 293386231739651383671093937901401441029900333343756180943719955181399\
8720547264775523890814163918870022577756819121255250908302324548341752\
5799551299287270249497082899177881842423291475209081895318821924548421\
2550173202376627438271458307202709939923915455770059044472221279996028\
4369927336856117396780377324174439323358613736035591196319734691017561\
7587373168828511869898046399774481139378310530703889666926133189990672\
7630139516692307558731207324873436491115179549858002806473634432781056\
4632101215564364395807549941600 I



In[13]:= alpha = v10 w10

Out[13]= 6633847658858899930584325576507869278283626850741004618324124\
4957386468824206005959538189179709239797257700990094200153512226613682\
5778290738612715578628965168761276877154730201091023738616373536992409\
93622052643083879053082062539173197627744382754305433374597 + 
 221128255295296664352810852550262309276120895024700153944137483191288\
2294140200198651272972656974659908590033003140005117074220456085927635\
7953757185954298838958709229238491006703034124620545784566413664540684\
214361293017694020846391065875914794251435144458199 I

In[14]:= beta = 0

Out[14]= 0


In[15]:= Timing[
 xx = Factor[
   alpha^2 x^2 + (2 alpha beta - mod) x + (beta^2 - (8 + 6 I))]]

Out[15]= {0.078202, (8 + 6 I) (-1 + x) (1 + 
    488977052899418972785156563169002401716500555572926968239533258635\
6664534245441292539818023606531450037629594698535425418180503874247236\
2542999252165478783749161804831963136404038819125348469825531369874247\
3687583622003961045730452430512004516566539859092950098407453702133326\
7140616545561426862327967295540290732205597689560059318660532891151695\
9362645621948047519783163410666290801898963850884506482778210221983317\
7879383565861153845931218678874789060818525299249763338010789390721301\
760772016869260727399301258323601 x)}



In[19]:= y221 = 
 Mod[alpha (-1 PowerMod[
       889770528994189727851565631690024017165005555729269682395332586\
3566645342454412925398180236065314500376295946985354254181805038742472\
3625429992521654787837491618048319631364040388191253484698255313698742\
4736875836220039610457304524305120045165665398590929500984074537021333\
2671406165455614268623279672955402907322055976895600593186605328911516\
9593626456219480475197831634106662908018989638508845064827782102219833\
1778793835658611538459312186788747890608185252992497633380107893907213\
01760772016869260727399301258323601, -1, ( RSA260^2 - 1)/3]) + 
   beta , ( RSA260^2 - 1)/3]

Out[19]= 4196011502678228522651394674668421599244198885219399131026904\
3289669343577155055101920106196150772487107982269688214060323403496639\
0066796195613254878752266922653202654974394238033891827146108341535789\
7064021932851214217179647002005696802218962975079798254077514295596533\
6989462233404330808446291888976180740040612923112825511380322657407122\
7936139526603078738677239607595847651818136269895877292246515919558991\
1613999769739099050764205062230787783633643396360497705733443250472625\
3412595543910269408426978715859232603 + 
 683174886644184253849664892676727832993140580143898824633711542782971\
6490622325495108245788323394027389854514210202052475425120859352707380\
9852944235379279729823778790680409145755373200180947861974937294932705\
0632398256084927933902890462301206061991392267302693151468442382550111\
9576306095200278982929534402768833992545638139334142600283449817227060\
9381904789119818857101428995383717763400808003637642506441101909066430\
2750820925196413425650669453664522356017904645483712564781743868377274\
89305297498445370605426224601 I


This above is supposed to be the square root of 8+6 I or 3+I

In[21]:= yyy = 
 Solve[3 + II == 
   4196011502678228522651394674668421599244198885219399131026904328966\
9343577155055101920106196150772487107982269688214060323403496639006679\
6195613254878752266922653202654974394238033891827146108341535789706402\
1932851214217179647002005696802218962975079798254077514295596533698946\
2233404330808446291888976180740040612923112825511380322657407122793613\
9526603078738677239607595847651818136269895877292246515919558991161399\
9769739099050764205062230787783633643396360497705733443250472625341259\
5543910269408426978715859232603 + 
    683174886644184253849664892676727832993140580143898824633711542782\
9716490622325495108245788323394027389854514210202052475425120859352707\
3809852944235379279729823778790680409145755373200180947861974937294932\
7050632398256084927933902890462301206061991392267302693151468442382550\
1119576306095200278982929534402768833992545638139334142600283449817227\
0609381904789119818857101428995383717763400808003637642506441101909066\
4302750820925196413425650669453664522356017904645483712564781743868377\
27489305297498445370605426224601 II, {II}, Modulus -> (RSA260^2 - 1)/3]

Out[21]= {{II -> 
   8149617548323649546419276052816706695275009259548782803992220977261\
1075570757354875663633726775524167293826578308923756969675064570787270\
9049987536091313062486030080532718940067313652089141163758856164570789\
4793060366732684095507540508533408609442330984882501640124228368888778\
5676942426023781038799454925671512203426628159334321977675548185861598\
9377427032467458663052723511104846698316064181408441379636837033055296\
4656392764352564098853644647913151013642088320829388966846489845355029\
34620028115434545665502097203 + 
    814961754832364954641927605281670669527500925954878280399222097726\
1107557075735487566363372677552416729382657830892375696967506457078727\
0904998753609131306248603008053271894006731365208914116375885616457078\
9479306036673268409550754050853340860944233098488250164012422836888877\
8567694242602378103879945492567151220342662815933432197767554818586159\
8937742703246745866305272351110484669831606418140844137963683703305529\
6465639276435256409885364464791315101364208832082938896684648984535502\
934620028115434545665502097206 C[1]}}

Solve for I (but instead we get square root of 9)

In[65]:= Mod[II^2 , (-1 + RSA260^2)/3] /. yyy /. C[1] -> 0

Out[65]= {9}


This is not the natural root of 9 so we can find the square root of 1

In[34]:= ui = 
 Mod[II PowerMod[3, -1, (RSA260^2 - 1)/3], (RSA260^2 - 1)/3] /. 
   yyy /. C[1] -> 0 

Out[34]= {\
5460243757376845196100914955387193485834256203897684478674788054764942\
0632407427766694634596939601192086863807466978917169682293262427471506\
3491649181179751865640153956921689845100146899724579718433630262428951\
1350445710898343990052140717383768326361759871276098883233007155481640\
3551425435933295995634800199913176295840866753995725042617284527271288\
2876111753197304245324752440247287871763001543655724356680812147048631\
9783152116217946231941914101811179140199174955690607787148196387869661\
9541883734114559588640512801}

In[47]:= Mod[ui^2, (-1 + RSA260^2)/3]

Out[47]= {1}

so square root of 1 is found, can now get factors of (-1+RSA260^2)/3

In[43]:= GCD[ui - 1, (RSA260^2 - 1)/3]

Out[43]= {400}

In[39]:= ty = GCD[ui + 1, (RSA260^2 - 1)/3]

Out[39]= {\
8149617548323649546419276052816706695275009259548782803992220977261107\
5570757354875663633726775524167293826578308923756969675064570787270904\
9987536091313062486030080532718940067313652089141163758856164570789479\
3060366732684095507540508533408609442330984882501640124228368888778567\
6942426023781038799454925671512203426628159334321977675548185861598937\
7427032467458663052723511104846698316064181408441379636837033055296465\
6392764352564098853644647913151013642088320829388966846489845355029346\
20028115434545665502097206}

show factorisation of (-1+RSA260^2)/3 is found

In[41]:= ty 400 == 2 (RSA260^2 - 1)/3

Out[41]= {\
3259847019329459818567710421126682678110003703819513121596888390904443\
0228302941950265453490710209666917530631323569502787870025828314908361\
9995014436525224994412032213087576026925460835656465503542465828315791\
7224146693073638203016203413363443776932393953000656049691347555511427\
0776970409512415519781970268604881370651263733728791070219274344639575\
0970812986983465221089404441938679326425672563376551854734813222118586\
2557105741025639541457859165260405456835328331755586738595938142011738\
48011246173818266200838882400} == \
3259847019329459818567710421126682678110003703819513121596888390904443\
0228302941950265453490710209666917530631323569502787870025828314908361\
9995014436525224994412032213087576026925460835656465503542465828315791\
7224146693073638203016203413363443776932393953000656049691347555511427\
0776970409512415519781970268604881370651263733728791070219274344639575\
0970812986983465221089404441938679326425672563376551854734813222118586\
2557105741025639541457859165260405456835328331755586738595938142011738\
48011246173818266200838882400

how let's take the two square roots of 1 we know , ui and RSA260 

In[50]:= ui2 = 
 Mod[ui PowerMod[RSA260, -1, (-1 + RSA260^2)/3], (-1 + RSA260^2)/3]

Out[50]= {\
1083899133927045389673763715024621990471576231519988112930965389975727\
3050910728198463263285661144714250078934915086859676966783587914707030\
3648342300144637310642000710851619028952715727855774779927869887915000\
7477028775446984702502887634943345055830020989372497008267077765543196\
6924817158539785399118554867309583614366713278582528890647710068319686\
0628048719086101855980826925773868671475676850964749734513371097515471\
2207945273980958117193491966991239150261101263466588977652972492010439\
13397863438000322076634470199}

show this number is a root of 1 for the modulus given

In[62]:= Mod[ui2^2, (-1 + RSA260^2)/3]

Out[62]= {1}

get two factors

In[53]:= p = GCD[ui2 - 1, (-1 + RSA260^2)]

Out[53]= {\
2211282552952966643528108525502623092761208950247001539441374831912882\
2941402001986512729726569746599085900330031400051170742204560859276357\
9537571859542988389587092292384910067030341246205457845664136645406842\
143612930176940208463910658759147942514351444582}


In[54]:= q = GCD[ui2 + 1, (-1 + RSA260^2)]

Out[54]= {\
7370941843176555478427028418342076975870696500823338464804582773042940\
9804673339955042432421899155330286334433438000170569140681869530921193\
1791906198476627965290307641283033556767804154018192818880455484689473\
812043100589800694879702195863826475047838148606600}

show factorisation has been found

In[57]:= p q == (-1 + RSA260^2)/3

Out[57]= {\
1629923509664729909283855210563341339055001851909756560798444195452221\
5114151470975132726745355104833458765315661784751393935012914157454180\
9997507218262612497206016106543788013462730417828232751771232914157895\
8612073346536819101508101706681721888466196976500328024845673777755713\
5388485204756207759890985134302440685325631866864395535109637172319787\
5485406493491732610544702220969339663212836281688275927367406611059293\
1278552870512819770728929582630202728417664165877793369297969071005869\
24005623086909133100419441200} == \
1629923509664729909283855210563341339055001851909756560798444195452221\
5114151470975132726745355104833458765315661784751393935012914157454180\
9997507218262612497206016106543788013462730417828232751771232914157895\
8612073346536819101508101706681721888466196976500328024845673777755713\
5388485204756207759890985134302440685325631866864395535109637172319787\
5485406493491732610544702220969339663212836281688275927367406611059293\
1278552870512819770728929582630202728417664165877793369297969071005869\
24005623086909133100419441200

Endo999 (talk) 12:59, 9 October 2022 (UTC)[reply]

Square Root of 5 mod 5*RSA270^2-1[edit]

This is the modulus for a quadratic with ((S+1)/2) being the 
second square in the pythagorean expansion

take the square root of 5

for the modulus

5 RSA270^2-1



In[3]:= Factor[
 Expand[4 ((S^2 + ((S + 1)/2)^2))^2 - 5 (S 2 ((S + 1)/2) )^2]]

Out[3]= 1/4 (-1 - 4 S + S^2) (-1 + 5 S^2)


y25= 1165542651722037722638188284553402620728099062401527245214743059842479\
5912256789143394418465928855820910695963428632915745653033631345567701\
3804896583170813346973298098213872136943300938448156734352029533373451\
5619553741388032743245759604063496548832937573677282974966035


show the square root of 5 has been found

In[16]:= Mod[y25^2, 5 RSA270^2 - 1]

Out[16]= 5

A square root of 1 is found

In[18]:= Mod[(y25 RSA270)^2, 5 RSA270^2 - 1]

Out[18]= 1


Generally, any modulus of X*R^2-1 will have the root of X as X*R.

Endo999 (talk) 21:15, 18 October 2022 (UTC)[reply]

Link between Adolf Kunerth and Joseph or Otto Petzval[edit]

^[2] Translating from the German at ^[3]

The w. M. Mr. Hofrath Petzval presented a treatise by Prof. Adolf Kunerth at the secondary school in Brunn, entitled: "Practical method for the numerical resolution of indefinite quadratic equations in whole and in rational numbers".

So it appears that a Mr Petzval presented the treatise of Kunerth's. Hofrath is a German word for Counsellor, so this may be an honorific. There is a Joseph Petzval who was a very well known and important Austrian/Hungarian mathematician. In 1878 when this paper was published Petzval had retired and was becoming a recluse in Kahlenberg, outside Vienna. Petzval was a mathematician of great reknown and is important in the history of optics. He was also a good engineer earlier in his career, as Kunerth was. It's possible that Kunerth actually existed, as an engineer, and that Petzval used his name for various reasons that are unknown, to publish Petzval's math on the modular square root algorithm. Petzval was a mathematician who could have produced the math presented in the papers authored by Kunerth.

This is a speculation. Against this argument, Petzval doesn't seem to have done any number theory. It's also possible that it was his brother, Petrol Petzval, who was also a mathematician. Endo999 (talk) 02:49, 25 October 2022 (UTC). Petrol, better known as [| Otto Petzval], wrote several math books for high schools in Hungaria. It is more likely that Otto Petzval gave the lecture before a secondary school, but Otto was not known for independent math. Endo999 (talk) 00:52, 31 October 2022 (UTC)[reply]

Dickson's three volume "Theory of Numbers" only mentions Petzval once in the author's index and then only in a footnote on a page. Petzval was not known as a Number Theory man.Endo999 (talk) 10:21, 25 October 2022 (UTC)[reply]

One Hypothesis I have come up with regarding Petzval and Kunerth is that Kunerth was a student of Petzval, and they both worked on the math together. Petzval was known to be nice to his students, so Petzval gave the naming rights to the math paper to Kunerth, which would undoubtedly have helped his career. Endo999 (talk) 19:34, 8 January 2023 (UTC)[reply]

References

^ url=https://www.amazon.com./Unlimited-Congruent-Squares-Kunerth-Algorithm-ebook/dp/B0D1KDGJ3M/ref=sr_1_4?dib=eyJ2IjoiMSJ9.vnAuzEUQeyJUFIgaUkfmv0zAY35k8z5Xx3sm9TnxXMTx54p7uId0BnwWX7Qy8YQ5i6o5QfbZVxmMvL-uoV3YMADJFNcGeKMwrbdX6HjG1P5zzwY9oTE63yF4DuCh9XaPp7FF5bXvnofwZSXB5MAacVIzL83PmcpVfV5B_f9NXPX86wXOHVo53JFxJgaUlkBvQ2uWpgewBfXPSE5ud09rdsFtBFkXpK7CtFaulWzZMKE.M4uyUgrzxxgep1jLdeebnSoW2nKtaHBP3TfUr0aMSI4&dib_tag=se&keywords=paul+cheffers&qid=1713497200&sr=8-4, title="Unlimited Congruent Squares Using the Kunerth Modular Square Root Algorithm"
^ url=https://mathshistory.st-andrews.ac.uk/Biographies/Petzval/
^ url=https://www.zobodat.at/pdf/SBAWW_78_0244-0248.pdf, p245

Root of -1 mod (1+RSA260^4)/2[edit]

the root found will be -RSA260^2, but the exercise shows that the algorithm does find the square root of -1 for a very big number.

RSA260 = 2211282552952966643528108525502623092761208950247001539441374\
8319128822941402001986512729726569746599085900330031400051170742204560\
8592763579537571859542988389587092292384910067030341246205457845664136\
64540684214361293017694020846391065875914794251435144458199

In[2]:= w = ((((RSA260^2 - 1)^2) - 
      2 (RSA260^2 - 1)^2 - (2 1 RSA260)^2)/(-1))^(1/2)

Out[2]= 48897705289941897278515656316900240171650055557292696823953325\
8635666453424544129253981802360653145003762959469853542541818050387424\
7236254299925216547878374916180483196313640403881912534846982553136987\
4247368758362200396104573045243051200451656653985909295009840745370213\
3326714061654556142686232796729554029073220559768956005931866053289115\
1695936264562194804751978316341066629080189896385088450648277821022198\
3317787938356586115384593121867887478906081852529924976333801078939072\
1301760772016869260727399301258323602

In[3]:= v = (RSA260^2 - 1)

Out[3]= 48897705289941897278515656316900240171650055557292696823953325\
8635666453424544129253981802360653145003762959469853542541818050387424\
7236254299925216547878374916180483196313640403881912534846982553136987\
4247368758362200396104573045243051200451656653985909295009840745370213\
3326714061654556142686232796729554029073220559768956005931866053289115\
1695936264562194804751978316341066629080189896385088450648277821022198\
3317787938356586115384593121867887478906081852529924976333801078939072\
1301760772016869260727399301258323600

In[3]:= mod = -2 (RSA260^2 - 1)^2 - (2 1 RSA260)^2

Out[3]= -4781971165244023609193253196791346935400271927259111778265969\
1985160770756814936885346660111368850670666493697670666586431453151744\
2711370250636120225780637554458557438697078268086967739189443193412804\
9302202120905589502342767886893547487200711718868476434457572769846107\
0779502776905976101427525915982884866302577443003583425421519721143731\
1581794064984719510629844926745913046485178575326488301648428704124794\
3077087313577288574842779067916119983682237916726558930943954396419758\
4938176174479898752099204847165614981647667561896461244066743182500661\
0726271597370219506195692307132921311229935371896691967627882162994221\
5254113226582281041880468938995205313881101168610438216301537080461862\
9021037268827123481880256026406850793159040334688592213201131483445273\
6638821994514114746077142302601864843165084705043074367971789265654275\
2125200928636991668349302806176203387917056163741814786488245113405979\
3092448626793345719672585727633127359247751769700773062998076924975661\
8909418568298155559461293692441859519326899815869330273769667214404

In[5]:= alpha = v w

Out[5]= 23909855826220118045966265983956734677001359636295558891329845\
9925803853784074684426733300556844253353332468488353332932157265758721\
3556851253180601128903187772292787193485391340434838695947215967064024\
6511010604527947511713839434467737436003558594342382172287863849230535\
3897513884529880507137629579914424331512887215017917127107598605718655\
7908970324923597553149224633729565232425892876632441508242143520623971\
5385436567886442874213895339580599918411189583632794654719771982098792\
4690880872399493760496024235828074908238337809482306220333715912503305\
3631357986851097530978461535664606556149676859483459838139410814971107\
6270566132911405209402344694976026569405505843052191081507685402309314\
5105186344135617409401280132034253965795201673442961066005657417226368\
3194109972570573730385711513009324215825423525215371839858946328271376\
0626004643184958341746514030881016939585280818709073932441225567029896\
5462243133966728598362928638165636796238758848503865314990384624878309\
454709284149077779730646846220929759663449907934665136884833607200

In[6]:= beta = 0

Out[6]= 0

In[7]:= Timing[
 xx = Factor[alpha^2 x^2 + (2 alpha beta - mod) x + (beta^2 - (-1))]]

Out[7]= {0.015001, (1 + 
    239098558262201180459662659839567346770013596362955588913298459925\
8038537840746844267333005568442533533324684883533329321572657587213556\
8512531806011289031877722927871934853913404348386959472159670640246511\
0106045279475117138394344677374360035585943423821722878638492305353897\
5138845298805071376295799144243315128872150179171271075986057186557908\
9703249235975531492246337295652324258928766324415082421435206239715385\
4365678864428742138953395805999184111895836327946547197719820987924690\
8808723994937604960242358280749072603837036834682747634027861653005597\
0279757396389916136708704918932270811859768983802020921977520710323678\
6721622028968457922672100313014834070015120946235831840757383830417024\
4099616286480128906527345493065906279576655208696051007963932173351863\
3127907115717622366374703427899345923324023616471839243552476899116514\
0508519837719685358562078470982142940369226140343661144042344482927482\
9661162765989427987241984992810374716271261961734525530268753001878176\
58685649551103709068064778326238119416169413210338282316960000 x) (1 \
+ 23909855826220118045966265983956734677001359636295558891329845992580\
3853784074684426733300556844253353332468488353332932157265758721355685\
1253180601128903187772292787193485391340434838695947215967064024651101\
0604527947511713839434467737436003558594342382172287863849230535389751\
3884529880507137629579914424331512887215017917127107598605718655790897\
0324923597553149224633729565232425892876632441508242143520623971538543\
6567886442874213895339580599918411189583632794654719771982098792469088\
0872399493760496024235828074909216291915281144165904029038841310166568\
7997962556070343252200837319885218167742068539474186623877871182886246\
0103619913573012422179920751655404010174009758579831295066235587318596\
2726642586805911907529519201340962445681365052526910518441235401452490\
7154429575698534785555675858497058514648069096495793537408852840473795\
8434386144714957171853914935664876524714804113498768046899611500344152\
0151656858253927133077831992555005890570811557177427742374456431091759\
882648604455752225627663533281207483646456119935487350254404 x)}

In[8]:= y25 = 
 Mod[alpha (-1 PowerMod[
       239098558262201180459662659839567346770013596362955588913298459\
9258038537840746844267333005568442533533324684883533329321572657587213\
5568512531806011289031877722927871934853913404348386959472159670640246\
5110106045279475117138394344677374360035585943423821722878638492305353\
8975138845298805071376295799144243315128872150179171271075986057186557\
9089703249235975531492246337295652324258928766324415082421435206239715\
3854365678864428742138953395805999184111895836327946547197719820987924\
6908808723994937604960242358280749092162919152811441659040290388413101\
6656879979625560703432522008373198852181677420685394741866238778711828\
8624601036199135730124221799207516554040101740097585798312950662355873\
1859627266425868059119075295192013409624456813650525269105184412354014\
5249071544295756985347855556758584970585146480690964957935374088528404\
7379584343861447149571718539149356648765247148041134987680468996115003\
4415201516568582539271330778319925550058905708115571774277423744564310\
91759882648604455752225627663533281207483646456119935487350254404, \
-1, (1 + RSA260^4)/2]) + beta, (1 + RSA260^4)/2]

Out[8]= 11954927913110059022983132991978367338500679818147779445664922\
9962901926892037342213366650278422126676666234244176666466078632879360\
6778425626590300564451593886146393596742695670217419347973607983532012\
3255505302263973755856919717233868718001779297171191086143931924615267\
6948756942264940253568814789957212165756443607508958563553799302859327\
8954485162461798776574612316864782616212946438316220754121071760311985\
7692718283943221437106947669790299959205594791816397327359885991049396\
2345440436199746880248012117914037453630191851841734137381701393082650\
2798513987869819495806835435245946613540592988449190101046098876035516\
1839336081101448422896133605015650741703500756047311791592037869191520\
8512204980814324006445326367274653295313978832760434802550398196608667\
5931656395355785881118318735171394967296166201180823591962177623844955\
8257025425991885984267928103923549107147018461307017183057202117224146\
3741483058138299471399362099249640518735813563098086726276513437650093\
908829342824775551854534032389163119059708084706605169141158480000

show square root of -1 found

In[9]:= Mod[-y25^2, (1 + RSA260^4)/2] 

Out[9]= 1

Endo999 (talk) 04:23, 29 November 2022 (UTC)[reply]

x^2+y*z==p o^2 is not x^2+y^2==p o^2[edit]

If you have x^2+y^2==p*o^2 then you can the square root of p quite easiiy if x^2 or y^2 is a square of the modulus. However, Kunerth's method is more broad than that. It can discover the modular square root of the equation x^2+y*z==p o^2, which is more general, where z is the modulus. Endo999 (talk) 16:17, 17 February 2023 (UTC)[reply]

Upon further investigation it appears tha Kunerth's method is a another type of minus of 2 squares method, which can be quickly found by other means. Since the quadratic equals $x^{2}+y*z==p*o^{2}$ this can be rewritten as $p*o^{2}-x^{2}\mod {z}\equiv 0$

After some thought on the matter, it seems the novel aspect of Kunerth, is that joined to the Pythagorean theorum in the Quadratic there is a modulus of a certain formula that allows the root of a certain residue to be taken easily.

For instance, if the quadratic is $(2(x^{2}-1))^{2}+((x^{2}-1))^{2}+5(2*1*x)^{2}==5(x^{2}+1)^{2}$ then the formula for the modulus is $X^{4}+18*x^{2}+1$ . Any modulus that fits this will reveal the root of 5 easily. It's really hard to do this with ordinary $5*x^{2}-y^{2}{\bmod {p*q}}\equiv 0$ .

A Way To Generate The Division Of Two Squares Mod a Modulus[edit]

Using a better method of setting the modulus to be a multiple of RSA260, I was able to find a square root that was not obviously a division of two easy numbers, like (2/5).

The changing parameters are

(RSA260-n)^2+o^2

Setting n=1 returned only naiive divisions of squares like (4/16). Setting n=2 returned squares of (4/25). Setting n=3 returned a root that was (2/5+10).

I'd say that by changing the N and O variables in the equation given above that you can automatically generate the minus of two squares equaling the multiple of a modulus you are interested in, particularly a RSA number.

This leads to a modular square that is the division of two natural squares, and thus the root can be found easily.

Using the Pythagorean theorum come up with a quadratic number
and determine a SQUARE that will ensure a modulus that RSA260*x

In this case use (RSA260-4), and 3^2 and the inputs to the pythagorean
triple.

As such (RSA260-4)^2+3^2 is the resulting square.  32 makes the square
(4(RSA260-4)^2+3^2)*2


In[29]:= y1 = 
 Solve[( square - 1) ((RSA260 - 4)^2 - 3^2)^2 +     
    square (2 3 (RSA260 - 4))^2 +    
    31 square ((RSA260 - 4)^2 + 3^2)^2 == 0, {square}, 
  Modulus -> RSA260] 

Out[29]= {{square -> 
   1310074348496985087958227895934029051306378242573836062042042519166\
7871151633616076909466726506246372628441650527102960316106219092081078\
2782697034448186243471410872828623439969212125671314423500663717755571\
28362798348048332822650444386978185719854262751334260}}

make the square (or half the square)
this is a square*2 that will make the modulus
be a multiple of RSA260.

In[30]:= sq = square /. y1

Out[30]= {\
1310074348496985087958227895934029051306378242573836062042042519166787\
1151633616076909466726506246372628441650527102960316106219092081078278\
2697034448186243471410872828623439969212125671314423500663717755571283\
62798348048332822650444386978185719854262751334260}


make the modulus and ensure it is a multiple of RSA260

In[31]:= mod = ( sq - 1) ((RSA260 - 4)^2 - 3^2)^2 +     
  sq (2 3 (RSA260 - 4))^2 +    31 sq ((RSA260 - 4)^2 + 3^2)^2 

Out[31]= {\
1002358041414149256141274976883084858155451228382361129174692948058420\
3599822966056879419332122392602397619194035843768768709541019270410555\
6433865054516535536095433805068898049589154927235644010444905709641657\
5664206624064244511391622161730259643289116736731448910028590146704947\
3161788407261817986244137659489378985393013818434265570008614736512776\
3545618430509765369662358402759029772411007313696489988416538699895793\
2062486200292789019019944056514768367832365326072002803950843223356312\
4166954570325030969756112101858031090970125818758607383491205471097319\
2814060103436411355386558984309895156603054428229565301682429394578997\
6942467702973118538396177479356022104478800105886098857119937058438326\
5882291105445591594288115650278960467162451625164324314977683968541369\
2081124697290064794747604396221843134077697331584288261403440452001303\
0621478551564289565584772940068021559707725584052454208322434397897947\
8871328222771961549263669750618180963391086959070362771744490889921681\
5532811395394495346475476550388193475366787875136485329364485382293503\
2066672551241188787138210654359505034219224134083222406474511360502171\
8752529498150360411729367426811841015002456997874675195860846076561970\
3321287953956776844475358091709648072725163365318816992866389964393118\
360635870348680478314650421801249969664}


modulus is multiple of RSA260

In[32]:= Mod[mod, RSA260]

Out[32]= {0}


make the W variable in Kunerth's method

In[33]:= w1 = (((((1 (PowerMod[1, 1, 
               RSA260] ((RSA260 - 4)^2 - 3^2)))^2 + (sq - 
            1) ((RSA260 - 4)^2 - 3^2)^2 +       
         sq (2 3 (RSA260 - 4))^2) + (31)   sq ((RSA260 - 4)^2 + 
           3^2)^2)/(( 2  sq))))^(1/2) 

Out[33]= {\
1955908211597675891140626252676009606866002222291707872958133034542665\
8136981765170159272094426125800150518378794141701672722015496988945017\
1997008661915134996647219327852545616155276501393879302125479496989475\
0334488015844182921809722048018066266159436371799686019397863583980927\
2518900637313552476000541370758002609991296119013933393490928922710232\
5559298675115198076553162501416832541260653853680479089845834176986483\
8838927812903169227782727641691137148863931697158492481780996676539958\
573959447769493551280410632136}


make the V variable in Kunerth's method

In[8]:= v1 = 1 (PowerMod[1, 1, RSA260] ((RSA260 - 4)^2 - 3^2))

Out[8]= 48897705289941897278515656316900240171650055557292696823953325\
8635666453424544129253981802360653145003762959469853542541818050387424\
7236254299925216547878374916180483196313640403881912534846982553136987\
4247368758362200396104573045243051200451656653985909294992150484946589\
5995231812972515932838811900013534268950065249782402975348334837273223\
0677558138982466877879951913829062535420813531516346342011977246145854\
4246620970973195322579230694568191042278428721598292428962312044524916\
9134989643489861942373387820102658016


make the alpha variable in Kunerth's method

In[34]:= alpha1 = w1 v1

Out[34]= {\
9563942330488047218386506393582693870800543854518223556531938397032154\
1513629873770693320222737701341332987395341333172862906303488542274050\
1272240451561275108917114877394156536173935478378886386825609860440424\
1811179004685535773787094974401423437736952868908225434566640747860098\
3877982231006470294327231117537963340934886813968052527174610604544112\
6446792134946419268141842319276017601204137720022890992661139113325319\
9391187378239462665467103121813253475519495308197690941869365894281561\
6546655629994820101244915485320888366429132996054452031763750688999910\
0373429755223816490881797241928409251675605491355049233197310323467611\
4507049622544668047364440656457744805636700155250482094869502994691294\
5655709430147160222472286490593100993873738142913137560438652412311116\
9071561761293061288370201477187340962214738792899421099831906504908793\
4049878071431293908772739046972354503073523173903098439865856028936635\
2054596141074097522698141038711562563733125043318767121833784330024745\
9723593764289212411359121432052711136049324198680387602176}


make the beta variable in Kunerth's method

In[35]:= beta1 = 0

Out[35]= 0


Factor according to the Kunerth equation

In[36]:= Timing[
 xx = Factor[
   alpha1^2 x^2 + (2 alpha1 beta1 - mod) x + (beta1^2 - (( sq 2)))]]

Out[36]= {0.047995, {24 \
(-10917286237474875732985232466116908760886485354781967183683687659723\
2259596946800640912222720885386438570347087725858002634218492434008985\
6522475287068218695595090606905195333076767713927620195838864314629760\
696899862337361068554203698914848809987855229277855 + 
     99624399275917158524859441599819727820838998484564828713874358302\
4182724100311185111388752320184388972218618701472220550655273994672315\
3546888252504703763282384553279972855797251811827899780066529433436046\
2544185533114632140997643615572650014827476426592384460681610069174456\
8760248728981572984065565908657474353784801405070978833880491402193797\
3345067154084739025200709810857492458516679209767916905114506886865763\
8054160324868523327736098615657518888057036661409460392613977805894732\
0996005694329479112709387967869602085974849513712416680466426530556215\
0115212210198057401771836041971430019188274680404183177939653719160316\
5185624546036599462386474619066113157595981140178763390492757655425891\
7895506568954194884391578400791041573151722439675871412894520897220137\
7513691449660551498955665193174860972081406774420167692152421536477155\
4631290704450732796429043374529801725175915272569126118811847037056819\
4526903003619973509088619920670091682213546952296180311014237393098563\
2257178903551037678692408139606017931677877067086204510377344 x) (1 + 
     38255769321952188873546025574330775483202175418072894226127753588\
1286166054519495082773280890950805365331949581365332691451625213954169\
0962005088961806245100435668459509576626144695741913515545547302439441\
7616967244716018742143095148379897605693750947811475632901738266562991\
4403935511928924025881177308924470151853363739547255872210108698442418\
1764505787168539785677072567369277104070404816550880091563970644556453\
3012797564749512957850661868412487253013902077981232790763767477463577\
1262466186622519979280404979661955366092589219798400430317146322271925\
4348561498721987748251542014260906299905715927568724500065038550325026\
1977636230718926163787972661803864209441588335772596861907540016340415\
0831690723197030341675413672388164780717689573069608682548987484686765\
5924095055824438568891331527432670885448437516532998801582268785244811\
5725056768515490056522517526092931916368473123518846795163769664618412\
8232485683379058765290151535590994486530507835318613310707507511324791\
9192921089786515845081406147362745535924783600832486911115922496 x)}}


construct the root

In[37]:= y26 = 
 Mod[alpha1 (-1 PowerMod[
       382557693219521888735460255743307754832021754180728942261277535\
8812861660545194950827732808909508053653319495813653326914516252139541\
6909620050889618062451004356684595095766261446957419135155455473024394\
4176169672447160187421430951483798976056937509478114756329017382665629\
9144039355119289240258811773089244701518533637395472558722101086984424\
1817645057871685397856770725673692771040704048165508800915639706445564\
5330127975647495129578506618684124872530139020779812327907637674774635\
7712624661866225199792804049796619553660925892197984004303171463222719\
2543485614987219877482515420142609062999057159275687245000650385503250\
2619776362307189261637879726618038642094415883357725968619075400163404\
1508316907231970303416754136723881647807176895730696086825489874846867\
6559240950558244385688913315274326708854484375165329988015822687852448\
1157250567685154900565225175260929319163684731235188467951637696646184\
1282324856833790587652901515355909944865305078353186133107075075113247\
919192921089786515845081406147362745535924783600832486911115922496 , \
-1, RSA260]) + beta1, RSA260]

Out[37]= {\
2056492774246258978481140928717439476267924323729711431680478593678980\
5335503861847456838645709864337149887306929202047588790250241599127012\
8969941829374979202315995831917966362338217358971075796467647080228363\
19356002506455439387143691264600758653834684346125}


y26 is root of 2 sq

In[38]:= Mod[y26^2, RSA260] == Mod[2 sq , RSA260]

Out[38]= True


the root is not one of the low inverses

Table[{x, Mod[1 PowerMod[ y26[[1]], -2, RSA260], RSA260] == x}, {x, 1,
    100}] // Grid

Endo999 (talk) 00:51, 11 May 2023 (UTC)[reply]

The root is 7/100 mod RSA260. The square always seems to be the division of two squares which in this case is 49/10000 Endo999 (talk) 10:16, 11 May 2023 (UTC)[reply]

If you could come up with a combination of

((RSA260^2-n)^2-o^2)^2, (2 o (RSA260-n))^2 and ((RSA260^2-n)^2+o^2)^2 where the division of the square was a low number mod RSA260 then you should be able to produce the root of a low square Endo999 (talk) 22:57, 11 May 2023 (UTC)[reply]

[1] url=https://www.amazon.com./Unlimited-Congruent-Squares-Kunerth-Algorithm-ebook/dp/B0D1KDGJ3M/ref=sr_1_4?dib=eyJ2IjoiMSJ9.vnAuzEUQeyJUFIgaUkfmv0zAY35k8z5Xx3sm9TnxXMTx54p7uId0BnwWX7Qy8YQ5i6o5QfbZVxmMvL-uoV3YMADJFNcGeKMwrbdX6HjG1P5zzwY9oTE63yF4DuCh9XaPp7FF5bXvnofwZSXB5MAacVIzL83PmcpVfV5B_f9NXPX86wXOHVo53JFxJgaUlkBvQ2uWpgewBfXPSE5ud09rdsFtBFkXpK7CtFaulWzZMKE.M4uyUgrzxxgep1jLdeebnSoW2nKtaHBP3TfUr0aMSI4&dib_tag=se&keywords=paul+cheffers&qid=1713497200&sr=8-4, title="Unlimited Congruent Squares Using the Kunerth Modular Square Root Algorithm"

[2] url=https://mathshistory.st-andrews.ac.uk/Biographies/Petzval/

[3] url=https://www.zobodat.at/pdf/SBAWW_78_0244-0248.pdf, p245

[1]

[2]

[3]