View text source at Wikipedia
Wikipedia:Babel | ||||
---|---|---|---|---|
| ||||
Search user languages |
I have created some javascript in my GoogleTrans.js file that will marry the Google translation javascript api with Wikipedia. Help for this gadget is at User:Endo999/GoogleTrans.
You can install GoogleTrans by going to my preferences when you are logged into Wikipedia. clicking on the Gadgets tab in your profile, and then selecting the GoogleTrans gadget.
Then, you may need to restart your browser (clear the cache) to get it working. (Shift+F5 also work for Firefox, and CTRL+F5 works for Internet Explorer).
From then on the following will happen
1) Like the Google toolbar: whenever you place the cursor over a word (for say 2 seconds), a popup will happen with the foreign language translation of the word. When you move the cursor away from the word, the popup window will disappear.
Note: a new feature recently introduced means that you have to hold the shift key down after you have hovered over a word (or selected text). This feature can be turned off by clicking on the Translation Popups tab at the top of the page and clicking on the link that turns this feature off.
2) Over 50 languages: As many languages as Google does. The Change Translation Languages popup window has a To language. Click on the ->French (ie) at the top of the Popup window to change the language being translated to.
3) Work with: IE, Firefox, Epiphany, Safari, Opera, and Chrome. This feature is turned off for Konqueror at the moment because 2005 Konquerer does not run the javascript well. Perhaps later versions of Konqueror do, but I have not tested on them.
4) And: when a cursor is placed within selected text, then all the selected text is translated (this for IE, Firefox, Chrome, and Epiphany). Safari and Opera don't support this option.
5) Within the popup are some links
6) To stay up: move the cursor into the popup, or outside the frame of the document (like onto the nondocument part of the browser) the popup window will stay up.
7) There is a 'GoogleTrans (on/off)' tab. (on/off) tells whether the translation popups feature is on or off. Click on the tab to get the Change Translation Languages popup window, which will allow you to toggle the feature on or off.
The page goes beyond the Google translation feature of their toolbar in that over 50 languages are supported (translations between them and not just from English), and translation of selected text paragraphs (up to 500 characters) happens for IE, Firefox, Chrome, and Epiphany.
The translation software at Google is very powerful and I thought I would marry the premier language site on the web with it. The Javascript for determining the word under the cursor in a web page and/or the selected text under the cursor is mine.
Endo999 (talk) 02:59, 11 October 2008 (UTC)
Translation of small amounts of selected text is possible. Select less than 500 characters of text, put the cursor within the selected text (preferably right on a word within the selected text), and hit the SHIFT key. At this point you will see a popup (like the picture shown) with the translated text. If you wish to have the next sentence translated, simply click on the "Translate Next Sentence?" link at the bottom left of the popup.
The following material is Endo999's math blog.
For fun, consider the following:
Everybody knows the following is true:
However, the following analogue for is also true:
So:
and
Viola! Make sure to remember the in the denominator.
With the equation in the section above, we can take a cube and draft the equation as:
or
or
Thus,
This is a redrafting of any cube or power of cubes.
You can also redraft the cube as:
As , in our RSA cipher, then , therefore,
If has a cube power then the equation holds.
You can solve for by solving the cubic modular equation:
where
Or
How about the 2 modular square roots of a modular power. For instance,
is the modular square root for . So is because .
As the power cycle is for the modulus , then since . As such and
So
and
Also,
Also,
Also,
and
Also,
and
Also,
Also, while the above equations usually show the sum of powers mod p*q, the terms, individually, usually show powers of p and q mod p or q. Thus,
Most of the above equations of sums of powers can be split up in the manner shown just above.
Also, This seems obvious since and ,however, many times
Also,
as the base or generator for modular powers is also fun to do
will equal a complex number with the real or imaginary numbers sometimes being or
It seems to vary with the semi-prime looked at.
as a generator is really wild and you should definitely check it out. In general the real and imaginary terms will equal the square roots of what the powers would produce if the generator was .
1)
2)
As the power cycle is for the modulus , then since . As such and
So
and
3)
You can take a modular square root of any odd composite modulus in square root of the modulus steps via:
Multiply the root by squares (i*i) until the resulting number mod the modulus is an actual square. At this point you can take the real square root, and modular divide by i (the root of the square you multiplied the left side with). This will give the modular square root.
I have a way, which is similar but more complex, which introduces and coefficients into the equation. By manipulating the coefficients you can get a small number of the right (after moding). This small number can be worked with something like the quadratic sieve to find a square root in less that steps.
Interestingly the sum of all the squares in a modulus is . Thus:
This means that:
This means that any quadratic number (a square in mod p*q) is equal to the minus of all the sums of squares of all the other numbers
The well known sum of squares formula shows the sum of squares for the first squares.
The sum of all numbers in a modulus field is also 0. Since every number in a semiprime modulus field is countered by on the other side of the field then this has to be.
Even though we don't know what is, when we are given , we do know that
You can take the sum of consecutive powers from 1 to N quite easily according to Faulhaber's formula. The mathematica for doing this follows:
Faulhaber[m_, p_, n_] := Module[{a1, a2}, a1 = 0; For[a2 = 0, a2 <= p, a2++, a1 += (-1)^a2 (Binomial[p + 1, a2]) BernoulliB[a2] (m^(p + 1 - a2)); ]; a1 /= (p + 1); Print[Mod[a1, n]]; ];
Since
then every modular square is equivalent to:
and every power root is defined as:
Now viewers may say that is a hard term to come up with, however, terms like this are possible. Note:
So terms like the one needed are almost instantly possible to generate from moduli of .
The general equation is a polynomial where:
The general equation is (Neal Koblitz reports this as well in [1]):
As well:
If you take one modular square root, let's say , you can get the other square root (in this case , by:
You can get the modular square root of 1 by
You can get a quad root of 1 by
So, using this ChineseRemainder method you usually get the other root, but in the two cases just shown above you get the square root of the inputs.(Mathematica code is above). The last equation tends to indicate that there are no quad roots of 1 for 3 mod 4 semiprimes.
Quoting from Wilson's theorem:
where p is an odd prime, and is a positive integer.
This means that the multiplication of all numbers up to (n-1)/2, where n=p*q, that are not factors of n will equal the square root of 1 mod p*q:
As in the following mathematica statement:
Mod[1 2 3 4 6 8 9 11 12 13 16 17, 35]=6
where 6*6 mod 35 === 1.
This works since, GAUSS has proven (see above) that
Mod[1*2*3*4*6*8*9*11*12*13*16*17*18*19*22*23*24*26*27*29*31*32*33*34, 35]==1
and thus that
Mod[1*2*3*4*6*8*9*11*12*13*16*17*-1*-2*-3*-4*-6*-8*-9*-11*-12*-13*-16*-17, 35]=== Mod[1*2*3*4*6*8*9*11*12*13*16*17*18*19*22*23*24*26*27*29*31*32*33*34, 35]==1
As such
Mod[1*2*3*4*6*8*9*11*12*13*16*17,35]===Mod[-1*-2*-3*-4*-6*-8*-9*-11*-12*-13*-16*-17, 35]
and since
Mod[1*2*3*4*6*8*9*11*12*13*16*17,35]*Mod[-1*-2*-3*-4*-6*-8*-9*-11*-12*-13*-16*-17, 35]==1
then
Mod[1*2*3*4*6*8*9*11*12*13*16*17,35]===1^(1/2) mod 35
Working from Gauss' definition above, we can see that in the case of a prime modulus that, for instance:
Mod[1*2*3*4, 5]==-1==4
Thus since
Mod[1*2*-2*-1, 5]==Mod[1*2*3*4, 5]==-1==4
the same proof outlined just above can be applied to prime moduluses for . Namely, that:
Mod[1*2, 5]==2 where 2*2==4==-1 mod 5
As such (this is partially revealed in an earlier section):
ChineseRemainder[{Mod[1*2,5],Mod[1*2*3*4*5*6, 13]},{5,13}]==57 mod 5*13 where 57*57 mod 5*13 == -1
This can be rewritten, given the ChineseRemainder statement above, as the following Mathematica statement:
Mod[1 2 + (1 2) (3 4 5 6 - 1) 5 PowerMod[5 - 13, -1, 5 13], 5 13]=57 where 57*57 mod 5*13==-1
I've only tested this out for 1 mod 4 semiprimes.
Since the following two equations are the equations for the two square roots of -1:
ChineseRemainder[{Mod[1*2,5],Mod[1*2*3*4*5*6, 13]},{5,13}]
ChineseRemainder[{Mod[1*2,5],Mod[-1*2*3*4*5*6, 13]},{5,13}]
since the then the following applies:
ChineseRemainder[{Mod[1*2,5],Mod[1*2*3*4*5*6, 13]},{5,13}]*ChineseRemainder[{Mod[1*2,5],Mod[-1*2*3*4*5*6, 13]},{5,13}]=14
this can be converted into the following equation below by observing that the muliply sign outside the ChineseRemainder symbols can be applied within them as such:
Mod[ChineseRemainder[{(1 2)^2,-( 1 2 3 4 5 6)^2},{5, 13}] , 5 13]=14 where 14*14 mod 65 === 1
and also where
Mod[ChineseRemainder[{(1 2)^2, ( 1 2 3 4 5 6)^2},{5, 13}] , 5 13]=64 where 64 mod 65 === -1
The definition of the square root of 1 mod p*q shown in the first equation in this section can be rewritten, with knowledge of the Chinese Remainder theorum, to be:
Mod[(1 2)^2 + (1 2)^2 (-(3 4 5 6)^2 - 1) 5 PowerMod[5 - 13, -1, 5 13], 5 13]=14 where 14*14 mod 65 == 1
this semiprime works as well:
Mod[(1 2 3 4 5 6)^2 + (1 2 3 4 5 6)^2 (-(7 8)^2 - 1) 13 PowerMod[13 - 17, -1, 17 13], 17 13]=103 where 103*103 mod 17*13 = 1
If you take it has some unusual properties, the main one being that it is its own square and square root. For instance,
Mod[89 PowerMod[60, -1, 89 29], 89 29]=1335 where 1335*1355 mod 89*29===1335
Also,
Mod[29 PowerMod[-60, -1, 89 29], 89 29]=1247
which is one off 1247.
This number has unusual properties.
By and large, any number that is and will be its own square or square root.
The difference between 1335 and 1247 is 88 which is . Thus:
and
Moreover,
Because both self-square numbers described here for 89*29 (1247 and 1335) are either 0 mod p and 1 mod q or 1 mod p and 0 mod q, then the Product To Sum Theorum, described elsewhere in the blog, applies. Thus:
where . This is another way to unwind the multiplication!
Because then:
and by switching the sign of one of the numbers the other square root is found. Thus:
The Squareless number has the Idempotent (ring theory) property for a P*Q modulus.
Quoting from the wiki article Idempotent (ring theory):
There are two nontrivial idempotent elements given by e = (1 − j)/2 and e∗ = (1 + j)/2. Recall that idempotent means that ee = e and e∗e∗ = e∗. Both of these elements are null:
Zero divisor has the following quote:
An idempotent element e!= 1 of a ring is always a two-sided zero divisor, since e(1-e)=0=(1-e)e} e(1-e)=0=(1-e)e
There are two idempotent numbers in a P*Q modulus, and the multiplication of both mod p*q is equivalent to 0. These are the Zero Divisors that James Cockles spoke about in his Tessarines.
As well, according to Split-quaternion,
Unlike the quaternion algebra, the split-quaternions contain nontrivial zero divisors, nilpotent elements, and idempotents. (For example, 1/2(1 + j) is an idempotent zero-divisor, and i − j is nilpotent.)
However, in modular arithmetic, there are no nilpotent numbers, according to the passage above:
So nilpotentacy is not a thing in modular arithmetic for tessarines. As a result, there can't be any Unipotent numbers in the P*Q field either.
These items apply to the two SQUARELESS numbers of P*Q modula. in the above equations equals
According to [3] you can construct the squareless number via:
or
Moreover, these is a type of definition of any square with regard to the squareless number. If are the two squareless numbers of then:
Thus, since the difference between the two squareless numbers is then
This is a type of algebra. An example:
Working with the residue as a modular complex number and working with the inverse definition of a complex number, one can derive the following equate for all p*q modulus:
and
Dropping into Mathematica to come up with examples:
Mod[PowerMod[1335 + 1, -1, 89 29]+ PowerMod[1247 + 1, -1, 89 29], 89 29] = 1292 Mod[3 PowerMod[2, -1, 89 29], 89 29]= 1292 Mod[1335^2, 89 29]= 1335 Mod[1247^2, 89 29]= 1247 here's an example of the minus of the two items. Mod[2493(PowerMod[1335 + 1, -1, 89 29]- PowerMod[1247 + 1, -1, 89 29]), 89 29]=1291 PowerMod[2,-1, 89 29]=1291 lets try another number Mod[PowerMod[(6060 + 1), -1, 101 73] + PowerMod[(1314 + 1), -1, 101 73], 101 73]= 3688 Mod[3 PowerMod[2, -1, 101 73], 101 73]= 3688 Mod[6060^2, 101 73]= 6060 Mod[1314^2, 101 73]= 1314 lets try a 3 mod 4 semiprime Mod[PowerMod[1027 + 1, -1, 79 19] + PowerMod[475 + 1, -1, 79 19], 79 19]=752 Mod[3 PowerMod[2, -1, 79 19], 79 19]=752 Mod[1027^2, 79 19]=1027 Mod[475^2, 79 19]=475
Determining that
An example:
PowerMod[1335 + 1, -1, 89 29]=624 Mod[PowerMod[1335 + 1, -1, 89 29]+ PowerMod[1247 + 1, -1, 89 29], 89 29] = 1292 Mod[-(PowerMod[1335 + 1, -1, 89 29] - PowerMod[1247 + 1, -1, 89 29]), 89 29]=44= (-\sqrt{1}/2) Mod[(1292 -44) PowerMod[2, -1, 89 29], 89 29]=624 Mod[((3 + 2493) PowerMod[4, -1, 89 29]), 89 29]=624
By symmetry
Mod[((3 - 2493) PowerMod[4, -1, 89 29]), 89 29]=668 PowerMod[1247 + 1, -1, 89 29]=668
These numbers bear some similarity to Eisenstein integer.
Similarly,
Dropping into Mathematica to come up with examples:
Mod[PowerMod[1335 + 2, -1, 89 29]+ PowerMod[1247 + 2, -1, 89 29], 89 29] = (1292+1)/3 = 431 Mod[3 PowerMod[2, -1, 89 29], 89 29]= 1292 here's the example for the minus of the two squares: 2493 is square root of 1 mod 89*29 Mod[2493(PowerMod[1335 + 2, -1, 89 29]- PowerMod[1247 + 2, -1, 89 29]), 89 29]=2151 Mod[ 5 431-4, 89 29]=2151 lets try another number Mod[PowerMod[(6060 + 2), -1, 101 73] + PowerMod[(1314 + 2), -1, 101 73], 101 73]= (3688+1)/3 = 6145 Mod[3 PowerMod[2, -1, 101 73], 101 73]= 3688 lets try a 3 mod 4 semiprime Mod[PowerMod[1027 + 2, -1, 79 19] + PowerMod[475 + 2, -1, 79 19], 79 19]= (752+1)/3 = 251 Mod[3 PowerMod[2, -1, 79 19], 79 19]=752
Working with the definition of the Idempotent number in terms of P and Q given above we can make the following statements:
Finally,
This above equation establishes a new relationship between a residue mod p*q and its inverse!
My math blog has previously defined numbers in terms of powers of p and q. This is the first time I have defined ordinary
residues in terms of p and q (not powers of p and q).
Some examples follow:
Mod[(89 - 29) (PowerMod[ (1)89 - 29, -1, 89 29] - PowerMod[ (1)29 - 89, -1, 89 29]), 89 29]= 2 now take the inverse of 1 PowerMod[1, -1, 89 29]= 1 now take 7 as the multiplier PowerMod[7, -1, 89 29]=1475 Mod[(89-29) (PowerMod[7 89 - 29, -1, 89 29] - PowerMod[7 29 - 89, -1, 89 29]), 89 29]=1476 this converts to Mod[((-6 89) PowerMod[7 89 - 29, -1, 89 29] - (6 29) PowerMod[ 7 29 - 89, -1, 89 29]), 89 29]=1474 or Mod[((6 89) PowerMod[7 89 - 29, -1, 89 29] + (6 29) PowerMod[ 7 29 - 89, -1, 89 29]), 89 29]= -1474 Finally, Mod[(( 89) PowerMod[7 89 - 29, -1, 89 29] + ( 29) PowerMod[ 7 29 - 89, -1, 89 29]), 89 29]=1475 now take 5 as the multiplier PowerMod[5, -1, 89 29]=2065 Mod[(89-29) (PowerMod[5 89 - 29, -1, 89 29] - PowerMod[5 29 - 89, -1, 89 29]), 89 29]=2066 Mod[(( 89) PowerMod[5 89 - 29, -1, 89 29] + ( 29) PowerMod[5 29 - 89, -1, 89 29]), 89 29]=2065 lets try a 3 mod 4 semiprime Mod[60 (PowerMod[7 79 - 19, -1, 79 19] - PowerMod[7 19 - 79, -1, 79 19]), 79 19]=430 Mod[ (79 PowerMod[7 79 - 19, -1, 79 19] + 19 PowerMod[7 19 - 79, -1, 79 19]), 79 19]=429 PowerMod[7, -1, 19 79]=429
Minusing the sign introduces the square root of 1 into the equation, as per some of my other examples:
Mod[89 PowerMod[3 89 - 29, -1, 89 29] - 29 PowerMod[3 29 - 89, -1, 89 29], 89 29]= 1750 Mod[88 PowerMod[3, -1, 89 29], 89 29]= 1750 Mod[88 PowerMod[79, -1, 89 29], 89 29]= 1700 Mod[89 PowerMod[79 89 - 29, -1, 89 29] - 29 PowerMod[79 29 - 89, -1, 89 29], 89 29]= 1700
Finally, since there is a close relationship between the idempotent numbers and the square root of 1 mod p*q, we have the following equation
2493 is the square root of 1 for the 89*29 modulus Mod[PowerMod[-2493 + 3, -1, 89 29] + PowerMod[2493 + 3, -1, 89 29], 89 29]= 646 Mod[3 PowerMod[4, -1, 89 29], 89 29]= 646
The relationship between the Squareless number and the two Square Roots of -1 mod p*q are shown in the following equations:
where 568 and 945 are the two square roots of -1 mod 89*29 and 1247 and 1335 are the two squareless numbers of 89*29.
Thus:
where is one of the squareless numbers.
Also,
Thus this is the definition of the quad root of 1. The other quad root is:
Thus the idempotent numbers of the p*q modulus provide the coefficients for the modular complex definition of the quad roots of 1 (this is only for 1 mod 4 semiprimes now). You can swap the idempotent numbers and change the square root of -1 to get the other quad roots.
Since, and are squareless numbers mod , and then
Thus since and , and since then
or
Thus, probably all of the sums of are derivable from the squareless numbers. This is a conjecture but if each only has one , then the conjecture is probably proved.
Thus the squareless numbers seem to be the anchors of the ring of numbers that are of the form: .
As well as and then the equation for and is now known:
In another section of this blog there is the claim that
With knowledge of the self-square numbers for of and then the above equation can be turned into:
or
Another equation that can be made from this melange is:
where
or we can change the base of the powers to and
In other words:
For instance,
Mod[ 1335 4^30 , 89 29]=712
and
Mod[(4 1335)^30, 89 29]=712
Mod[(2 2493 - 2)^30, 89 29]=712 where 2493 is square root of 1 mod 89*29
For instance:
Mod[4^(88 + 28), 89 29]==981==Mod[1335 4^(88) + 1247 4^(28), 89 29]
and
Mod[ (2 2493 - 2)^(88) + (2 2493 + 2)^(28), 89 29]==981
For instance, with an rsa key of 23 then the base can be changed in the following equation:
Mod[(2 37)^(23 (89 29-1)), 89 29]==915==Mod[1335 (2 37)^(23 88) + 1247 (2 37)^(23 28), 89 29]
This equals
Mod[(37 2493 - 37)^(23 88) + (37 2493 + 37)^(23 28), 89 29]==915
If and are odd primes and
and
then the product of these
The sum or subtraction of the powers will be one off the product of the powers. This type of equivalence happens for
Basically, any combination of the and powers above will yield a similarity between the product of these powers and the sum of the powers. The signs of the sums will change according to whether the congruence is or .
Normally, the is:
so it partakes of this relationship (theorum) as well.
Sometimes the quad root of 1 ( and ) and also the square root of -1 () also partake of this theorum as well.
Thus,
or
as
so both signs will be pluses.
Since
so
as the sign of the terms is switched among the terms due to polynomial expansion since:
and
Now
The other three terms of the multiplication are:
This resulting residual is equal to
This theorum is a type of analogue, among modular powers, to the Parallelogram law, which works on squares.
If we take and then
Please note that and for this example :
If we divide the cipher, , which we know, away from then:
This is perfect for the Product To Sum theorum shown in the just previous section. As such
So either or can be derived from a public encryption key of 3.
With the example given, note that and as well, although
All modular cube roots could be expressed again as the sum of powers of 2(p-1) and 2(q-1). Thus the cube root, or the base, can be expressed as more than one power, not just one.
Using , modulus of ,(which is known) and noting that then, after some steps of algebra I am not showing:
Thus, it looks like the general equation where any nth root, given can be rewritten in terms of the powers of p and q is:
This accords with the section directly below this post which says that all modular powers are the sum or subtraction of 3 other modular powers!
By the Product To Sum theorum given above, it follows that one is:
It thus follows that all bases of powers, ie.,, can be defined as:
and that all powers of can be defined as:
Since is an RSA operation, this has implications for RSA.
As in the preceding section:
or
it follows that any power can be expressed via . Thus,
or
As such, since and then:
This result seems to be like, for modular numbers, Legendre's_three-square_theorem.
Iterate all the possibilities of and through the equivalency:
The mathematica code for this follows:
SetPairTest[p_, q_, x_] :=
Module[{a1, a2, EnumerateSet},
EnumerateSet = { };
Print[{"p=", p, " q=", q, " x=", x}];
Print[{"The correct answer is: p-1=", Mod[p - 1, x - 1], " q-1=",
Mod[q - 1, x - 1]}];
For[a1 = 0, a1 < x - 1, a1 += 2,
For[a2 = 0, a2 < x - 1, a2 += 2,
If[FreeQ[EnumerateSet, {a1, a2}] &&
FreeQ[EnumerateSet, {a2, a1}] &&
Mod[a1 a2 + a1 + a2, x - 1] == Mod[p q - 1, x - 1],
EnumerateSet = Append[EnumerateSet, {a1, a2}];
];
];
];
Print[EnumerateSet];
]
Some code executions follow:
SetPairTest69[NextPrime[5003, 2], NextPrime[809, 3], 11]
{p=,5011, q=,823, x=,11}
{The correct answer is: p-1=,0, q-1=,2}
Candidates are:{{0,2},{6,8}}
SetPairTest69[NextPrime[5003, 2], NextPrime[809, 3], 37]
{p=,5011, q=,823, x=,37}
{The correct answer is: p-1=,6, q-1=,30}
Candidates are: {{0,0},{4,28},{6,30},{10,22},{12,24},{16,16},{18,18},{34,34}}
SetPairTest69[NextPrime[5003, 8], NextPrime[809, 8], 37]
{p=,5077, q=,857, x=,37}
{The correct answer is: p-1=,0, q-1=,28}
Candidates are: {{0,28},{4,12},{6,34},{10,18},{16,24},{22,30}}
In this case of six answers to x=37, as in this P*Q pair, p-1+q-1 mod 12 = 4 and p-q mod 36 = 8 or q-p mod 36 = 28
Some Notes: Approximately, half the square root of all the possibilities for the pairs of and are shown of where and are not known. Among this list of candidates for and , of these number of possibilities will be the candidates for .
Thus for there will be:
My question is: in the case of the 6 possibilities for the is definite knowledge of and known since is known and either or is known.
As it turns out, can be derived from via:
So while this algorithm knows this is not new knowledge. That means that the claim that either or remains possible new knowledge.
By decomposing , using the Chinese Remainder Theorum, into and it can be shown that or is derivable from examination of . As such, it appears any new knowledge from the algorithm above would be in the form of or . Since is known therefore the new knowledge would either be , or . If there is a way to derive and/or then the algorithm I show above would not have new knowledge in the case of . But if this sum were not derivable from examination of , then this algorithm would show new knowledge.
By solving the following problem in Mathematica:
Solve[a b == 2, {a, b}, Modulus -> 9]
you get the following answers:
{{a -> 1, b -> 2}, {a -> 2, b -> 1}, {a -> 4, b -> 5}, {a -> 5,
b -> 4}, {a -> 7, b -> 8}, {a -> 8, b -> 7}}
As can be seen all the and resolve to or . This is what we get from or , so, amazingly, there is NO new knowledge in the case of that is not derivable from .
There is still the reduced set of 's and 's.
A Third Modulus Transforms the Hard P*Q division problem into a B*E modular residue problem[4] that is solvable when
Considering that all RSA semiprimes are you can pick a modulus between and (try the number closest to ). The resulting new modulus, , is . Given this new modulus, the following equation holds:
and
When P and Q are close together, , then is a product, not a residue. As such it can be factored and two of the divisors of this factorisation will either be and the other . With known and known, it is easily possible to discover .
Example:
When is a square (the product which the residue represents is a square, the residue doesn't need to be a square), and are often discoverable as well.
Example:
Pretty simple isn't it. So the mighty P*Q (of large prime numbers) does have some holes in it. Some P*Q combinations (no matter how big) are easily factorable. So start out with a modulus near the square root of P*Q, take the modular square root and see if the answer was a square. If it isn't, increment the modulus by 4 and try again. After approximately attempts you will have a product, , that is a square and you will have your answer (if does have a modular square root!).
I roughly estimate that when is approximately 2 times that the numbers of modulus you need to try is . However, a word of caution: the modular square root operation is a relatively slow operation, and the factoring and seiving of the divisors is also relatively slow.
According to [5] once either and is known, one can pick a modulus, , which is both and . When this happens then will be a multiple of , and will also be a multiple of . As such it will be possible to divide by and reduce, or implode, the product. If is big enough, then the remainder of stops being a remainder and starts being a product. At this point you can factor and reconstitute
Note: This method of deriving or is equivalent to the traditional Chinese Remainder Methods where and are known and used to derive . This is because, knowing one can always derive via the equation:
However, there are two cases where this method of imploding the product is superior to traditional Chinese Remainder methods.
Besides and no factor of the modulus, , can evenly divide in the following equation:
As a factor of the modulus, , is by definition and only and are where and are both primes.
People may legitimately ask whether it is possible for a factor of modulus to divide a sum under that modulus. This is true, but the theorum is still relevant because the factor of can't be a factor, not just that it can be a factor that can't be divided by.
Since common factors of (p-1) and (q-1) are also present in the factorisation of p*q-1, factors of p*q-1 are candidates for divisors of B*E when where is a common factor of (p-1) and (q-1), and thus also a factor of p*q-1.
As it works out
and
Most times, though you are interested in the case where is a square as in . In this case
and
In the first equation when there is a common factor between and this common factor will appear in the whole sum: . This common factor will also be a factor of since .
Likewise when there is a common factor between and this common factor will also appear in .
Since there are two possible common factors at play, then it is twice as common as random that a factor of will appear in an iteration of, say, where to . In this way it is quite easy to come up with a small factor of , although a big factor is still hard to obtain.
Likewise, taking the equation:
it is twice as likely that a factor of will appear in an iteration of the above equation (where n goes from 1 to 30, say). In this case common factors may appear in and . The subtraction of these: .
Both factors of and can be evenly divided from the sum . Factors of can be divided once and factors of can be divided twice (by the square).
If you take a factor of , a factor of , and divide them, you get the following:
Since:
and
and
If you square this then you get:
As well:
Since the section above shows how to get a few possible small candidates of factors of (p-q) and factors of (p+q), we can get the fraction of the large factors of (p-q) and (p+q).
If we take [| RSA768], the largest RSA number factored so far, the factorization of (p-q) is:
{{3, 1}, {13, 1}, {2663267, 1}, {1220501291, 1}, {1841645951176282753, 1}, {13997633621862976969633164898062916727, 1}}
and the factorisation of (p+q) is:
{{863, 1}, {39685579, 1}, {57151500641, 1}, {35876917512866434717253057870281548347589681335861687, 1}}
If we can iterate the factors of (p+q) and the factors of (p-q) at twice the random rate then we can find 13 and 863, the least of the factors involved in the two sums, in around (1 million)/4 possibilities (and 500 factorizations of p*q+n^2 and 500 factorisations of p*q-n^2), which is possibly achievable using Mathematica or any other number of math packages.
Take a mathematica equation showing the iteration of below. Note that the factorisation of this sum is important.
Table[{x, GCD[(1013 - x), (331 + x)], GCD[(1013 + x), (331 - x)], FactorInteger[1013 331 + x^2]}, {x, 0, 30}] // Grid 0 1 1 {{331,1},{1013,1}} 1 4 6 {{2,3},{3,2},{4657,1}} 2 3 7 {{3,1},{7,2},{2281,1}} 3 2 8 {{2,4},{19,1},{1103,1}} 4 1 3 {{3,1},{111773,1}} 5 336 2 {{2,5},{3,1},{7,1},{499,1}} 6 1 1 {{41,1},{8179,1}} 7 2 12 {{2,3},{3,1},{89,1},{157,1}} 8 3 1 {{3,3},{12421,1}} 9 4 14 {{2,3},{7,1},{53,1},{113,1}} 10 1 3 {{3,2},{83,1},{449,1}} 11 6 64 {{2,6},{3,1},{1747,1}} 12 7 1 {{7,1},{173,1},{277,1}} 13 8 6 {{2,4},{3,1},{29,1},{241,1}} 14 3 1 {{3,1},{111833,1}} 15 2 4 {{2,3},{41941,1}} 16 1 21 {{3,1},{7,1},{19,1},{29,2}} 17 12 2 {{2,3},{3,2},{59,1},{79,1}} 18 1 1 {{37,1},{47,1},{193,1}} 19 14 24 {{2,4},{3,4},{7,1},{37,1}} 20 3 1 {{3,1},{317,1},{353,1}} 21 32 2 {{2,7},{43,1},{61,1}} 22 1 3 {{3,1},{19,1},{43,1},{137,1}} 23 6 28 {{2,3},{3,1},{7,1},{1999,1}} 24 1 1 {{335879,1}} 25 4 6 {{2,3},{3,1},{13997,1}} 26 21 1 {{3,2},{7,1},{5333,1}} 27 2 16 {{2,5},{10501,1}} 28 1 3 {{3,2},{107,1},{349,1}} 29 24 2 {{2,4},{3,1},{47,1},{149,1}} 30 1 7 {{7,1},{48029,1}}
Note in the fifth iteration that there is a factor of seven. Seven also appears as a factor in the 12th iteration, or the (5+7) iteration.
If we were to multiply the 5th iteration with the 12th, we would have a case where the 7 factor was now a square. If we were then to take the (5+3) iteration (since there is a 3 factor in the fifth iteration) and multiply it with the 5th were would have a case where the resulting equation had a 3 as a square. Don't forget that is always a square. If we were to take some time and using this method construct a equation that was totally a square then we would have equivalent squares. Equivalent squares is usually enough to factor and .
Given:
Now make the modulus, , via
Taking the naiive equation:
Now take the augmented equation:
Note that and that
Thus, the product (not the remainder) has been successfully divided, or imploded, to a smaller product and that:
This method of imploding the product is superior to Traditional Chinese Remainder Methods when the divisor, , is a divisor of . In this situation then and can be used as the divisors. Thus, if then and can be determined from
Given:
Now make the modulus, where then will do.
Now note that the naiive equation is:
and the augmented equation is:
and that:
Note that you cannot determine and solely from knowledge of and solely using the Chinese Remainder Theorum!
Note that when the third modulus, X, is a factor of P-Q, then both B and E can be determined by a modula square root of .
As such let's take to be the modulus, which is a factor of P-Q:
Note that
Since and then then,
and so:
As such we can take the modular square root of the modulus, since it's prime factorisation is known, and:
Thus, and .
Thus, if a factor of is known then and can be worked out. Note that it is possible to find at twice the random rate the factors of . This is worked out in the section Common Factors of P-Q at twice the random rate
Let's take, from the above example, the case where is the modulus, for and .
Since , then and .
Since and then the equation above can be rewritten for the modulus: as: . So adding .
From we can construct by the following manner:
Thus:
So:
If we divide by the common term, 3, and minus by 6 (the addition of 3 and 3) then we get:
As such we can minus
If there is a common factor between and , then this will also be a factor of , since
Accordingly, any common factor of and will appear also in . Many factors of will not be factors of and but all common factors will be.
As well any common factor of and will also be a factor of ! As such, the square of any such factor can be divided as per the example just above this section.
Furthermore, the square of a common factor, shown just above, is a factor of the totient of , and it is possible to find out the decryption key of an RSA triple (Encypt key, Decrypt key, Modulus) mod the square of the common factor:
Given:
As you can see above, is the common factor. Common factors will always appear in the factorisation of but not every factor of this sum will be a common factor. McKee and Pinch also note that the common factor of p-1 and q-1 can be found in the factorisation of p*q-1[6]
This common factor will have implications for RSA.
Given:
So some information about the private key is leaked, specifically . As well, a factor of is revealed so my product implosion scheme is invoked.
So it is never a good idea to have a common factor between and except perhaps 2 or 3. I have looked at current RSA key generation methods and none of them explicitly mention that common factors between and should be avoided. I think that the RSA key generation protocols should include this prohibition! KoblitZ also enjoins against large GCD(p-1,q-1) in his public key cryptography book[7] The original RSA paper also made note of this [8]
I have checked through the key generation code of the openssl ssl code. I hacked it to report the greatest common divisor of p-1 and q-1. I then ran 100 key generations. It only had greatest common divisors of 2, 4 , 8, and 16. There were no other primes reported besides small powers of 2.
Viktor Dukhovni, from the openssl-dev@openssl.org newsgroup[9], reports, after looking at the rsa key generation code of openssl, that p-1 and q-1 are both checked for the first 2048 factors (up to 17863). As such they are not possible as factors of either p-1 or q-1. However, common factors higher than 17863 are possible as factors of both p-1 and q-1, however it takes 20,000 key generations (not in safe mode) before such an event happens. He managed to get a common factor of gcd(p-1,q-1) = 2 * 28559 from the following 1024 bit rsa generated key (factorisation of p*q-1 is shown):
5485062554686449262177590194597345407327047899375366044215091312099734701911004226037445837630559113651708968440813791318544450398897628 67234233761906471233193768567784328338581360170038166729050302672416075037390699071355182394190448204086007354388034161296410061846686501 4941425056336718955019
Let's say that the message is and that the cipher is , because and that then the message, can be split into two powers based on the cipher such as:
Therefore:
or
or
Now:
and note- not a power multiple of 23!.
253503289===148815052^(23(totient-6290)) see above Solve[253503289 2^23 + x 3^23 == 0, {x}, Modulus -> 8467 39343] {{x -> 201204739}} See Australian Innovation Patent 2018100919 for explanation of this following equation Mod[253503289 2^22 PowerMod[201204739 3^22, -1, 8467 39343], 8467 39343]=166558589 see equations above Mod[148815052^6290 166558589, 8467 39343]= 67952848 Notice the message with the 23rd root of another number has been found Mod[37 PowerMod[201204739, -1/23, 8467 39343], 8467 39343]= 67952848
Since is always a multiple of the totient, we can apply 4 to the equations always instead of 83 as we have in the above example:
Thus, it is always possible to get the secret message to a power that is not a multiple of the public key!
Including the math in User:Endo999#A_Close_Call_ON_RSA, we can see that we have the and the which allow us to apply in part the math from "A Close Call On RSA":
get cipher1 Mod[37^23, 8467 39343]= 148815052 Mod[ 148815052 PowerMod[148815052 , -22 3, 8467 39343], 8467 39343]= 331864148 Mod[37 PowerMod[37, 23 22 4 79647023, 8467 39343], 8467 39343]= 331864148 get cipher2 Mod[41^23, 8467 39343]= 330768180 Mod[330768180 PowerMod[330768180, -22 3, 8467 39343], 8467 39343]= 98398282 Mod[41 PowerMod[41, 23 22 4 79647023, 8467 39343], 8467 39343]= 98398282 solve x power1^e + y power2^e===0 Solve[ x PowerMod[37, 23 23 4 79647023, 8467 39343] + y PowerMod[41, 23 23 4 79647023, 8467 39343] == 0, {x, y}, Modulus -> 8467 39343]= {{x -> C[1], y -> 136895256 C[1]}} Mod[-PowerMod[37, 23 23 4 79647023, 8467 39343] PowerMod[ 41, -23 23 4 79647023, 8467 39343], 8467 39343]=136895256 apply x power1^(e-1) (y power2^(e-1))^(-1) to get (x/y)^(1/e) Mod[ 2^23 331864148 PowerMod[136895256 2^23 98398282, -1, 8467 39343], 8467 39343]= 186681852 get m1/(m2 136895256^(1/e)) Mod[ 37 PowerMod[41 PowerMod[136895256, 1/23, 8467 39343], -1, 8467 39343], 8467 39343]= 186681852 this number is also Mod[-PowerMod[37 , 23 3, 8467 39343] PowerMod[41 , -23 3, 8467 39343], 8467 39343]=186681852
This is a transformative equation since it makes knowing the division of two secret messages to be the taking the eth root of another number, whose cipher is calculable
Now that we have
and we know the cipher, or we can use Pollard's Kangaroo Discrete Logarithm Algorithm to solve the log (which is a factor of ). As such we can take the base for the discrete logarithm algorithm to be and that (with us knowing and ) , we can solve for in . If the common factor is high enough we can actually do this, however, most of the time the term will still be too high. However, the RSA cipher is transformed since , so the decryption key can be determined using this method.
Since and e is odd, then d must be odd and the same equations can be applied to any RSA cipher as in the section above. Seeing that and , then
and
Therefore, since ,
(Note that and are known).
Thus, you can apply Pollard's Kangaroo Algorithm to any RSA Cipher to get .
Take then is true. Since and are known then can be found using Pollard's Kangaroo Discrete Logarithm Algorithm.
Since then is in the same power ring as and the power ring length for both sums will be the same. In fact the power ring length for 37 (), 148815052 () and 158806108 () is the same: 668814. Since , then the actual logarithm to be found by the Kangaroo algorithm will be . However, , so finding for is also finding the for .
Seeing that the power ring length of the message, in this example, is and the modulus is , one can see that often in practice the power ring length is 2/3 in bit length of the modulus, and that the Kangaroo algorithm will only take 1/3 the bit length of the modulus to find an appropriate power (in our example, ). Thus, properly calibrated, the Kangaroo algorithm will often be a algorithm, and not as you would naively think.
It's always possible to get an equation like that above with any base. Take for instance.
The math in this section is totally theroretical since you can always use Pollard's RHO method to factor P*Q in time.
If p-2 is a prime, and q-2 is a prime and both p and q are primes (twin prime) then the Dedekind_psi_function()[10] is the totient of p*q. For instance, the Dedekind PSI function of the primes 107*137 would be (107+1)(137+1)=(109-1)(139-1) so this number would be the totient function of 109*139, a semiprime.
Since common factors of p-1 and q-1 will be factors of p*q-1, then these common factors will be factors of (p-2+1) and (q-2+1) in the case of common factors of the RSA semiprime totient(p-1)*(q-1) a factor of the Dedekind PSI function of (p-2)*(q-2) can become known.
Interestingly, Dickson in his vol 3 of "History Of The Theory Of Numbers" doesn't seem to remark on Dedekind's PSI function, which deals with modular forms. The Third volume of Dickson's work is devoted to Modular forms.
Dickson does refer to the Dedekind PSI function at Vol 1, p123 where he states:
R. Dedekind[11]proved that , if n is decomposed in every way into a product ab and if e is the g.c.d. of a,b then
where a ranges over all divisors of n and p over the prime divisors of n.
note that is the totient function.
For the purposes of semiprimes then the addition of the factors, 1, n, p, q will equal the multiplicative PSI function (p+1)(q+1). Thus, this equation of Dedekind's unwinds the multiplication of the right side (with the prime factors) and equates this with the addition of the divisors on the left side of the equation. A change in operation from multiplication to addition is thus seen.
For RSA semiprimes, a square factor of the Dedekind PSI function of P*Q can be found by factoring p*q+1.
This will reveal common factors of p+1 and q+1, if there are any besides two.
The square of these common factors is then a factor of the Dedekind PSI value of P*Q
The common factors of p-3 and q-3 can be found by factoring p*q-9.
See User:Endo999#The_Bad_Stuff_That_Happens_When_There_Are_Common_Factors_Between_(P-1)_and_(Q-1) here for a more complete explanation of common factors in p-1 and q-1 in rsa.
With knowledge of a common factor for both p-3 and q-3 then 0 mod (commonfactorofp-3)*(commonfactorofq-1) can be found.
which will be a factor of p*q-p-3q+3. Running -p*q mod n|(p*q-p-3q+3) will establish p+3q-3 mod n|(p*q-p-3q+3). By knowledge that p (and also q)mod commonfactorofp-3 === 3 and p(and also q) mod commonfactorofq-1 === 1 then it will be possible to establish p+q mod n|(p*q-p-3q+3). Indeed, if we ever knew when a p-x and q-x had common factors, then this could be used, via the Chinese Remainder Theorum to establish p+q mod alargenumber. However, we don't know when the common factor arises, we just know candidates for it, if it is there.
This could work for cousin prime as well (when p, q, p-4, and q-4 are all primes). In fact the math shown just above could work for any combination of primes (p, q, p-x,q-x) when p-1 and q-1 have common factors and p-x and q-x have common factors.
According to [12] if:
then
which is both
as well as being
It is remarkable that such a humdrum equivalence as could also have such a remarkable equivalence as .
Thus if I could take token from Joe, and convince Joe that I am signing the 1010 divided by 1652 (which I have obtained from the equation above), then I could convince Joe that I have RSA signed with Jack's secret key, even though I am Brad, and I only know Jack's modulus.
even though
Again according to [12] if
then RSA is broken for the token 2441, since:
and
It is hard to set this equation though.
Thus it is very important that when the RSA user presents a number for his opponent to sign that that opponent DOES NOT add a divisor of his own to this number. This can fool the unwary.
Now you could achieve the same spoof by 1) select a residue randomly:A, 2) increase this residue to the 23rd power:B, 3) take the number given by the other party (C) (the number to be signed) and find the other number that transforms this to B: D, 4) then say you are signing C divided by D by providing A.
Although this is quite similar to the process I have described above, in my process, I derive both B and C before I derive A, that is the root is determined AFTER the powers, not BEFORE.
This method of imploding the product is superior to Traditional Chinese Remainder Methods when a multiplier, , is used to make look like to the modulus .
According to [13], the multiplier is defined as:
When this is multiplied to then the remainder can safely be divided by .
Given:
Now make the Multiplier:
Now make the modulus, where then will do.
Now note that the naiive equation is:
and the augmented equation is:
and that:
and that
and that
Note that when the multiplier is very low then this method is superior to traditional Chinese Remainder Theorums.
When is approximately times (or any power of 5) greater than , then it is possible to factor a number (by guessing one number within the square root of q from q). Example:[4]
This works because in RSA semiprimes (Internet HTTPS RSA keys) are always and .
In the above discussion a multiple of 5 was used for the modulus, and this affected the coefficient. If the modulus is redefined from to , then a multiple of 3 can be used for the modulus. Example:
Thus, we can divide by 2 again to get another multiple of the term, which is in the above equation.
In the above case, since or .
So it is possible to come up with different multiples of , and then perform arithmetic operations on them. In this case above,
Note that the actual product has declined to a tenth by this operation. For small numbers it is possible to actually change the to an actual product, which can be factored, leading to and discovery.
If we take a slight deviation from our normal equation of and say the following:
and create an equation like this:
then the following equations hold:
Most of the other equations feature not as we have above. Plus if we minus 9*3405, where we know 9, we get:
This new behavior, where we get in one of the terms of the equation, is a totally new feature of the equations we have been establishing. Mostly, we get when we have equations of the term:
We get in the following equations:
These above residues can actually be shown as full sums. For instance:
so
can produce equations featuring both and
Extending the modulus to gives us an unusual property that is explained below:
or
which can be turned into (by reversing the sign).
Thus, the multiplier in the sum for one of the terms is sharply reduced, from to .
The best I have been able to do with this sum above is to turn it into
If we could indeed create both terms to the exact same coeficient then we could reduce the term to
which is not a residue but an actual sum. Alas, I have not been able to do this.
You can get and thus solve to retreive by
Once you know you don't actually have to factor , which saves much time. You can create two numbers, and , separate them by and then increment them until they either match or exceed .
In the case where is a factor of (see earlier section for this algorithm), then
Pollard's excellent Kangaroo algorithm can be adapted to leap in bounds instead of bounds, as it normally does.
The time to compute will be dividing the total time to do by instead of as when the bound for the Kangaroo algorithm is 1. When the earlier product implosion algorithm still doesn't create a product out of the remainder, then this algorithm can still be used as it can process the quotient part of the product in .
For instance, for a 1000 bit modulus, will be a 500 bit number. If is a 125 bit number then the answer can be found in bit operations. This is approximately operations. To find a that is 125 bits in length will entail approximately operations. To iterate this to , using Traditional Chinese Remainder methods, will take around operations for a combined total of operations.
However, to take the that is 125 bits and then apply the extended Pollard algorithm to the equation above will entail operations, that is approximately .
It looks like the earlier naiive version of the algorithm (when ) is the best since it will take operations. But anytime you have a on hand the new method will be faster.
When the third modulus is no is required. The equation is:
This also works when the modulus is . The equation is:
One way to define numbers one off each other is via:
Thus, the general equation is:
Sometimes, there is, indeed, a , a type of modular imaginary number. It only seems to appear for semiprimes that are both . The following treatment of this number is similar to Euler's factorisation method: [[1]].
If there are two of these modular imaginary numbers, as there often are, then both have an intimate relationship with . The following group of equations summarises this:
The inverse of the I number is its negative number
For and and and , then:
As well, there is a intimate relationship between , and and . The Chinese Remainder of these last two residues will either be or . Thus
The other combination will reveal another quad root of 1. Thus if the equation above revealed , then
This is, in effect, a definition of two of the square roots of , and tends to indicate that there are no quad roots of 1 for 3 mod 4 semiprimes. This conjecture is shown to be probably true in Mathematica test code. (There are quad roots when 1 semiprime is 1 mod 4 and the other is 3 mod 4).
I was able to get the complex square root function to work, in modular arithmetic. This work is only done on 1 mod 4 semiprimes. Please consult this link Complex_number#Square_root, for the formula. My work is as follows:
Take . Construct a simple complex form: where and .
Construct (according to the complex square root formula):
Now we have the intermediate terms of the complex moduluar number. Instead of use the other :
Thus, the complex square root equation does have an analogue in modular arithmetic, but we need to know one of the square roots of -1 mod p*q and we need to take three modular square roots in order to derive the sum.
In an example that will show that sometimes you can use the same , we will show the case where the root is of the type:
Take the form of . This simplifies the three square roots that are to be taken considerably. As we only need to take one square root:
Now that we have the intermediate term of then the root can be made as:
We don't even need to take a modular square root if we construct the square as:
In this case the square root is:
or the square is:
and the root is:
This all works because
According to [14][15], Pythagorean Triples can populate the Complex Square Root formula in modular arithmetic without taking a modular square root for the intermediate values. The intermediate values all derive to natural squares.
Quoting from [15]:
More specifically, the Pythagorean Triples should be primitive Pythagorean Triples or primitive Pythagorean Triples multiplied by squares.
The equation for the square root, of the square , will resolve to . Therefore the square , will resolve to .
is the most famous Pythagorean Triple. If we pass these parameters into the Complex Square Root formula we get the following calculations:
As such
or , and .
Please note that and .
Therefore
, , and .
It is possible to work this formula out with the the ComplexExpand[...] command of mathematica, as in:
ComplexExpand[((a + b) + (a - b) (-1)^(1/2))^2] // this is the root formula 4 a b + I (2 a^2 - 2 b^2) // this is the formula for the square
However, if you can describe the square (with knowledge of ) using the parameters of the pythagorean triple, you can instantly derive the square root. Thus knowledge of one of the allows large numbers of modular square roots to be instantly taken.
Since then .
As mentioned in [16], the following equation generalizes the taking of a square root using the Pythagorean Method mentioned above:
For instance, for Pythagorean Triple where and and and , then take any root square combination, such as: . In this case:
and
This works for the negative root as well:
and
This equation is close to the regular binomial square formula, except that you can go from the square to the root.
Interestingly, the product of both these answers, and , is the subtraction of two squares, and its square root is also the subtraction of two squares.
and this sums square root is:
Thus this number forms the second part of a Pythagorean Triple:
With and
and
we have some roots and some squares.
If and , and m is a Pythagorean Triple (ie., (a Modular Complex Number), then the cipher, has a secret message that can be deciphered as such:
ComplexExpand[(3 + I)^23] 138606163968 + 284232882176 I or (3+I)^23 mod p*q= 138606163968 + 284232882176 I
Just remember to take the pythagorean triple and create the root modular complex number via the method shown above. In this case, above, and and . Thus if where .
The Quadratic residue article on Wikipedia says that taking modular square roots of p*q modulus is equivalent to factoring the p*q modulus.
If the complete factorization of n is not known, and and n is not congruent to 2 modulo 4, or n is congruent to 2 modulo 4 and , the problem is known to be equivalent to integer factorization of n (i.e. an efficient solution to either problem could be used to solve the other efficiently).
By way of a counter example I will show that some modular imaginary numbers are quite easy to find. For instance,
Now that we know as one of the two imaginary numbers of modulus , we are still not in any condition to factor , for we need two imaginary numbers to do that. However, using the Pythagorean method of populating the complex square root theorum, and knowing one of the , we can take almost unlimited numbers of modular square roots almost instantly, via the mathematical reasoning shown just above.
Therefore, for some P*Q 1 mod 4 semiprimes, it is not necessary to factor the modulus to find and thereafter many modular square roots can quicky be taken. The conjecture quoted above is shown not to be fully correct.
Quoting from the Quadratic residue article on Wikipedia again:
The above discussion indicates how knowing the factors of n allows us to find the roots efficiently. Say there were an efficient algorithm for finding square roots modulo a composite number. The article congruence of squares discusses how finding two numbers x and y where x2 ≡ y2 (mod n) and x ≠ ±y suffices to factorize n efficiently. Generate a random number, square it modulo n, and have the efficient square root algorithm find a root. Repeat until it returns a number not equal to the one we originally squared (or its negative modulo n), then follow the algorithm described in congruence of squares. The efficiency of the factoring algorithm depends on the exact characteristics of the root-finder (e.g. does it return all roots? just the smallest one? a random one?), but it will be efficient.[17]
Please note that I have shown:
I cannot
Therefore, I cannot use my ability to take a modular square root to find the other square root. Therefore, although I can take a square root I cannot factor the semiprime.
Euclid's famous formula for generating Pythagorean Triples is the following:
I've come up with another formula for generating Pythagorean Triples. The math has to do with multiplying in the SQUARELESS number I have spoken of in other parts of this blog.
There are two such squareless numbers in a p*q modulus. They have several properties that make them interesting to applying to the Pythagorean Triples method of using the Complex Square Root formula in modular arithmetic.
Replacing the equations above with equations involving the squareless numbers, we can see that the coefficients for the square are:
and the coefficients (and equation) for the root are:
We can reduce these equations for , and to:
The equations for the coefficients of the roots also simplify
You will notice that the imaginary coefficients for both the square and the root involve , which is unknown.
There is an intimate relationship between the square root of 1 and the two square roots of -1. It is .
Thus the term cancels out when we apply the known to it. Thus the working equations for the imaginary coefficient for the square modular square is:
and the working equation for the imaginary coefficient of the root is:
This SQUARELESS number cancels out eventually leaving the following formula:
or
The coefficients for the root, considering that the square matches the coefficients given above is:
Bottari, in 1908, as reported by Dickson's History Of Numbers vol 2 p169, does show a more general form of my equations shown here for the Pythagorean Triple, but, most probably, he did not use the SQUARELESS number to derive the equations. Thus, although the equations have been worked out before, the way they are derived is probably unique. See here for the relevant quote from Dickson of Bottari's work.
Looking at the definition of Quaternion#Definition which has its definition of the three imaginary numbers of the system:
i2 = j2 = k2 = ijk = −1,
It does seem that the ,, and come close to this definition, but they do not quite make the definition.
This is close to the Quaternion imaginary definition. However, I was not able to make the Quaternion inverse work with modular arithmetic, nor was I able to make the Hamilton Product work with modular arithmetic. The definitions for the imaginary numbers are close to Hamilton's so I suspect an analogue operation may eventually be found.
Looking at my definition of the quad root of 1, it seems that this definiton is close to a quaternion (with all the coefficients being the same):
This above number is a type of Hurwitz quaternion, which is defined as:
a Hurwitz quaternion (or Hurwitz integer) is a quaternion whose components are either all integers or all half-integers (halves of an odd integer; a mixture of integers and half-integers is excluded).
After some research in the Wikipedia, it does seem that the imaginary units I have put forth have been written of already as Bicomplex number or tessarines by James Cockle (lawyer) in 1848.
Quoting from Bicomplex number:
In 1848 James Cockle introduced the tessarines in a series of articles in Philosophical Magazine.[18]
A tessarine is a hypercomplex number of the form
where Cockle used tessarines to isolate the hyperbolic cosine series and the hyperbolic sine series in the exponential series. He also showed how zero divisors arise in tessarines, inspiring him to use the term "impossibles." The tessarines are now best known for their subalgebra of real tessarines , also called split-complex numbers, which express the parametrization of the unit hyperbola.
In the case of modular tessarines, then , and .
Quoting the imaginary multiplication table from Bicomplex number:
|
|
There are some minor differences, but mostly the same for the two systems.
I was able to come up with an analogue, for this Quaternion-like system, for both the conjugate, the form, and the multiplicative inverse. Given , and , then the conjugate of would be:
There is a norm to this (which isn't great) of:
and so the multiplicative inverse is:
(It can be seen from the above definition that the norm of modular quarternions where , or , is indeed the norm of quaternions: and thus, looking at the definition of the quad root of 1 mod p*q, as a modular quaternion (see above), the norm is . This makes the quad root of 1 a unit quaternion. I suspect that all roots of 1 have norms of 1, since the cube root of 1 also has a norm of 1)
Since we know the norm of the quad root of 1 to be 1, we can take a stab at the inverse of the quad root of 1:
In[6]:= Mod[PowerMod[2, -1, 89 29] (1 + 568 + 945 + 2493), 89 29] Out[6]= 713 In[7]:= PowerMod[713, -1, 89 29] Out[7]= 1781 and the inverse of the quad root of 1 is: In[9]:= Mod[(1 - 568 - 945 + 2493) PowerMod[2, -1, 89 29], 89 29] Out[9]= 1781
Thus the inverse of the quad root of 1, after considering it as a modular quaternion, is:
See User:Endo999#The_Cube_Root_Of_1_Defined_In_Polar_Coordinates for the cube root of -1 shown as a quaternion, and it's inverse successfully computed.
An example, showing a conjugate, norm, and multiplicative inverse, follows:
A modular quaternion for is:
The conjugate is:
The norm(it's odd) is:
and the multiplicative inverse of quaternion , given above, is:
Multiplication follows the following rule:
Mod[(29 + 13 568 + 17 945 + 23 2493) (39 + 23 568 + 27 945 + 33 2493), 89 29]==2172 In[15]:= Mod[k (a w + b x + c y + d z) + j ( -b w + a x - d y + c z) + i (-c w - d x + a y + b z) + d w - c x - b y + a z, 89 29] /. {k -> 2493, i -> 568, j -> 945, a -> 29, b -> 13, c -> 17, d -> 23, z -> 39, y -> 23, x -> 27, w -> 33} Out[15]= 2172
It is somewhat similar to the Hamilton Product but is different regarding the non i,j,k items.
Quoting from Quaternion#Exponential,_logarithm,_and_power:
Exponential, logarithm, and power Given a quaternion,
the exponential is computed as
- .[19]
It follows that the polar decomposition of a quaternion may be written
where the angle and the unit vector are defined by:
and
Any unit quaternion may be expressed in polar form as .
The power of a quaternion raised to an arbitrary (real) exponent is given by:
Dealing with the Logarithm, it would be particularly attractive if a LOG2 could be taken of a Quaternion, in that the Diffie Hellman Key Exchange Protocol deals with discrete logs, and the prime modulus of the key exchange would help in taking the square roots in this regard. However, my initial researches into this matter show that the ARCCOS[x] function that is part of the LOG function, seen above, always returns a nonrational number. In general, all numbers that are part of a modular equation need to be rational.
However, we can create modular Quaternions that have natural squares for both the Norm of the Quaternion and the norm of the vector part of the Quaternion. We simple zero out A and C, for instance, and set B and D to be parameters of a Pythagorean Triple, such as Quaternion[0,3,0,4] where the and the norm of the vector for this Quaternion equals 5 as well. So we are almost at the point where the LOG2[Quaternion[0,3,0,4]] could be taken, alas, the ARCCOS[0] returns which is not rational. However, the log2[Quaternion[0,3,0,4]] returns:
In modular arthmetic, the but the PI value cannot be instantiated in a MOD P*Q scheme.
So it looks like there is no LOG2 analogue for a modular quaternion.
Dealing with the de moivre square like formula of Quaternions, things look a bit better. Getting the of the Quaternion[0,3,0,4] is okay:
where the formula for the square is:
Setting then . This happens for the as well.
However, my inital enquiries show that there is no analogue for the demoivre theorum. Using as the modulus I get the equation:
Mod[372155 (1574679 + (3 1574679 246254 + 4 1574679 1925202) PowerMod[ 5, -1, 1201 4801]), 1201 4801] =1342976 where 372155 is the square root of 5 1574679 is the inverse square root of 2 246254 is the square root of -1 1925202 is the square root of 1 However, PowerMod[Mod[3 246254 + 4 1925202, 4801 1201], 1/2, 4801 1201] 2118921
According to YouTube Mathologer video [[2]], the number PI can be expressed as .
Working with this I was able to get a rough relationship with SIN[PI/4] and SIN[PI/8] and the sum given above.
Mod[PowerMod[3, 1/2, 97 47] + PowerMod[2, 1/2, 97 47], 97 47] = 2110
I'm still working out the properties of this modular number but there is one I can point out right now.
There is often a direct relationship between the SIN[PI/4] and SIN[PI/8] and sqrt{2}+sqrt{3}.
and
This relationship happens around half the time that there is a modular square root for 2 and for 3 in the P*Q modulus.
I have constructed a Mathematica function here that will demonstrate this relationship:
try222a[p_, q_] := Module[{a1, a2, a3, a4, a5, a6, a7, a8, a9, a10, a11, a12, a13, a21, a22, a23, a24, a25, a26, a27, a28, a29, a210, pq}, a1 = NextPrime[p, 1]; a7 = 0; a8 = 0; a11 = 0; a12 = 0; For[a2 = 1, a2 < 100, a2++, a1 = NextPrime[a1, 1]; a3 = NextPrime[q, 1]; For[a4 = 1, a4 < 100, a4++, a7++; If[1 == 1, If[IntegerQ[PowerMod[2, 1/2, a1 a3]] && IntegerQ[PowerMod[3, 1/2, a1 a3]], a8++; Print[{a1, a3}]; pq = a1 a3; a21 = Mod[PowerMod[2, 1/2, pq] + PowerMod[3, 1/2, pq], pq]; a22 = PowerMod[2, -1/2, pq]; a23 = Mod[4 a22, pq]; a24 = Mod[a21 - PowerMod[a21, -1, pq], pq]; a29 = Mod[a21 + PowerMod[a21, -1, pq], pq]; a25 = Mod[PowerMod[2 - PowerMod[2, 1/2, pq], -1, pq] PowerMod[ 2, -1, pq], pq]; a210 = Mod[PowerMod[2 + PowerMod[2, 1/2, pq], -1, pq] PowerMod[ 2, -1, pq], pq]; a26 = Mod[a25 8, pq]; a210 = Mod[a210 8, pq]; a27 = Mod[(PowerMod[3, 1/2, pq] - 1) PowerMod[ 2 PowerMod[2, 1/2, pq], -1, pq], pq]; a28 = Mod[12 a27, pq]; Print[{a21, a22, a23, a24, a25, a26, a28, a29, Mod[-a210, p q]}]; a13 = 0; If[a23 == a24 && a23 + 4 == a26, a11++; a12++;, If[a23 + 4 == a26, a12++; ];]; ]; ]; a3 = NextPrime[a3, 1]; ]; ]; Print[{a7, a8, a11, a12}]; ]
If you run this function, and iterate through 10,000 P*Q semiprimes, of all descriptions, you get
try222a[88, 28] {9801,506,269,269}
This output is one of totals. There are 9801 semiprimes tested, 506 have both modular square roots for both 2 and 3, and 269 of them have both relationships shown above. That's about half of the possible candidates. I have no explanation yet while this is so, but the prevalence of the relationships between the SIN[PI/X] and ~PI-~PI^{-1} is very strong. Possibly, the roots for the other half of the nonmatching candidates are not in alignment (square root of 1 in the way). This would nicely account for the other half of the candidates that don't match.
Working with a modified mathematica procedure, I was able to come up with this definition of the modular square root of 2 mod p*q.
I give the following Mathematica procedure to show this as examples:
try222b[p_, q_] := Module[{a1, a2, a3, a4, a5, a6, a7, a8, a9, a10, a11, a12, a13, a21, a22, a23, a24, a25, a26, a27, a28, a29, a210, pq}, a1 = NextPrime[p, 1]; a7 = 0; a8 = 0; a11 = 0; a12 = 0; For[a2 = 1, a2 < 100, a2++, a1 = NextPrime[a1, 1]; a3 = NextPrime[q, 1]; For[a4 = 1, a4 < 100, a4++, a7++; If[1 == 1, If[IntegerQ[PowerMod[2, 1/2, a1 a3]] && IntegerQ[PowerMod[3, 1/2, a1 a3]], a8++; Print[{a1, a3}]; pq = a1 a3; a21 = Mod[PowerMod[2, 1/2, pq], pq]; a22 = Mod[PowerMod[3, 1/2, pq] - PowerMod[PowerMod[2, 1/2, pq] + PowerMod[3, 1/2, pq], -1, pq], pq]; If[(a21 == a22), a11++;, ]; ]; ]; a3 = NextPrime[a3, 1]; ]; ]; Print[{a7, a8, a11}]; ] try222b[88, 28] {9801,506,506}
Some of the output shown above of this procedure shows that among 9801 semiprimes, 506 had both modular square roots of both 2 and 3 and that all 506 of these had the definition of the modular square root of 2 given above.
Working on the definition of the modular square root of 2 mod p*q found in the previous section, it seems that this type of definition of the square root of r in terms of the square root of r+1 applies to all modular square roots mod p*q.
I give the following Mathematica procedure to show this as examples:
try222c[p_, q_, r_] := Module[{a1, a2, a3, a4, a5, a6, a7, a8, a9, a10, a11, a12, a13, a21, a22, a23, a24, a25, a26, a27, a28, a29, a210, pq}, a1 = NextPrime[p, 1]; a7 = 0; a8 = 0; a11 = 0; a12 = 0; For[a2 = 1, a2 < 100, a2++, a1 = NextPrime[a1, 1]; a3 = NextPrime[q, 1]; For[a4 = 1, a4 < 100, a4++, a7++; If[1 == 1, If[IntegerQ[PowerMod[r, 1/2, a1 a3]] && IntegerQ[PowerMod[r + 1, 1/2, a1 a3]], a8++; (*Print[{a1,a3}];*) pq = a1 a3; a21 = Mod[PowerMod[r, 1/2, pq], pq]; a22 = Mod[PowerMod[r + 1, 1/2, pq] - PowerMod[ PowerMod[r, 1/2, pq] + PowerMod[r + 1, 1/2, pq], -1, pq], pq]; If[(a21 == a22), a11++;, ]; ]; ]; a3 = NextPrime[a3, 1]; ]; ]; Print[{a7, a8, a11}]; ] try222c[88, 28, 3] {9801,2304,2304} try222c[88, 28, 4] {9801,2256,2256} try222c[88, 28, 101] {9801,395,395}
A very interesting definition of the modular square root mod p*q if I don't say so myself.
It is not remarkable that:
In fact, it is algebra. However, the inverse operation is supposed to scramble the terms, but instead it seems to function, as the difference between the two squares or r and (r+1).
By taking advantage of natural squares sometimes we can simplify this equation. Take for example the case when :
Taking the other root as a natural we get:
Since the definition of the inverse of a complex number is described here, as
Now the modular definition of the complex number means that, for instance, then the inverse of the two adjacent square roots is:
As such the difference of the squares becomes apparent.
For the difference when the roots are n integers apart then:
Thus, knowing the sum of squares that are 1 apart, allows the knowing of the difference of the squares, and thus of the two individual squares themselves. Since this is because of the complex definition of the inverse then it will also work for knowing the difference of the two squares.
337 is the modular square root of 5 mod 89*29 get the sum of the two roots whose squares are adjacent to each other Mod[(2 + 337)*(-1)= 2242 invert the difference of two roots PowerMod[(2 - 337), -1, 89 29]= 2242
As such you should be able to take any residue mod p*q and invert it and then find the two adjacent squares whose roots equal the residue involved.
If we take the example shown just above, where
So and
therefore and halving 4 gets 2, so 2 is one of the roots and 337 is the other root. Sure enough and . This process can basically happen for any residue of p*q.
We'll take another example of this:
PowerMod[1011, -1, 89 29]= 1399 Mod[-1011, 89 29]= 1570 Mod[-1399, 89 29]= 1182 find the two roots (1570 - 1182)/2= 194 1182 + 194= 1376 confirm the squares are adjacent to each other Mod[194^2, 89 29]= 1502 Mod[1376^2, 89 29]= 1503
Extending the formula given above for the inverse of square roots 1 apart to N apart we get:
From this the following Mathematica routine will find squares N apart from any residue
a is the difference of the roots o is the difference of the squares try222a[a_, pq1_, o_] := Module[{a1, a2, a3, a4, a5, a6, a7, a8, a9, a10, pq}, pq = pq1; a1 = Mod[PowerMod[a, -1, pq] PowerMod[-o, 1, pq], pq]; a2 = Mod[(a + a1) PowerMod[2, -1, pq], pq]; a3 = Mod[-(a - a2) , pq]; Print[{{a2, a3}, {Mod[a2^2, pq], Mod[a3^2, pq]}}]; root1 = a2; root2 = a3; square1 = Mod[a2^2, pq]; square2 = Mod[a3^2, pq];] aa is sum of the roots o is difference of the squares try222b[aa_, p_, q_, o_] := Module[{a1, a2, a3, a4, a5, a6, a7, a8, a9, a10, pq}, pq = p q; a1 = PowerMod[aa, -1, pq]; a2 = Mod[o^2 a1 + o aa, pq]; a3 = Mod[a2 PowerMod[2 o, -1, pq], pq]; a4 = Mod[aa - a3, pq]; Print[{{a3, a4}, {Mod[a3^2, pq], Mod[a4^2, pq]}}]; ] calling this routine we get squares 2 apart try222b[1011, 41, 73, 2] {{1179,2825},{1289,1287}} now we get squares 6 apart try222b[1011, 41, 73, 6] {{2526,1478},{2593,2587}} Feeding in either -1 or 1 as the residue gives us roots as apart as the squares are: try222b[41 73 - 1, 41, 73, 6] {{1493,1499},{2257,2251}} try222b[1, 41, 73, 6] {{1500,1494},{2257,2251}}
Focusing on work done on the difference between two modular square roots, where it has been decided that
it is easily seen that knowing the difference between the two roots will reveal both the roots, if you know the squares.
Take the Mathematica Expand command and the proof is easy to see:
Expand[(a + b)^2 - a^2 - (d + b)^2 + d^2] = 2 a b - 2 b d
Knowing 2(a-d) it is easy to find b. An example follows:
PowerMod[34, 1/2, 89 29]= 482 PowerMod[45, 1/2, 89 29]= 1011 so the difference between the two roots is 529 1011-482 = 529 take 500 as a guess for 34^(1/2), add 529 to it to get 1029 Mod[(500^2) - 34 - (1029^2) + 45, 89 29]= 1604 Mod[1604 PowerMod[2 529, -1, 89 29], 89 29]= 2563=-18 so 500-18=482, the answer and 1029-18=1011 the answer
After experimenting with De Moivre's formula I was able to take a type of square root and even a cube root when and can be expressed as a rational number (a fraction). This work is probably restricted to 1 mod 4 semiprimes and to 1 mod 4 primes.
My work, showing two examples where division of the makes for a square or even cube root.
Since and , then the coefficients for the complex number are .
Since the complex coefficients for would equal the , then the complex equation:
and
then we have found the quad root of -1.
Back to our original quest for a square root, since this is modular arithmetic let's try .
Since we are dividing by 2, then the sine and cosine formulas are:
After some play with the coefficients I had to switch the sin and cos parameters, giving:
Thus the square root of the coefficients for are the coefficients, sort of, for the . Please note that I had to switch the two square roots of -1 in the root and square.
I believe the switching of the sin and cos coefficients and the change of the square root of -1 mod p*q have to do with the reflection around the four axis of the polar coordinates.
For people reading the following examples the wikipedia math article Root_of_unity#Trigonometric_expression is quite applicable. The following two examples show that there are roots of unity in modular arithmetic.
I was able to take the cube root of -1 mod p*q in the following example:
Since and the math is considerably simplified. The sin and cos values for are:
And, interestingly, the following equation is the cube root of -1.
Please note that if the number shown above is then the cube root of any negative number can be derived if the cube root of its positive number is known:
To take the 5th Root of 1, first take the sin and cos of ,
With and
Then:
Thus the fifth root of 1 has polar coordinates.
The Square Root Of 5 mod p*q is found with the following addition and subtraction of the fifth roots of unity, as can be seen from the Square root of 5 wiki article:
The field ℚ[√−5], like any other quadratic field, is an abelian extension of the rational numbers. The Kronecker–Weber theorem therefore guarantees that the square root of five can be written as a rational linear combination of roots of unity:
Thus:
Interestingly, 9045 is the other square root of 5 mod 401*101, but I was unable to come up with
any permutation of the root of unity, 3125, to equal 9045. Use the other fifth root of 1, 10498, to get this figure.
and
In this case the other root of 5 is used to calculate the complex coefficients.
See here for an example of the modular square root of -3 being equal to the sum of the two roots of unity of 3.
Consult Hilbert's twelfth problem where the article says:
Kronecker's Jugendtraum or Hilbert's twelfth problem, of the 23 mathematical Hilbert problems, is the extension of the Kronecker–Weber theorem on abelian extensions of the rational numbers, to any base number field. That is, it asks for analogues of the roots of unity, as complex numbers that are particular values of the exponential function; the requirement is that such numbers should generate a whole family of further number fields that are analogues of the cyclotomic fields and their subfields.
Now we have successfully showed that the 5th root of unity per modulus p*q can be written in polar coordinates, or as modular complex numbers. Are modular complex numbers a contribution to extending the Kronecker-Weber theorem beyond the abelian extensions of the rational numbers? Clearly, the integer values of the modular numbers shown here are subfields of Q, but now that their polar coordinates have been revealed, has a contribution to Hilbert's twelfth problem been shown? Perhaps, an interesting example of the permutation of roots of unity in regular mod p*q fields has been shown.
Since, according to Golden ratio, the Golden Ratio is , then if the modulus has a square root of 5, then there is a golden ratio for the modulus.
And examination shows that some of the properties of the Golden Ratio do hold, although the ways to approximate the golden ratio do not.
And the quadratic equation holds as well as in the following mathematica solve command:
Solve[a^2 - a == 1, {a}, Modulus -> 89 29] {{a -> 169}, {a -> 633}, {a -> 1949}, {a -> 2413}}
One of the solutions will always be the golden ratio.
As well the well known identity with the Golden Ratio:
For instance,
Mod[1318 100, 89 29]=169 PowerMod[100, -1, 89 29]=2039 Mod[2039 PowerMod[1318 - 2039, -1, 89 29], 89 29]=169 Mod[1318 PowerMod[2039, -1, 89 29], 89 29]=169
According to Golden ratio:
This illustrates the unique property of the golden ratio among positive numbers, that
And this is true in modular arithmetic since: .
If we take the Golden Ratio, whose inverse is 1 less, and the square root of 2, whose inverse is half, then . Dropping into Mathematica we can see this holds for the modulus:
PowerMod[5, 1/2, 599 601 ]=67039 PowerMod[2, 1/2, 599 601]=16606 Mod[((1 + 67039) PowerMod[2, -1, 599 601] 16606) PowerMod[2, -1, 599 601] - PowerMod[((1 + 67039) PowerMod[2, -1, 599 601] 16606), -1, 599 601], 599 601]=8303 Mod[16606 PowerMod[2, -1, 599 601], 599 601]=8303
Quoting from the Wikipedia article Complex conjugate:
"In polar form, the conjugate of is . This can be shown using Euler's formula."
As such, since polar coordinates have an analogue in modular arithmetic, we can see that
This happens to be the case for this sum above.
I was able to get another modulus to work with this sum:
Now that we have a formula for taking the cube root of -1, we can apply this to prime modula instead of semiprime modula. In this case it is easy to find the square root of 3 mod p. Thus if is the modulus in the equation above instead of then the equation becomes:
Reducing this further, per the mod p, we get:
This above equation (on the right) is very close to an Eisenstein integer.
Dropping into Mathematica and trying the prime modulus we find the formula works as well:
Mod[(PowerMod[2, -1, 1153] (1 + PowerMod[-3, 1/2, 1153]))^3, 1153]== -1
If we have knowledge of as in , and the RSA plaintext can be expressed as , then my example below shows that you can derive .
Take where
Now the cipher text expands out, and certain terms cancel out:
And so, dividing by 3:
This equals also:
Divding by which is known, gives:
Thus, if is known, then the cube root of -1 can be known and the RSA (with E=3) ciphertext can be rewritten as . From here can be derived.
Or
According to Square root of 2:
"One-half of √2, also the reciprocal of √2"
and this is true in modular arithmetic:
However, we can note that so it is possible to get as in:
Thus if we take a modular square root of , we can then divide . At this point we have so it is easy to derive from this sum.
Since and the square root of , then .
So to derive the cube root of -1 from a cube:
For modula of 1 mod 4, based upon proofs in the wiki article, Eisenstein integer, there is only a cube root of -1 mod p*q when there is also a square root of -3 mod p*q.
If we try 3 mod 4 semiprimes with the formula: we find that the equation works for these semiprimes as well:
Try this Mathematica function
try888[p_, q_] := Module[{a1, a2, a3, a4, a5, a6, a7, a8, a9, a10}, a1 = NextPrime[p]; For[a2 = 1, a2 <= 10, a2++, a3 = NextPrime[q]; For[a4 = 1, a4 <= 10, a4++, If[Mod[a1, 4] == 3 && Mod[a3, 4] == 3, If[IntegerQ[PowerMod[-3, 1/2, a1 a3]], a6 = PowerMod[-3, 1/2, a1 a3]; a5 = Mod[PowerMod[2, -1, a1 a3] (1 + a6), a1 a3]; Print[{{a1, a3}, a6, a5, Mod[-(a5)^3, a1 a3]}]; a3 = NextPrime[a3]; ]; ]; a1 = NextPrime[a1]; ]; ]; ]
and get the following answers:
try888[72, 66] P, Q, (-3)^(1/2), (-1)^(1/3}, 1 {{79,67},126,2710,1} {{127,67},1817,909,1} {{199,67},611,306,1} {{271,67},1683,842,1} {{283,67},477,239,1} {{367,67},2002,13296,1} {{439,67},343,172,1} {{487,67},11666,22148,1} {{547,67},1013,507,1} {{607,67},6491,3246,1}
Although we have found a case above where the 3 mod 4 semiprime had the third root of -1, according to the DeMoivre's Theorum, this will usually not be the case in 3 mod 4 semiprimes, for two reasons:
If and due to the fact that , then
By empirical observation I also note that:
Also note that and that
This means that the following sequence of equations can be made to solve for and (See Mathematica below):
PowerMod[3,-1, 337 577]==129633 Reduce[(a + 1) (-3 x - 1) == 1 && (6 a - 3) (-2 x - 1) == 1 && a - 9 x == 5 && (3 a) (-3 x - 4 129633) == 1, {a, x}, Modulus -> 337 577] (a == 4253 && x == 472) || (a == 68877 && x == 180496) || (a == 125573 && x == 13952) || (a == 190197 && x == 193976) Mod[4253^3, 337 577]==-1 Also note that a == 9*x+5 ==9*472+5==4253
This above equation seems to hold for all 1 mod 4 semiprime modula. The general equation to solve for seems to be:
Solve[81 (x + 1) x == -21, {x}, Modulus -> 337 577] {{x -> 472}, {x -> 13952}, {x -> 180496}, {x -> 193976}}
(with Gauss's modular quadratic work, it is necessary to solve for the square root of (-3/81)).
and the general equation to solve for the cube root of -1 for the modulus (noting that ) seems to be:
Expand[(a + 1) (-3 (a - 5) 97225 - 1) - (6 a - 3) (-2 (a - 5) 97225 - 1)] 4375121 - 5250145 a + 875025 a^2 == 0 for modulus 337*577.
Since then
Some more formulas for where are
(Factoring will reveal both x and x^{-1} but we don't have the full sum of , only the residue).
You'll notice with the following three equations for x that x increments by (3*x+1) and the sum is (3*x+1)(3*x+2). That is an unusual pattern, and if the sum were known instead of the residue it would be trivial to figure out x.
The inverse definition is so the inverse is almost exactly
-1/3 of the sum.
The inverse so the inverse is almost exactly -1/9 of the sum.
The inverse so the inverse is almost exactly -1/27 of the sum.
These last three equations unwind the exponentiation to become division in the inverses.
These formulas are remarkable in that all 1 mod 4 semiprimes seem to have these equations equal 49 or 189.
The following Mathematica procedure will isolate x from 1/x or x^2. It will find
where (this is the guess for the value of x). It starts with the remarkable facts that and .
This is another way of solving
In fact if the guess, then the equation reduces to
If we use the following Mathematica command:
Factor[Expand[(a-7)(x+1)+7-(a+x)+8(x+a)]]
we get the equation
try888[a_, m_] := Module[{a1, a2, a3, a4, a5, a6, a7, a8, a9, a10}, a1 = Mod[-21 PowerMod[81, -1, m], m]; (* x^2+x *); a2 = a; (* x+a *); a3 = Mod[a (27 + a2 27) - 7, m]; (* (x+a)(7/x+27 a) *); a4 = Mod[a3 PowerMod[27 a2, -1, m], m]; (* 7 a /(x(27 a2)) + a *); a5 = Mod[a4 - a2, m]; (* (7 a/(x (27 a2)) - x *); a6 = Mod[a5 27 - 27, m]; (* ( 7a /(x( a2))-7/x *); a7 = Mod[a6 a1, m]; (* ( 7 a /((a2))-7))(x+1) *); (* x is isolated from 1/x or x^2 *); (* Solve for x *); a8 = Solve[(7 aa1 PowerMod[27 a, -1, m] 27 - 7) (x + 1) == a7 && x + aa1 == a, {x, aa1}, Modulus -> m]; Print[{a8}]; (* Verify (9 x +)^3 === -1 *); Print[{Mod[-(9 (x) + 5)^3, m] /. a8}]; ]
Some runthrus
try888[500, 337 577] {{{x->472,aa1->28},{x->13952,aa1->180997},{x->180496,aa1->14453},{x->193976,aa1->973}}} {{1,1,1,1}} p768 = 334780716989568987860441698482126908177047949837137685689124313\ 88982883793878002287614711652531743087737814467999489 q768 = 367460436667995904282446337996279526322791581643430876426760322\ 83815739666511279233373417143396810270092798736308917 In[7]:= p7 = NextPrime[p768, 1] Out[7]= 33478071698956898786044169848212690817704794983713768568912431\ 388982883793878002287614711652531743087737814467999749 In[8]:= q7 = NextPrime[q768, 1] Out[8]= 36746043666799590428244633799627952632279158164343087642676032\ 283815739666511279233373417143396810270092798736309087 try888[500, q7 ] {{{x->10859022257142929095284059240054363429972063896712078650637124749656480166883451577930018604815010297714820350940868,aa1->25887021409656661332960574559573589202307094267631008992038907534159259499627827655443398538581799972377978385368719},{x->25887021409656661332960574559573589202307094267631008992038907534159259499627827655443398538581799972377978385368218,aa1->10859022257142929095284059240054363429972063896712078650637124749656480166883451577930018604815010297714820350941369}}} {{1,1}} try888[500, p7 ] {{{x->9908924269737473060489962247148555494388931671897720886095195362894007181408094477524590786903090300437941505529569,aa1->23569147429219425725554207601064135323315863311816047682817236026088876612469907810090120865628652787299872962470680},{x->23569147429219425725554207601064135323315863311816047682817236026088876612469907810090120865628652787299872962470179,aa1->9908924269737473060489962247148555494388931671897720886095195362894007181408094477524590786903090300437941505530070}}} {{1,1}}
To isolate a where x+a is known try the following procedure
try888[a_, m_] := Module[{a1, a2, a3, a4, a5, a6, a7, a8, a9, a10, a11, a12, a13, a14, a15, a16, a17, a18, a19, a20}, a1 = Mod[-21 PowerMod[81, -1, m], m]; (*x^2+x*); a2 = a; (*x+a*); a3 = Mod[a (27 + a2 27) - 7, m]; (*(x+a)(7/x+27 a)*); a4 = Mod[a3 PowerMod[27 a2, -1, m], m]; (*7 a/(x(27 a2))+a*); a5 = Mod[a4 - a2, m]; (*(7 a/(x (27 a2))-x*); a6 = Mod[a5 27 - 27, m]; (*(7a/((a2))-7)/x*); a7 = Mod[a6 a1, m]; (* ( 7 a /((a2))-7))(x+1) *); a10 = Mod[7 PowerMod[a2, -1, m], m]; a11 = Mod[a2^2 a10, m]; a12 = Mod[a11 - 2 a7 , m]; (* (7/a2)(x^2+a^2)-2 (7/a2) a +14 (x+1)*) a14 = Mod[a10 (472^2 + 28^2) - (a10) 2 28 + 14 473, m]; a15 = Mod[(a12) - a10 (-21 PowerMod[81, -1, m] + a2) - 14 a2, m]; a16 = Mod[a10 (28 + 28^2) - 2 (a10 28) - 14 28, m]; (* a is isolated *) a17 = Solve[a10 (ab + ab^2) - 2 (a10 ab) - 14 ab == a15, {ab}, Modulus -> m]; (* (7/guess)(a+a^2)-2(7/guess)a-14 a *) Print[{a12, a14}]; (* answer for modulus 337*577 found *) Print[{a15, a16}]; (* solve for a for large prime modula *) Print[a17]; ] a runthrough try888[500, 337 577] {159088,159088} {74287,74287} {{ab->28},{ab->973},{ab->14453},{ab->180997}}
This procedure will find the guess (a) in the form of
If the guess is 7 then the equation reduces to
which is easier to work with.
A fascinating feature of X is that the sum of various powers of x always equals 0.
The Mathematica below shows this. Note the equations are always :
Table[{x, Mod[PowerMod[472, -(x + 2), 337 577] 7 + 27 (PowerMod[472, -(x + 1), 337 577] + PowerMod[472, -(x), 337 577]), 337 577]}, {x, 1, 10}] // Grid (Debug) Out[12]= \!\( TagBox[GridBox[{ {"1", "0"}, {"2", "0"}, {"3", "0"}, {"4", "0"}, {"5", "0"}, {"6", "0"}, {"7", "0"}, {"8", "0"}, {"9", "0"}, {"10", "0"} },
and
Table[{x, Mod[PowerMod[472, x, 337 577] 7 + 27 (PowerMod[472, (x + 1), 337 577] + PowerMod[472, (x + 2), 337 577]), 337 577]}, {x, 1, 10}] // Grid {"1", "0"}, {"2", "0"}, {"3", "0"}, {"4", "0"}, {"5", "0"}, {"6", "0"}, {"7", "0"}, {"8", "0"}, {"9", "0"}, {"10", "0"} },
If we take the realisable equation (the sum, not the residue)
(7 PowerMod[472, -1, 337 577] + 27 472)^2 37799914084
Since this sum is always the residue of (-27)^2, no matter what the p*q, then this sum is quickly realisable within 34 possible numbers.
This sum is also the following equation
1 4 27 337 577 472 - 4 27 27 (472^2 + 472) + (-7 PowerMod[472, -1, 337 577] + 27 472)^2 37799914084
Notice another low modulus
(7 PowerMod[1720, -1, 97 73] + 27 1720)^2 4057944804 9 4 27 1720 73 97 - 4 27 27 (1720^2 + 1720) + (-7 PowerMod[1720, -1, 97 73] + 27 1720)^2 4057944804
Notice how the multiplier in red is always low, my researches indicate it will always be between 1 and 27, no matter how large the number is
Another low modulus
(7 PowerMod[844, -1, 67 73] + 27 844)^2 859603761 6 4 27 844 73 67 - 4 27 27 (844^2 + 844) + (-7 PowerMod[844, -1, 67 73] + 27 844)^2 859603761
Now let's take a large number. Interestingly the large RSA numbers of around 600 bits to 750 bits don't have cube roots of -1 (no square roots of -3). Perhaps they were designed not to. However, we can try out primes adjacent to these numbers, which will have cube roots of -1 mod p*q.
let's take RSA-768 which was factored a few years ago. qq = \ 3674604366679959042824463379962795263227915816434308764267603228381573\ 9666511279233373417143396810270092798736308917 pp = 33478071698956898786044169848212690817704794983713768568912431388\ 982883793878002287614711652531743087737814467999489 now get x number Solve[81 (x^2 + x) == -21, {x}, Modulus -> NextPrime[qq, 1]] {{x -> 1085902225714292909528405924005436342997206389671207865063712474965\ 6480166883451577930018604815010297714820350940868}, } Solve[81 (x^2 + x) == -21, {x}, Modulus -> NextPrime[pp, 1]] {{x -> 9908924269737473060489962247148555494388931671897720886095195362894\ 007181408094477524590786903090300437941505529569}, {x -> } SS is the X number associated with the cube root of -1 ss = ChineseRemainder[{\ 1085902225714292909528405924005436342997206389671207865063712474965648\ 0166883451577930018604815010297714820350940868, 9908924269737473060489962247148555494388931671897720886095195362894\ 007181408094477524590786903090300437941505529569}, {NextPrime[qq, 1], NextPrime[pp, 1]}] 4375045719360799277111179417581904093171804109852946387918123\ 7779057042900790184181770653489280098352117595833705399124586219099662\ 8280520656291170940173641183140966763633985007962962933885697665175242\ 118352407342905904895300576268 create the modulus (it's not an RSA number but close to an actual RSA number mo = NextPrime[pp, 1] NextPrime[qq, 1] 1230186684530117755130494958384962720772853569595334792197322\ 4521517264005072636575187452021997864693899564749427893090894673831236\ 3127456739364769363131942239210345690548131094423078477949267226430938\ 3518878918414737015987902419163 create the (7/x+27x)^2 sum (not the residue) n1 = (7 PowerMod[ss, -1, mo] + 27 ss)^2 1513359278795203462908039994573225983635087960749583410587171\ 4438024587283531274752137527463757233272031971826952289102948803903822\ 3917106024833705284808208639947404748563975464966277329159186123596368\ 0716549697555137108153732037194637287966619458314178093014467221966369\ 8081590541083770294744287928011199456090725133365037403696451491888971\ 4120305912820533025681483173054808399518010039376732015590690386893522\ 370474704678084235130730749195439444679177307655709609 get the number in the above sum that is a multiple of 4 27 p q x n2 = n1 + 4 27 27 (ss^2 + ss) - (-7 PowerMod[ss, -1, mo] + 27 ss)^2 5812692827221597331851013445025210565593955729649624284393586\ 4660278304216343007746509463826095556032893247149222779236409443300877\ 3604164579791094387152090749860509534324980834525552731784172358572341\ 9685295413208802853376799827036569030424254321102258334756199509532351\ 8681734085031736277755372871097557994214597499542946255781936520491782\ 7849944397315644355891105464327580185274955215111850497926629058719544\ 474956898565206613925783812076356419828800001121578720 confirm that the multiplier of this above term is between 1 and 27, even though the number is a 750 bit number n3 = n2/(mo 4 27 ss) 10
Given
(7 PowerMod[472, -1, 337 577] + 27 472)^2 37799914084 37799914084/4 9449978521 (4 27 337 577 - 4 27 27 ) 450 9448909200
You can see that in the above sum the estimate of 450 is close to the answer of 472, around 5 percent.
My examinations of the four examples for (7/x+27 x)^2 yield a multiplier of (1/4, 1/3, and 3) in order to achieve an estimate of X around 95 percent correct. In other words around 16 possiblities (1/4, by 1/4 up to 3) fits all four of my examples.
The next example will have a multiplier of 3
6 4 27 844 73 67 - 4 27 27 (844^2 + 844) + (-7 PowerMod[844, -1, 67 73] + 27 844)^2 859603761 3 859603761 2578811283 (6 4 27 67 73 - 4 27 27) 844 2672485488 (6 4 27 67 73 - 4 27 27) 815 2580658380
Again an estimate of around 95 percent. If you split 337*577 into 20 equally distant numbers and your answer was 472, then the closest estimate would have been 9000, a lot further away from the answer than 450 we arrived at with our calculation. So the rough estimate is better than random.
Another small example
9 4 27 1720 73 97 - 4 27 27 (1720^2 + 1720) + (-7 PowerMod[1720, -1, 97 73] + 27 1720)^2 4057944804 (3 4 27 73 97 - 4 27 27) (1750) 4009824000
So the estimate again with 5 percent of the number The multiplier was 1/3 in this case
A big example follows. The multiplier is 3 in this case
xx = 15133592787952034629080399945732259836350879607495834105871714438\ 0245872835312747521375274637572332720319718269522891029488039038223917\ 1060248337052848082086399474047485639754649662773291591861235963680716\ 5496975551371081537320371946372879666194583141780930144672219663698081\ 5905410837702947442879280111994560907251333650374036964514918889714120\ 3059128205330256814831730548083995180100393767320155906903868935223704\ 74704678084235130730749195439444679177307655709609 mo = \ 1230186684530117755130494958384962720772853569595334792197322452151726\ 4005072636575187452021997864693899564749427893090894673831236312745673\ 9364769363131942239210345690548131094423078477949267226430938351887891\ 8414737015987902419163 1230186684530117755130494958384962720772853569595334792197322\ 4521517264005072636575187452021997864693899564749427893090894673831236\ 3127456739364769363131942239210345690548131094423078477949267226430938\ 3518878918414737015987902419163 Multiply the hidden sum by three 3 10 4 27 mo ss Out[49]= 1743807848166479199555304033507563169678186718894887285318075\ 9398083491264902902323952839147828666809867974144766833770922832990263\ 2081249373937328316145627224958152860297494250357665819535251707571702\ 5905588623962640856013039948110970709127276296330677500426859852859705\ 5604520225509520883326611861329267398264379249862883876734580956147534\ 8354983319194693306767331639298274055582486564533555149377988717615863\ 3424870695695619841777351436229069259486400003364736160 Now print the (7/x+27 x)^2 number In[44]:= xx = \ 1513359278795203462908039994573225983635087960749583410587171443802458\ 7283531274752137527463757233272031971826952289102948803903822391710602\ 4833705284808208639947404748563975464966277329159186123596368071654969\ 7555137108153732037194637287966619458314178093014467221966369808159054\ 1083770294744287928011199456090725133365037403696451491888971412030591\ 2820533025681483173054808399518010039376732015590690386893522370474704\ 678084235130730749195439444679177307655709609
It may be hard to see from the printout of the mathematica but the order of the two numbers is the same and the first three digits of both are 151 and 174, which is around 15 percent off. If the multiplier was 2.75 then the calculation would have been less than 1/15 off.
Thus (7/x+27 x)^2 can be used to give a rough estimation of the X number.
In[15]:= Reduce[ 7/x^3 + 27/x^2 + 34/x + 27 x == 7/x^2 + 27/x == -27, {x}, Modulus -> 337 577] Out[15]= x == 472 || x == 13952 || x == 180496 || x == 193976
Understanding that then . Multiplying (-27)^2-2*7*27 by get
construct:
Thus:
oh yea,
An example of how formulas for x, x^2 and x^3 can be found where 9*x+5 is the cube root of -1 mod p*q follows:
I have first of all determined that:
and that
Please also note that the integer value of both sums above is low. For the first sum it varies by the modulus but will always be from -50 to +50. It is 6 for the 1000000009*2400000061.
The second sum can also be treated as an integer. Simply take the
First, determine x for our testing purposes:
Solve[81 (x^2 + x) == -21, {x}, Modulus -> 1000000009 * 2400000061] {{x -> 495617883584492178}, {x -> 980012060696177200}, {x -> 1419988021903823348}, {x -> 1904382199015508370}} Now note, if we treat x^2 as y as x^3 as z we can get an Integer equation instead of a modular equation. Therefore, we don't have to factor the modulus. Solve[35 PowerMod[9, -1, 1000000009 2400000061] + 8 x1 - 12 y - 27 z == 6 1000000009 2400000061 && x1 + y == -18044445065474078202 , {x1, y, z}, Integers] {{x1 -> ConditionalExpression[6 + 27 C[1], C[1] \[Element] Integers], y -> ConditionalExpression[-18044445065474078208 - 27 C[1], C[1] \[Element] Integers], z -> ConditionalExpression[8177778059229631505 + 20 C[1], C[1] \[Element] Integers]}}
Note that just above we have created a fourth variable, C[1], which describes
x y=Mod[x^2, p*q] z=Mod[x^3,p*q]
So an answer for x, x^2, and x^3 is
Mod[(495617883584492178 - 6) PowerMod[27, -1, 1000000009 2400000061], 1000000009 2400000061]=551689569599425758 Mod[495617883584492178^2, 1000000009 2400000061] =659937711741434012 Mod[-18044445065474078208 - 27 551689569599425758, 1000000009 2400000061]=659937711741434012 Mod[495617883584492178^3, 1000000009 2400000061] =11568790418142273 Mod[8177778059229631505 + 20 551689569599425758, 1000000009 2400000061] = 11568790418142273
It's hard to go further than this except to say that .
The equations for C[1], for 551689569599425758 in our example, can be manipulated a bit.
If we set C[1] to be 'a', then we note that and that
Thus we can arrive at where . Some of the details of this equation may change with different modulus, in particular the
We can take this a bit further with the equation
Mod[(27 27 ( 551689569599425758)^2 + 13 27 ( 551689569599425758) + 36) - 27 551689569599425758, 1000000009 2400000061]= 659937711741434012 where Mod[495617883584492178^2, 1000000009 2400000061]=659937711741434012
So
If we take and expand out the square we can get an absolute sum that is enumerable. It will be between 0 and 1000 lets say, even for large numbers.
As such the following sum equals
(36 + 2 27 6 551689569599425758 + 27 27 1279989787935977699 - (-18044445065474078208 - 27 551689569599425758))/(1000000009 2400000061)=477 Solve[(36 + 2 27 6 x + 27 27 y - (-18044445065474078208 - 27 x)) == 477 (1000000009 2400000061), {x, y}, Integers] {{x -> ConditionalExpression[27 C[1], C[1] \[Element] Integers], y -> ConditionalExpression[1545618099224590101 - 13 C[1], C[1] \[Element] Integers]}} note that this C[1] for this equation is 1/27 of the first equation for the 9*x+5==cube root of -1 mod p*q
The important thing to note is that these sums are enumerable. Even though I would have to guess what multiple of the modulus these sums equal, the multiple is quite achievable as it will be below 1000 for most of the time.
However, the new number C[1] seems to have no quick way of being determined.
If we take the inverse definition of we come up with
As such
I haven't been able to go further with this equation, however.
Taking the Integer equations of the previous section it does seem we can solve as a modular (without factoring the modulus) by adding
Solve[35 PowerMod[9, -1, 1000000009 2400000061] + 8 x1 - 12 y - 27 z == 6 1000000009 2400000061 && x1 + y == -18044445065474078202 && (y + 2 z + x4) == (-18044445065474078202 )^2, {x1, y, z, x4}, Modulus -> 1000000009 2400000061] {{x1 -> C[1], y -> 1155555595325926190 + 2400000082600000548 C[1], z -> 1244444487274074359 + 1155555595325926191 C[1], x4 -> 2367078270767353079 + 88888891948148168 C[1]}}
We can now see that x1 is the x value, and y,z, and x4 are powers of x
Mod[(495617883584492178^2 - 1155555595325926190) PowerMod[ 2400000082600000548, -1, (1000000009 2400000061)], (1000000009 \ 2400000061)]= 495617883584492178 Mod[(495617883584492178^3 - 1244444487274074359) PowerMod[ 1155555595325926191, -1, (1000000009 2400000061)], (1000000009 \ 2400000061)]= 495617883584492178 Mod[(495617883584492178^4 - 2367078270767353079) PowerMod[ 88888891948148168, -1, (1000000009 2400000061)], (1000000009 \ 2400000061)]= 495617883584492178
This Solve command works for large modula as well. Take RSA768, the largest factored number to date, and you get.
RSA768 = 1230186684530117755130494958384962720772853569595334792197322\ 4521517264005072636575187452021997864693899564749427740638459251925573\ 2630345373154826850791702612214291346167042921431160222124047927473779\ 4080665351419597459856902143413 (Debug) In[9]:= Solve[ 35 PowerMod[9, -1, RSA768] + 8 x1 - 12 y - 27 z == 0 && x1 + y == -21 PowerMod[81, -1, RSA768] && (y + 2 z + x4) == (-21 PowerMod[81, -1, RSA768])^2, {x1, y, z, x4}, Modulus -> RSA768] (Debug) Out[9]= {{x1 -> C[1], y -> 113906174493529421771342125776385437108597552740308777055307634\ 4584931852321540423628467779814617101286996736058124133190671474590116\ 9476423440261745443676167797619569089541011243625946492967400692016611\ 85801251314442092460094577234 + 123018668453011775513049495838496272077285356959533479219732245215\ 1726400507263657518745202199786469389956474942774063845925192557326303\ 4537315482685079170261221429134616704292143116022212404792747377940806\ 65351419597459856902143412 C[1], z -> 911249395948235374170737006211083496868780421922470216442461075\ 6679454818572323389027742238516936810295973888464993065525371796720935\ 5811387522093963549409342380956552716328089949007571943739205536132894\ 864100105155367396807566179 + 113906174493529421771342125776385437108597552740308777055307634458\ 4931852321540423628467779814617101286996736058124133190671474590116947\ 6423440261745443676167797619569089541011243625946492967400692016611858\ 01251314442092460094577235 C[1], x4 -> 10259993198824576064737187032895162335115157343127072066611413\ 5927057565364666159639423468167005510752962076373828070071100482451969\ 0524691178026539441445201484585584889843101457203640810033211795666088\ 890321719702490062541833337716 + 182249879189647074834147401242216699373756084384494043288492215133\ 5890963714464677805548447703387362059194777692998613105074359344187116\ 2277504418792709881868476191310543265617989801514388747841107226578972\ 8200210310734793615132357 C[1]}}
I was able to get a further series of equations for a Mathematica Integer Solve command. These Integer values are achievable although they may take a million repetitions or so.
Solve[49 x4 + 140 x3 + 189 x2 + (540) x1 == 140 PowerMod[495617883584492178, -3, 1000000009 2400000061] + 49 PowerMod[495617883584492178, -4, 1000000009 2400000061] + 189 PowerMod[495617883584492178, -2, 1000000009 2400000061] + 540 PowerMod[495617883584492178, -1, 1000000009 2400000061] && 7 x1 + 27 x == 7 PowerMod[495617883584492178, -1, 1000000009 2400000061] + 27 495617883584492178 && 7 x2 + 27 x1 == 7 PowerMod[495617883584492178, -2, 1000000009 2400000061] + 27 PowerMod[495617883584492178, -1, 1000000009 2400000061] && x22 + x == 495617883584492178 + PowerMod[495617883584492178, 2, 1000000009 2400000061] && 7 x3 + 20 x2 == 7 PowerMod[495617883584492178, -3, 1000000009 2400000061] + 20 PowerMod[495617883584492178, -2, 1000000009 2400000061] , {x, x22, x4, x3, x2, x1}, Integers] {{x -> ConditionalExpression[1840 + 2401 C[1], C[1] \[Element] Integers], x22 -> ConditionalExpression[1155555595325924350 - 2401 C[1], C[1] \[Element] Integers], x4 -> ConditionalExpression[-52086299168729844913 + 255879 C[1], C[1] \[Element] Integers], x3 -> ConditionalExpression[21110204808175436792 - 102060 C[1], C[1] \[Element] Integers], x2 -> ConditionalExpression[-5828571629171402519 + 35721 C[1], C[1] \[Element] Integers], x1 -> ConditionalExpression[2400000082599993448 - 9261 C[1], C[1] \[Element] Integers]}}
Notice that 2401 is a bigger value than 189 in the other equations and 255879 is getting bigger for
Out sum (7/x+27 x)^2 can be rewritten as
(4 27 337 577 - 4 27 27 - 2 27 (7 PowerMod[472, -1, 337 577] + 27 472)) 472 - 27 27 472^2 + 49 PowerMod[472, -1, 337 577]^2 Out[13]= 37799914084
Then using the modulus, (4 27 337 577 - 4 27 27 -
2 27 (7 PowerMod[472, -1, 337 577] + 27 472)) (as (7 PowerMod[472, -1, 337 577] + 27 472) can be quessed) we have the following interesting residue
Mod[37799914084, (4 27 337 577 - 4 27 27 - 2 27 (7 PowerMod[472, -1, 337 577] + 27 472))] 4277284
which as the difference of two squares can be rewritten as
Mod[-(27 472 - 7 PowerMod[472, -1, 337 577]) PowerMod[(27 472 + 7 PowerMod[472, -1, 337 577]), 1, ((4 27 337 577 - 4 27 27 - 2 27 (7 PowerMod[472, -1, 337 577] + 27 472)))], ((4 27 337 577 - 4 27 27 - 2 27 (7 PowerMod[472, -1, 337 577] + 27 472)))] 4277284
However, (7 PowerMod[472,-1,337 577]+27 472) is always a large factor of the resulting modulus we are using.
The following equations can find
You actually have to make a correct number for (not a residue) for this to work.
Mod[2 ( 7 PowerMod[472, -1, 337 577] + 27 472), 27 + 7]= 20 Mod[(27 - 7) (- PowerMod[472, -1, 337 577] + 472), 27 + 7]= 20 thus -472^{-1}+472 mod 17 == 1 Mod[(- PowerMod[472, -1, 337 577] + 472), 17]= 1
Similarly, for the modulus of 47 and the sum , the following Mathematica is shown
Mod[2 (20 Mod[472^2, 337 577] + 27 Mod[472^3, 337 577]), 47]= 39 Mod[(-7 Mod[472^2, 337 577] + 7 Mod[472^3, 337 577])]= 39 Mod[(-7 Mod[472^2, 337 577] + 7 Mod[472^3, 337 577]) PowerMod[7, -1, 47], 47]= 19 Mod[(-Mod[472^2, 337 577] + Mod[472^3, 337 577]), 47]= 19
Dropping into Mathematica and getting the complex coefficients of mod p. In this case for and we get:
Cos(PI/24)=Mod[PowerMod[2 + PowerMod[2 + PowerMod[3, 1/2, 1153 ], 1/2, 1153 ], 1/2, 1153 ] PowerMod[2, -1, 1153 ], 1153 ]=198 Sin(PI/24)=Mod[PowerMod[2 - PowerMod[2 + PowerMod[3, 1/2, 1153 ], 1/2, 1153 ], 1/2, 1153 ] PowerMod[2, -1, 1153 ], 1153 ]=140 (-1)^{1/2} mod 1153=== 140 Mod[(140 140 - 198)^24, 1153]== -1 Mod[(140 140 - 198)^48, 1153]== 1
Please note that . It is just a coincidence here the both the
Take the following example for the modulus
Cos(PI/24)=Mod[PowerMod[2 + PowerMod[2 + PowerMod[3, 1/2, 337 ], 1/2, 337 ], 1/2, 337 ] PowerMod[2, -1, 337 ], 337 ]=185 Sin(PI/24)=Mod[PowerMod[2 - PowerMod[2 + PowerMod[3, 1/2, 337 ], 1/2, 337 ], 1/2, 337 ] PowerMod[2, -1, 337 ], 337 ]=216 (-1)^{1/2} mod 337=== 189 Mod[-148, 337] === 189 Mod[(216 148 - 185)^12, 337]==189 // 12th root of modular imaginary number found here. Mod[(216 148 - 185)^24, 337]== -1 Mod[(216 148 - 185)^48, 337]== 1
If we take the traditional image of polar coordinates with the imaginary number as the delta for the vertical component, we can imagine the two imaginary numbers of the modulus p*q to allow two vectors which one can multiply together. Since the two roots of -1 multiplied together equal the square root of 1, then we can establish a root of 1 instead of a root of -1.
Take the two square roots of -1 mod 113*257 to be 241 and 13123. Take 13077 to be the Cos[Pi/4] and Sin[Pi/4] then multiplying the two polar vectors for the quad roots of -1 should give us the quad root of 1. As in:
Now see that . We have found the quad root of 1.
Therefore, the Nth root of 1 can be found by multiplying the two different Nth roots for -1, which use different square roots of -1.
Simplifying the quad root of 1 to be:
This further simplifies to:
Taking the argument above to the cube root of 1 mod p*q we get the equation:
or
This above equation should work for 3 mod 4 semiprime modula if there is a . In this case the equation will be:
So if you know and one of the then you can derive the cube root of 1 mod p*q.
Please note that this equation doesn't seem to exist, or have an analogue, in continuous arithmetic.
Since the Jacobi Symbol is authoritative if it is 0 (nonquadratic number) then if the Jacobi Symbol for -3 is 0 for the p*q modulus, then this means there is no cube root of 1 for mod p*q.
Check out User:Endo999#The_Modular_Quaternion_Worked_Out_And_Demonstrated for the definition of a modular quaternion.
With the definition above and our definition of the inverse of a quaternion, we should be able to create . The math follows:
Mod[(1 + 3 118286 - 31296 (133263 + 55416)) PowerMod[ 4 , -1, 337 577], 337 577]=169639 PowerMod[169639, 3, 337 577]=1 the norm of the cube root of 1 is 1 as in: (1/16) + (3/16) + (3/16) + (9/16)=1 the extra sum of the norm equation, ie <math>(1*3-\sqrt{3}^{2}==0)</math> cancels out. PowerMod[105015, -1, 337 577]=169639
Thus, the cube root of 1 mod p*q is a unit quaternion as well, since its norm = 1.
So the division method is a good way of taking the higher roots of -1 or 1 mod p.
Taking roots by the De Moivre's formula of -1 is a sensible thing to do in modular arithmetic when:
It is also clear that at least for 1 mod 4 prime and semiprime modula that there are universal formulas for the roots, including higher roots, of -1, where a complex modular number is constructed and where the coefficients of the complex number for are of the form: and . This is exactly like that of continuous numbers. The Wikipedia math article, Root_of_unity#Algebraic_expression, has relevant material on just which roots of unity need only modular square roots to be taken:
My examples, shown in this section and just above, show that this above statement is true for modular arithmetic as well.
I also conclude it should be now possible to take a Discrete Fourier transform, using the nth roots of unity found by now. This modular discrete Fourier Transform should be capable of convolution and many of the other properties of the continuous Discrete Fourier Transform.
Initial tests with Chebyshev Polynomials indicate that they successfully change modular trigonmetric values in p*q modula. For instance:
Thus:
Since I'm pretty sure that Chebyshev polynomials work in modular arthmetic.
If we could invert the Chebyshev polynomials we could quickly establish Cos[PI/4] since Cos[PI]=-1 but we do not seem to be able to do this.
See here for some work using the Chebyshev polynomials.
Chebyshev Polynomials can also be used to quickly generate answers to Pell's Equation, which work in modular arithmetic:
The Chebyshev polynomials can also be defined as the solutions to the Pell equation
in a ring R[x].[20] Thus, they can be generated by the standard technique for Pell equations of taking powers of a fundamental solution:
See here for an example in mathematica where and so
create first root with x=2 and T_2 Mod[2 2 2 - 1, 89 29]= 7 create second root with x=2 and U_1 Mod[2 2, 89 29]= 4 show Pell's equation Mod[7 7 - (4 - 1) 4 4, 89 29]= 1
Some of the math in this section builds on matter in the Blum integer Wikipedia article.
If has a modular square root where are both 3 mod 4 primes, then Will Not have a modular square root.
This happens since and for the equation must be . But it is well known that modula of 3 mod 4 semiprimes (where both p and q are 3 mod 4 primes) cannot have . Therefore, the arithmetic inverse of a quadratic number in a 3 mod 4 semiprime modulus must be a nonquadratic number.
Therefore, the negative of an actual square in a 3 mod 4 semiprime modulus has to be a nonquadratic. So it is possible to find some nonquadratics with such a modulus. This corrects, sometimes, the Jacoby Symbol, since it will usually report that when it cannot be.
A quick look at the Jacobi Symbol of arithmetic inverses in modula of 3 mod 4 semiprimes shows that arithmetic inverses always share the same Jacobi Symbol, and it looks as if when both Jacobi Symbols for and always equal 1 that one of the numbers is a quadratic while its arithmetic inverse is a nonquadratic. Note the following Mathematica equations of the modulus, , for the numbers 1 to 30 and of their arithmetic inverses:
Table[{x, 19 79 - x, JacobiSymbol[x, 19 79], JacobiSymbol[19 79 - x, 19 79], IntegerQ[PowerMod[x, 1/2, 19 79]], IntegerQ[PowerMod[19 79 - x, 1/2, 19 79]]}, {x, 1, 30}]//Grid x -x J[x} J[-x} SR[x] SR[-x] 1 1500 1 1 True False 2 1499 -1 -1 False False 3 1498 1 1 False True 4 1497 1 1 True False 5 1496 1 1 True False 6 1495 -1 -1 False False 7 1494 -1 -1 False False 8 1493 -1 -1 False False 9 1492 1 1 True False 10 1491 -1 -1 False False 11 1490 1 1 True False 12 1489 1 1 False True 13 1488 -1 -1 False False 14 1487 1 1 False True 15 1486 1 1 False True 16 1485 1 1 True False 17 1484 -1 -1 False False 18 1483 -1 -1 False False 19 1482 0 0 True False 20 1481 1 1 True False 21 1480 -1 -1 False False 22 1479 -1 -1 False False 23 1478 1 1 True False 24 1477 -1 -1 False False 25 1476 1 1 True False 26 1475 1 1 True False 27 1474 1 1 False True 28 1473 -1 -1 False False 29 1472 1 1 False True 30 1471 -1 -1 False False
Since 1 is always a quadratic number, then this means that -1 must be a nonquadratic number. Since and the Jacobi symbol is multiplicative, this means that if -1 has 1 as a Jacobi Symbol (that the Jacobi symbol says it is quadratic), then . Thus, even though is quadratic and is nonquadratic. There is no way of telling which arithmetic inverse is and which is . Basically, for 3 mod 4 semiprimes the Jacobi Symbol can only say that either or is quadratic, it cannot say which one is quadratic.
Considering that 3 mod 4 semiprimes are known as Blum Integers, then Blum integer says the following on this matter:
Now if you have a Jacoby=1 arithmetic inverse pair and you square one of the numbers, then the resulting square will have to be a quadratic, and then that squares arithmetic inverse has to be a nonquadratic.
Seeing that a quadratic number, a square, always has four square roots, , , , it follows therefore that there can, at most, only be four quad roots for a square of a RSA semiprime. Since the square root of is and there cannot be quad roots of 1 for 3 mod 4 semiprimes (see below), and since arithmetic inverses of quadratic numbers cannot both have square roots in 3 mod 4 semiprimes, then, if the only square root that can have a square root is . This number will have four square roots which will be: , , , and
This is so for octal roots and for all roots that are powers of 2. There will only be four ultimate roots.
There can be no quad roots of 1 per an RSA semiprime. In an earlier section, I have argued that there are NO quad roots of one for 3 mod 4 semiprimes, since the definition of a quad root of one for modulus is . Please note once again that there are no for 3 mod 4 semiprimes.
Since there can be at least four square roots of , , , , .
And since there are two for a 1 mod 4 semiprime, and there are and to consider, A simple Mathematica function shows that there can be at least 16 quad roots of a 1 mod 4 semiprime. The quad roots of 16 mod p*q can be defined as:
is important for square roots, and is important for quad roots.
Given: , , , and then:
Since this is so the quad root of 1 mod p*q (for 1 mod 4 semiprime) is:
and
Thus:
In the examples above all the quad roots of 1 are 1 mod 73 or p. In the example below it is shown how to get a quad root of 1 that is 1 mod 13 or q.
or
As well a definitions of a square root of -1 mod p*q in terms of two different quad roots of 1 follows:
Note that the first quad root will be 1 mod p and the second quad root will be 1 mod q. An example:
and
The other square root of -1 mod 73*13, 684, can be defined in terms of quad roots of 1 by:
and
If we take then , which has some interesting properties in that .
Also, and
The same approach works for the other where . Again, . And and
There do seem to be some special properties of the two
If we take the modulus, , with ,,and (and the quad roots to be ,, and ), then the sums of quad roots of one that come 1 off these numbers follows:
The sums for the will both be or .
The sums for the will have one be while the other is
Since the above equivalents are true, the Product To Sum Theorum, shown in an earlier section, applies, and the product can be 1 off the sum of the two items.
Given that and , and and , are inverse quad roots of 1 for modulus , and , and that and , then the following applies:
Another table showing and as the coefficients
We can see that as in the following table:
The sum of all numbers mod p*q is 0. And interestingly the sum of all the numbers for the field up to is its inverse
These sums can be worked out by the well known equation:
With knowledge of the tables above lets look at:
Knowing that we can multiply the above term by to get:
Noting that and the Product To Sum Rule, described above, can be applied giving:
Subtracting out 2, adding 569 and combining terms gives us:
Adding (which is ) we get the powers of p and q multiplied by the quad powers of 1:
By symmetry and noting that the other quad roots of 1 per 89*29 are 800 and 233, that
These two sums are equivalent to:
and
which have been studied extensively in another section of this blog.
The Imaginary unit wiki article has some interesting equations that deal with I. These also apply to the modular as well:
Using the radical sign for the principal square root gives:
The following equation from the same wiki article also applies to the modular imaginary number:
The three cube roots of i are:
Similar to all of the roots of 1, all of the roots of i are the vertices of regular polygons inscribed within the unit circle in the complex plane.
Also, from my own observation:
An example:
get i number for 41*401 modulus PowerMod[-1, 1/2, 41 401]=5995 show the equation above to work for this modulus Mod[(2 + 4 5995) PowerMod[3 + 5995, -1, 41 401], 41 401]=5996
Interestingly, This also works for
A way to determine the is to subtract successive squares from . If the resulting sum is also a square then . In numeric terms . This works since . You can also create sum of square for any fourth multiple of :
Actually, if both and are quadratic then .
This is so since given the two numbers, and , That the fraction of these two sums will necessarily be: . Please note that .
Finally, you can factor the sum of squares by using the square root of -1 to multiply one of the roots.
This means that the a factorisation of 2 mod p*q is:
or, in our case of modulus 949:
You can also factor the minus of squares by using the square root of 1 like this:
I will now show that knowledge of one of the square roots of negative 1 mod p*q is tantamount to factoring p*q, if you can take a modular square root
Since
and
and
and
then the sum of these two equations equals:
If you raise this above sum to the fourth power you get
Surprisingly, sometimes, you can use the Product Of Powers To Sum Of Powers theorum (described in an earlier section) to simplify:
Numerically, as and and and and then:
Understanding that have and , and that the quad root of 1 () has and , it is sometimes possible to use a in conjunction with a to decompose products into sums. In the equation above and have the right properties and we can change the equation to be:
Another simplification is to notice that , or , is equal to . Working on this in the square noted above we have:
This is equivalent to:
Multiplying through and substituting for leads to:
Finally,
We know the two terms and (remember we know one of the for this exercise but not the second).
Therefore, we know one of the square roots of the complicated equation we started with:
A very complicated endeavor, but one that, nonetheless, yields one of the square roots of in this case since
Symmetry is important in modular math algebraic equations. In this case to find the square root of the other equation:
or
and and
Remember that
and
so the two equations are roughly symmetric to each other. Also, remember that the signs in these above two equations change depending on the primes used.
Having found two roots and mod , let's see what roots we need to apply the two equations three sections previous:
As numbers we want these roots:
We can see that so we do have one of the square roots we want, however,
so we don't have the second square root we want, but its reflection. So we are close to factoring but, unfortunately, no ecigarette.
Understanding that is the inverse of , and that inverses are often equivalent when it comes to the Product To Sum theorum, we can therefore unwind:
As such, when we substract our two derived roots,
and this , after the unwinding mentioned above is equivalent to:
or
Thus we have removed powers of from the equations, however, it still does not solve for either or
We can further reduce the equation by applying the Product To Sum rule to and . The expansion of this algebra is shown below:
This contracts to:
or
Thus, we have removed both and from the equation and only the quad roots of 1 and the square root of -1 remain.
(It should be noted that where )
After some work with Mathematica, it seems there are two cases for the roots created in this section. There is one where 1) and the other 2) is when . For the second case you need to multiply the formula for both the two roots by (this is explained in the section showing the formulas for the numbers )
The P and Q primes need to be
When these conditions are observed, then will be case 2 () and the rest case 1 ().
Due to sign issues between
there are 8 possible computations you can make to get the root of this section. Of these 8, 2 will be correct, the other 6 incorrect.
Checking with a second modulus, with and as and
, I had to multiply the equations by one of the square roots of -1: :
The above numbers are the intended numbers. The numbers we get from our equations are:
The effect of multiplying by helps get the correct square we are after instead of the negative number to the square we want.
This set of equations also works with the modulus , however, the set of equations seems to require a square root of 1 mod p*q, , that is not . In other words, besides , there needs to be another square root of 1.
Since Imaginary Modular Numbers are one off the sum of two quad roots of one (see Definition Of Quad Roots), and quad roots are always it follows that we can use the Product To Sum Theorum to further decompose the two equations we have made in the previous section.
Taking and understanding that , and that both and are both quad roots of 1 for the modulus , then we can decompose the sum of in the following steps:
Note that we have created an equation that can now be compared with the other equation of the two, which shall be decomposed in the following steps (remembering that , , , and ):
At this point we can add both sums:
I checked this math for the modulus , and the result was similar. The two equations in question were:
The sum of and this equation was equivalent to
A quite similar result
Using the Product To Sum theorum I was able to come up with the two following definitions where and and :
Mod[-2493 2^(88 + 28) + 2493 + 2^28 , 89 29]== 2^88
and
Mod[2493 2^(88 + 28) - 2493 + 2^88 , 89 29]== 2^28
is derviable.
Using the Product To Sum Theorum I was able to do the following math steps:
Mod[2^88 - 2^28 - 1, 89 29]===Mod[(2^28) (2^88 - 2), 89 29]==Mod[2^(88 + 28) - 2 2^28, 89 29]==826
Thus:
Mod[2493 (2^88 - 2^28), 89 29]===Mod[2493 (2^(88 + 28) - 2 2^28 + 1), 89 29]===2073
Thus:
2071===Mod[2493 2^(88 + 28) - 2493 - 2 2^28 , 89 29]
Trying the modulus for this effect, I found I had to minus the sums in order to cancel out.
(For previous steps (on other modulus) see Original Equations Defined for how to originally define the two equations we add or subtract from each other. And then see Actual Algebraic Proof for the actual resolution of the equations. Consult Product To Sum Method for an algebraic method on P*Q modulus used extensively in the proof)
With:
I found that, minusing the two equations from the section above, that I was able to derive:
Since then it seems we have a new definition whereby:
We can see on examination of the modulus, 73*13=949, that this equation, subject to sign changes holds:
or
Thus, it seems that(noting possible sign changes):
This is a definition of the sum of the two square roots of -1 mod p*q per quad roots of 1. Please note that the quad roots need to be inverses of each other.
Trying the modulus we can see that this sums of inverse quad roots of 1 equaling sums of square roots of -1 holds, where 945 and 568 are square roots of -1 for the modulus 89*29, and -233, 144 are inverse quad roots of 1, and 713 and -800 are inverse quad roots of 1 per the modulus given.
You can't use the Product To Sum theorum to unwind the multiplication of
since
However, multiplied by such that , the multiplication can be unwound as in:
and
(Remember for this exercise we know but not )
So for modula of the Product To Sum theorum described here is almost another rule of algebra!
By manipulating these two sums, described just above, and multiplying by () I was able to establish that, for this modulus of that:
or
or
and
If we take the term we shall call :
we can see that any cancels out the .
In the case of though:
It's sorta like a multiplier took the power to the fourth power, , but this multiplier is not !
It implodes powers as well. If you take the inverse of , then the following equation holds:
To give an example:
and
This works for all and odd prime combinations.
Actually, the above explanation is an insight into a family of equations that are similar multipliers. I have been able to make half the and combinations work to create an that works for the equation:
and I have been able to make around of the and combinations for where:
You often have to use the to construct . There are around 8 cases. Consult [21] on how to do this.
As well, it is possible to construct an equation with all the unknowns on the left side being powers of , and a known number on the right:
An example:
or
Usually, equations always have unknowns of powers of and , not just powers of one of the primes.
If we take the equation just above, with its definition of then
If we expand out the polynomial shown on the right side of the equation above, then we can see that
This means that
This is a type of Product To Sum decomposition from multiplication to subtraction.
To emphasise that this is a family of equations observe the following:
and
Try the primes and for this exercise. The exact equation is determined by the prime states of the primes. Look at the paper[21] reference below for an explanation of prime states.
Take and to produce
This is a definition of the constant, , only in terms of powers of and the constant
The equations, for other prime pairs, will be slightly different depending on the prime states now.
As well, take:
or
and (in the case of for and )
which makes:
and
With knowledge that there are squareless numbers (numbers whose square mod p*q is itself), and taking the number , the following can be asserted:
This works because all sum squares are of the form:
If , then , and if , then the equation for the sum squared is:
You can see that , in other words they cancel out.
This also works, for the same reason for squares of , so that
Since both and equal it follows that, after taking the modular (or natural) square root of , we can determine P or Q via
Theoretically, this procedure should reveal the factorisation of 1 p*q combination every attempts, however, my trials with Mathematica show that the factorisation is revealed, because the square is a natural square, once every .
The Following mathematica output shows that taking the square root of does work.
{{p,q}, TYPEOFSQUARE, SQUARE,ROOT,GCD[ROOT-(-2)^{-1}] {{103,31},ModularSquare,2395,1287,103,1} {{103,43},ModularSquare,3322,1699,103,1} {{103,47},ModularSquare,3631,258,47,1} {{103,59},ModularSquare,4558,2626,103,1} {{103,67},ModularSquare,5176,2111,103,1} {{103,71},ModularSquare,5485,1597,71,1} {{107,31},ModularSquare,2488,481,107,1} {{107,43},ModularSquare,3451,2086,107,1} {{107,47},ModularSquare,3772,588,107,1} {{107,59},ModularSquare,4735,1445,59,1} {{107,67},ModularSquare,5377,3049,107,1} {{107,71},ModularSquare,5698,3585,71,1} {{127,31},ModularSquare,2953,698,127,1} ---- {{127,43},Natural Square,4096,64,43,1} ---- {{127,47},ModularSquare,4477,1715,47,1} {{127,59},ModularSquare,5620,2095,127,1} {{127,67},ModularSquare,6382,1842,67,1} {{127,71},ModularSquare,6763,2095,127,1} {{131,31},ModularSquare,3046,852,31,1} ---- {{131,43},Natural Square,4225,65,131,1} ---- {{131,47},ModularSquare,4618,1245,47,1} {{131,59},ModularSquare,5797,2685,131,1} {{131,67},ModularSquare,6583,1507,67,1} {{131,71},ModularSquare,6976,2947,131,1} {24 attempts, 2 natural squares}
This section shows that you only need one modular square root to factor p*q if the base is , and not two as with most bases. Thus the factorisation problem is equivalent to the modular square root problem.
By the same algebra, as shown above, I was able to discern that:
and taking the base of I was able to derive the cube to:
Thus, it is possible to derive:
but I wasn't able to get further than this.
Using the well known subtraction of cubes formula:
and given
then the SQUARELESS number (or ) can be derived but unfortunately we don't have that term.
It is also possible to derive:
but this doesn't get any further either.
Using the unique algebraic properties of the squareless number, you can solve for
Solve[(2 x a) == -(x^2 - 1), {a, x}, Modulus -> 101 73]
to get squares where
Thus a subtraction of squares can be done as in:
Likewise for cubes, you can solve for
Solve[3 x (a x + a^2) == -(x^3 - 1), {a, x}, Modulus -> 101 73]
Thus a subtraction of cubes can be done as in:
Unfortunately, for all these new equations above, it was not possible to derive p or q from them.
Quoting the equation from p 89 of "Ramanujan" by Hardy:
Ramanujan went a good deal further. He proved congruences with modulli being:
and put forward a conjecture that if
- then
Apparently, the conjecture has been shown to be incorrect at times, but it usually is good enough to work with.
The P function is the permutation function, or basically, the Factorial function.
This section will be devoted to topics found from a gleeming of Dickson's 1921 History of the Theory of Numbers.
The three volume work seems to have math that has dropped out of the Math corpus.
Quite a few of previous mathematicians worked on this above equation. I couldn't get some of their work to work, but for several of them I was able to get them to work, that of(if z is the modulus then the square root of -a/b mod z can be found easily)
S. Realis(Theory of Numbers vol ii p 627)
I was able quickly to make the above math work on Mathematica, but I was unable to set the modulus of the modulus which would be
On Theory Of Numbers, vol ii, p632, the following equations will create
if
Fermat method (Theory of Numbers, vol ii, p 631) works and I was able to set the modulus to be what I wanted. (The modulus was z so I proceeded with modular equations and cancelled out the z's simplying the equation). I was only able to get one of the square roots. The other one (for p*q modula never appeared)
A. Desboves math at p631 vol ii of "Theory Of Numbers" works.
==
It's quite good in that it doesn't require a working earlier case.
I'm not a professional mathematician but I just read Dickson's "History of Numbers" [24] where it says on page 215-216 that
After reading the Dickson text a couple of times on p215,216 I came across this formula for the square root of .
Noting that and noting that then
So Tonelli's math does seem to take modular square roots of prime powers! The Tonelli–Shanks algorithm article explicitly says the algorithm only takes the modular square root of primes:
Here's another equation: and
On page 215-216 of the Dickson book, the equation is given of Tonelli's:
Using and using the modulus of the math follows (in mathematica):
Mod[1115^2, 23 23 23]=2191 Mod[1115^2, 23]=6 PowerMod[6, 1/2, 23]=11 Mod[11^(23 23) 2191^((23 23 23 - 2 23 23 + 1)/2), 23 23 23] =1115
Thus Tonelli's work can work for a 3 mod 4 prime power.
This math proves that, under some circumstances, that Tonelli's work is greater than Shanks. Those old text books (in the case Dickson's "History of Numbers" volume 1) are sometimes worth pouring through! Shanks did refer to his algorithm as the RESSOL algorithm and cryptographers are famous for codes. It should be noted that RESSOL is LOSER backwards. Maybe, Shank was aware of Tonelli's powers of prime modular square root method, but did not publically reveal it. We will never know because Mr. Daniel Shanks is dead.
According to Dickson's "History Of Numbers" vol 1 p 218 [27], the following formula of Cipolla, Cipolla's algorithm, will find square roots of powers of prime modula and not just prime modula (as the wiki article states):
Taking the example in the wiki article we can see that this formula above does indeed take square roots of prime power modula.
Dropping into Mathematica
PowerMod[10, 1/2, 13 13 13]=1046 Create 2^(-1)*q^(t) via Mod[PowerMod[2, -1, 13 13 13] PowerMod[10, (13 13 13 - 2 13 13 + 1)/2, 13 13 13], 13 13 13]=1086 Create the (k+ sqrt{k^{2}-q})^{s} and (k- sqrt{k^{2}-q})^{s} via the following Mathematica procedure try999[m_, r_, i_, p_, i1_] := Module[{a1, a2, a3, a4, a5, a6, a7, a8, a9, a10}, a2 = r; a3 = i; For[a1 = 2, a1 <= p , a1++, a4 = a2; a5 = a3; a2 = Mod[a4 r + a5 i i1, m]; a3 = Mod[(a4 i + a3 r), m]; (*Print[{a2,a3,a1}];*) ]; Return[{a2, a3}]; ] (k+sqrt{k^{2}-q})^{s}= 1540 and (k-\sqrt{k^{2}-q})^{s}= 1540 via the following function calls try999[13 13 13, 2, 1, 13 13 7, -6]=1540 try999[13 13 13, 2, -1, 13 13 7, -6]=1540 and Mod[1086 (2 1540), 13 13 13]=1046 which is the answer.
Cipolla means onion in Italian by the way.
Says p207 of Dickson's "Theory of Numbers" vol 1:
The congruence is reduced (art. 152 [of Gauss' work]) to . For each root , it remains to solve .
Quoting from [28]
Knowing that then
or
For the purposes of this example we will say that since andSince we can multiply by which is known giving
and since
then the sum above equals , so add 1 and get .
Dividing by , which is known, gives us .
is a multiple of , one of the factors. This can quickly be derived via the Greatest Common Divisor function.
The equation, , shown above, is easily turned into a quadratic equation:
Let's see how it fares with Gauss's quadratic construction (as shown by Dickson):(a=1,b=1,c=569):
and
and
We can see here that this matches well with the answer we have from the blockquote above. Also, from the blockquote above, we can see that with knowledge of one of the square roots of -1 (568) is enough to factor the modulus.
As well, with knowledge of one of the square roots of -1 and the good fortune of having
that we don't have to take the modular square root and thus the equation is quickly solvable!
When one considers that:
If this new sum results in a natural square via
then the resulting value will be the same as the original equation.
Likewise, when you add or subtract:
you may end up with a natural square in the
Using this method, theoretically, all quadratic equations could be turned into natural squares with the X values the same as the original equation.
Looking at the Quadratic_equation#Alternative_quadratic_formula for the modular quadratic equation, one can see here that it is[29]:
The general quadratic equation can be written in the standard form
where u and v are complex numbers. Then the solutions can be written in the particularly symmetric form
or equivalently
Now if:
then could be worked out since
the root could be taken of 2*U and this would be the answer to the quadratic equation. An example showing this to be true for modular numbers follows:
Using the Pythagorean Triple 3 4 5, construct a modular complex number where 568 is the square root of -1 mod 89*29 Mod[4 + 3 568, 89 29]= 1708 Just to be quick use Mathematica to solve this equation which is the alternative quadratic equation mentioned above Solve[x^2 - 4 1708 x + 4 1708^2 == 0, {x}, Modulus -> 89 29] {{x -> 835}} Now take the square root of 2*1708, (see previous sections pertaining to taking modular square roots using the pythagorean parameters) Mod[(3 + 568), 89 29]= 571 Now square this number, and viola, we have the correct answer Mod[571^2, 89 29]= 835
In this section, I will quickly show that Pythagorean Triples, fed into Gauss' Quadratic Equation solution, can provide natural squares in the half the time. However, the root of the natural square given is NOT the solution root. The solution root is the .
This method rests upon the observation that
or
As such, is an equation that does not contain or any unknown. See [30] for a citation on the use of Pythagorean Triples and squares and roots using instead of as is normally the case in this math blog. See here for an explanation of the Pythagorean Triples method mentioned in this post.
The following Mathematica procedure shows that Pythagorean Triples fed into Gauss' method of solving a modular quadratic equation can provide natural squares for .
(* type: 1 SQUARE ROOT OF 1 sought *) (* type: 2 SQUARE ROOT OF -1 sought *) (* type: 3 CUBE ROOT OF -1 sought *) gaussian[p_, q_, lp3_, type_] := Module[{lp1, lp2, py1, py2, py3, r1, r2, mult, minus, square, root, ans1, ans3, ans2, ans4, cnt1, cnt2, sqrt, stoploop}, cnt1 = 0; cnt2 = 0; stoploop = 10; sqrt = Mod[p PowerMod[p, -1, q], p q]; If[Mod[(2 sqrt + 1), p q] == 1, sqrt = 2 sqrt + 1;, sqrt = 2 sqrt - 1; ]; For[lp1 = 1, lp1 < lp3, lp1++, For[lp2 = 1, lp2 < lp3, lp2++, If[lp1 == lp2, Continue[]]; cnt1++; py1 = 2 lp1 lp2; py2 = lp1^2 - lp2^2; If[py2 < 0, Continue[];]; py3 = lp1^2 + lp2^2; If[py1^2 + py2^2 == py3^2, r1 = (py3 + py1)^(1/2); r2 = (py3 - py1)^(1/2); If[r1 == IntegerPart[r1] && r2 == IntegerPart[r2], If[type == 1, mult = Mod[2 py2 PowerMod[r2, -1, p q], p q]; minus = Mod[-(2 py1 + 2 r2 r2 - mult r1), p q]; ]; If[type == 2, mult = Mod[2 py2 PowerMod[r2, -1, p q], p q]; minus = Mod[-(2 py1 - mult r1), p q]; ]; If[type == 3, mult = Mod[(2 py2 + r2^2 ) PowerMod[r2, -1, p q], p q]; minus = Mod[-(2 py1 - mult r1), p q]; ]; square = mult^2 - 4 minus; root = square^(1/2); If[root > 0 && root == IntegerPart[root], Print[{{"Pythagorean Triple ", py1, py2, py3}, {"Root Coefficients ", r1, r2}, {"mult", mult, "minus", minus, "square", square}, {"(b^2-4ac)^(1/2) ", root}, {lp1, lp2}}]; Print["following is x in 2*x-b==root"]; Print[{ans2 = Solve[2 x - mult == root, {x}, Modulus -> p q], ans1 = Solve[2 x - mult == root sqrt, {x}, Modulus -> p q] }]; ans3 = Mod[(x - (r1)) PowerMod[r2, -1, p q], p q] /. ans1; ans4 = Mod[(x - (r1)) PowerMod[r2, -1, p q], p q] /. ans2; Print[{"2 x-b=root", ans4, "2 x-b=root*(1)^(1/2)", ans3}]; cnt2++; If[cnt2 > stoploop, Exit[];]; ]; ]; ]; ]; ]; Print[{"success: ", cnt2, "attempts: ", cnt1}]; ]
gaussian[337, 577,5,1] The Output for this procedure is:
{{Pythagorean Triple ,4,3,5},{Root Coefficients ,3,1},{mult,6,minus,8,square,4},{(b^2-4ac)^(1/2) ,2}} following is x in 2*x-b==root {{{x->4}},{{x->118289}}} {2 x-b=root,{1},2 x-b=root*(1)^(1/2),{118286}} {{Pythagorean Triple ,6,8,10},{Root Coefficients ,4,2},{mult,8,minus,12,square,16},{(b^2-4ac)^(1/2) ,4}} following is x in 2*x-b==root {{{x->6}},{{x->42127}}} {2 x-b=root,{1},2 x-b=root*(1)^(1/2),{118286}} {{Pythagorean Triple ,12,5,13},{Root Coefficients ,5,1},{mult,10,minus,24,square,4},{(b^2-4ac)^(1/2) ,2}} following is x in 2*x-b==root {{{x->6}},{{x->118291}}} {2 x-b=root,{1},2 x-b=root*(1)^(1/2),{118286}} {{Pythagorean Triple ,8,15,17},{Root Coefficients ,5,3},{mult,10,minus,16,square,36},{(b^2-4ac)^(1/2) ,6}} following is x in 2*x-b==root {{{x->8}},{{x->160414}}} {2 x-b=root,{1},2 x-b=root*(1)^(1/2),{118286}} {{Pythagorean Triple ,16,12,20},{Root Coefficients ,6,2},{mult,12,minus,32,square,16},{(b^2-4ac)^(1/2) ,4}} following is x in 2*x-b==root {{{x->8}},{{x->42129}}} {2 x-b=root,{1},2 x-b=root*(1)^(1/2),{118286}} {{Pythagorean Triple ,24,7,25},{Root Coefficients ,7,1},{mult,14,minus,48,square,4},{(b^2-4ac)^(1/2) ,2}} following is x in 2*x-b==root {{{x->8}},{{x->118293}}} {2 x-b=root,{1},2 x-b=root*(1)^(1/2),{118286}} {success: ,6,attempts: ,12}
The answer to Gauss equation, the is given by the root obtained by the Pythagorean Triples method multiplied by the .
Thus part of the root is obtained by this method, but not the whole root needed.
Two other anchors, besides , for the square and root equations are possible:
Feeding in the following parameters will return natural squares for when the anchor is . The actual square root of -1 will be found when the square is found. The equation that has to be solved in order to find the first natural square is:
There seems to be no easy way to solve this equation. The output for the procedure for the first 10 natural squares follows:
{{Pythagorean Triple ,57618,78800,97618},{Root Coefficients ,394,200},{mult,788,minus,787,square,617796},{(b^2-4ac)^(1/2) ,786},{297,97}} following is x in 2*x-b==root {{{x->787}},{{x->13481}}} {2 x-b=root,{139033},2 x-b=root*(1)^(1/2),{133263}} {{Pythagorean Triple ,58408,79200,98408},{Root Coefficients ,396,200},{mult,792,minus,2367,square,617796},{(b^2-4ac)^(1/2) ,786},{298,98}} following is x in 2*x-b==root {{{x->789}},{{x->13483}}} {2 x-b=root,{139033},2 x-b=root*(1)^(1/2),{133263}} {{Pythagorean Triple ,59202,79600,99202},{Root Coefficients ,398,200},{mult,796,minus,3955,square,617796},{(b^2-4ac)^(1/2) ,786},{299,99}} following is x in 2*x-b==root {{{x->791}},{{x->13485}}} {2 x-b=root,{139033},2 x-b=root*(1)^(1/2),{133263}} {{Pythagorean Triple ,60000,80000,100000},{Root Coefficients ,400,200},{mult,800,minus,5551,square,617796},{(b^2-4ac)^(1/2) ,786},{300,100}} following is x in 2*x-b==root {{{x->793}},{{x->13487}}} {2 x-b=root,{139033},2 x-b=root*(1)^(1/2),{133263}} {{Pythagorean Triple ,60802,80400,100802},{Root Coefficients ,402,200},{mult,804,minus,7155,square,617796},{(b^2-4ac)^(1/2) ,786},{301,101}} following is x in 2*x-b==root {{{x->795}},{{x->13489}}} {2 x-b=root,{139033},2 x-b=root*(1)^(1/2),{133263}} {{Pythagorean Triple ,61608,80800,101608},{Root Coefficients ,404,200},{mult,808,minus,8767,square,617796},{(b^2-4ac)^(1/2) ,786},{302,102}} following is x in 2*x-b==root {{{x->797}},{{x->13491}}} {2 x-b=root,{139033},2 x-b=root*(1)^(1/2),{133263}} {{Pythagorean Triple ,62418,81200,102418},{Root Coefficients ,406,200},{mult,812,minus,10387,square,617796},{(b^2-4ac)^(1/2) ,786},{303,103}} following is x in 2*x-b==root {{{x->799}},{{x->13493}}} {2 x-b=root,{139033},2 x-b=root*(1)^(1/2),{133263}} {{Pythagorean Triple ,43776,87232,97600},{Root Coefficients ,376,232},{mult,752,minus,751,square,562500},{(b^2-4ac)^(1/2) ,750},{304,72}} following is x in 2*x-b==root {{{x->751}},{{x->23254}}} {2 x-b=root,{61186},2 x-b=root*(1)^(1/2),{55416}} {{Pythagorean Triple ,63232,81600,103232},{Root Coefficients ,408,200},{mult,816,minus,12015,square,617796},{(b^2-4ac)^(1/2) ,786},{304,104}} following is x in 2*x-b==root {{{x->801}},{{x->13495}}} {2 x-b=root,{139033},2 x-b=root*(1)^(1/2),{133263}}
In order to find the cube root of -1 mod p*q, the following call of the procedure will provide the first ten natural squares. In order to find the first natural square the following equation must be solved:
There doesn't seem to be an easy way to solve this equation.
{{Pythagorean Triple ,85376,19968,87680},{Root Coefficients ,416,48},{mult,880,minus,879,square,770884},{(b^2-4ac)^(1/2) ,878},{232,184}} following is x in 2*x-b==root {{{x->879}},{{x->10111}}} {2 x-b=root,{68877},2 x-b=root*(1)^(1/2),{4253}} {{Pythagorean Triple ,86210,20064,88514},{Root Coefficients ,418,48},{mult,884,minus,2643,square,770884},{(b^2-4ac)^(1/2) ,878},{233,185}} following is x in 2*x-b==root {{{x->881}},{{x->10113}}} {2 x-b=root,{68877},2 x-b=root*(1)^(1/2),{4253}} {{Pythagorean Triple ,87048,20160,89352},{Root Coefficients ,420,48},{mult,888,minus,4415,square,770884},{(b^2-4ac)^(1/2) ,878},{234,186}} following is x in 2*x-b==root {{{x->883}},{{x->10115}}} {2 x-b=root,{68877},2 x-b=root*(1)^(1/2),{4253}} {{Pythagorean Triple ,87890,20256,90194},{Root Coefficients ,422,48},{mult,892,minus,6195,square,770884},{(b^2-4ac)^(1/2) ,878},{235,187}} following is x in 2*x-b==root {{{x->885}},{{x->10117}}} {2 x-b=root,{68877},2 x-b=root*(1)^(1/2),{4253}} {{Pythagorean Triple ,88736,20352,91040},{Root Coefficients ,424,48},{mult,896,minus,7983,square,770884},{(b^2-4ac)^(1/2) ,878},{236,188}} following is x in 2*x-b==root {{{x->887}},{{x->10119}}} {2 x-b=root,{68877},2 x-b=root*(1)^(1/2),{4253}} {{Pythagorean Triple ,89586,20448,91890},{Root Coefficients ,426,48},{mult,900,minus,9779,square,770884},{(b^2-4ac)^(1/2) ,878},{237,189}} following is x in 2*x-b==root {{{x->889}},{{x->10121}}} {2 x-b=root,{68877},2 x-b=root*(1)^(1/2),{4253}} {{Pythagorean Triple ,90440,20544,92744},{Root Coefficients ,428,48},{mult,904,minus,11583,square,770884},{(b^2-4ac)^(1/2) ,878},{238,190}} following is x in 2*x-b==root {{{x->891}},{{x->10123}}} {2 x-b=root,{68877},2 x-b=root*(1)^(1/2),{4253}} {{Pythagorean Triple ,91298,20640,93602},{Root Coefficients ,430,48},{mult,908,minus,13395,square,770884},{(b^2-4ac)^(1/2) ,878},{239,191}} following is x in 2*x-b==root {{{x->893}},{{x->10125}}} {2 x-b=root,{68877},2 x-b=root*(1)^(1/2),{4253}} {{Pythagorean Triple ,92160,20736,94464},{Root Coefficients ,432,48},{mult,912,minus,15215,square,770884},{(b^2-4ac)^(1/2) ,878},{240,192}} following is x in 2*x-b==root {{{x->895}},{{x->10127}}} {2 x-b=root,{68877},2 x-b=root*(1)^(1/2),{4253}} {{Pythagorean Triple ,93026,20832,95330},{Root Coefficients ,434,48},{mult,916,minus,17043,square,770884},{(b^2-4ac)^(1/2) ,878},{241,193}} following is x in 2*x-b==root {{{x->897}},{{x->10129}}} {2 x-b=root,{68877},2 x-b=root*(1)^(1/2),{4253}} {{Pythagorean Triple ,93896,20928,96200},{Root Coefficients ,436,48},{mult,920,minus,18879,square,770884},{(b^2-4ac)^(1/2) ,878},{242,194}} following is x in 2*x-b==root {{{x->899}},{{x->10131}}} {2 x-b=root,{68877},2 x-b=root*(1)^(1/2),{4253}}
Going from the formula
and
where I and are natural squares and roots (not the
then a low root and square combination can be made of RSA260(850bits) shown in the following mathematica
In[3]:= RSA260 Out[3]= 22112825529529666435281085255026230927612089502470015394413748\ 3191288229414020019865127297265697465990859003300314000511707422045608\ 5927635795375718595429883895870922923849100670303412462054578456641366\ 4540684214361293017694020846391065875914794251435144458199 Get the root of the smallest square above RSA260 this is a 500 bit number of the 1000 bit modulus In[5]:= IIR = Mod[(Floor[RSA260^(1/2)] + 1), RSA260] Out[5]= 47024276208709120795061378748873252735571493245640595713707096\ 29848608672008763225036307999162383887826987432678940935201933498834 show the square In[15]:= II = Mod[(Floor[RSA260^(1/2)] + 1)^2, RSA260] Out[15]= 5481945886733977199005335761622105011576817180922572940050371\ 080118837515862925645017501652267319433494304753217083279905934901357 show the Pythagorean square root combination In[9]:= Mod[(8 + (II + 1) + 6 IIR), RSA260] == Mod[(3 + IIR)^2, RSA260] Out[9]= True show the square (500 bits of 1000 bit modulus) In[10]:= Mod[(8 + (II + 1) + 6 IIR), RSA260] Out[10]= 3369651161195944967604216301094605665291971312830693036827462\ 8859210489547915504995235349647241622760456229349290728891117535894370 show the root In[14]:= Mod[(3 + IIR), RSA260] Out[14]= 4702427620870912079506137874887325273557149324564059571370709\ 629848608672008763225036307999162383887826987432678940935201933498837
Considering that the above math has found another formula for the square root of -1 mod p*q. Normally, solving solves for , whereas we have now decided that solving for , and since for the cube root of 1 we have the formula , then the following formula should also hold, by symmetry:
It does as in:
Solve[3 x^2 + y^2 == 337 577, {x, y}, Integers] Out[4]= {{x -> -160, y -> -343}, {x -> -160, y -> 343}, {x -> -24, y -> -439}, {x -> -24, y -> 439}, {x -> 24, y -> -439}, {x -> 24, y -> 439}, {x -> 160, y -> -343}, {x -> 160, y -> 343}} Mod[3 (-160) PowerMod[-343, -1, 337 577], 337 577]=8505 this is the square root of -3 mod 337*577
Leonard Eugene Dickson at p219 vol 1 of "History Of Numbers" shows that A. Cunningham anticipates some of the math below by showing that then . However you can generalise beyond the roots of -1 to other negative roots, via the math below. "Number Theory" by Shanks at p143 also shows this type of construction in that then [31]
Australian Innovation Patents 2018100869 and 2018100919 show this generalisation more explicitly and for higher powers (which Cunningham suggested for the case of -1)
The quote from Dickson's "History Of Numbers" follows:
A. Cunningham[32] indicated how his tables may be used to solve directly for . From , we get the roots of . Also gives the roots and of , when e=a or b. Again, gives the roots , , and their reciprocals of [33]
The above math seems also to hold for the modulus as well.
Applying the same technique to the square root of -5:
Solve[5 x^2 + y^2 == 89 29, {x, y}, Integers] Out[14]= {{x -> -18, y -> -31}, {x -> -18, y -> 31}, {x -> -6, y -> -49}, {x -> -6, y -> 49}, {x -> 6, y -> -49}, {x -> 6, y -> 49}, {x -> 18, y -> -31}, {x -> 18, y -> 31}} Mod[5 (-18) PowerMod[(-31), -1, 89 29], 89 29]==1002 Mod[1002^2, 89 29]== -5
I am indebted to the Youtube Mathologer video[34] for this equation.
Put forward as a proof that the square root of 3 is irrational, this equation can often be achieved in modular arithmetic:
the root for 3, as opposed to -3 is:
Example in mathematica follows:
establish the sum of three squares Mod[3 8^2, 61 73]= 192 get the modular square root of the sum PowerMod[192, 1/2, 61 73]= 241 find the modular square root of 3 now Mod[3 8 PowerMod[241, -1, 61 73], 61 73]= 1700 confirm the root has been found Mod[1700^2, 61 73]= 3
It follows then that the modular square root of one number can be found if the modular square root of another number can be found, in this case the square root of 3 can be found from the square root of 192 in the 61*73 modulus.
Remembering the sum of three squares work equaling zero, that appears in other sections of this blog, then we can create and establish the square whose root is to be found as:
A Mathematica example follows:
Use this function to get the x^2+y^2 mod p*q === z^2 getASquareRootN[n_, n1_] := Module[{a1, a2, a3, a4, a5, a6, a7, a8, a9, a10}, a2 = IntegerPart[n^(1/2)/n1]; For[a1 = 1, a1 <= 10000, a1++, a4 = a1 n + n1^2; If[Mod[a4, 4] == 1 && PrimeQ[a4], Break[];];]; a5 = PowersRepresentations[a4, 2, 2]; a6 = Mod[a5[[1, 1]]^2 PowerMod[a5[[1, 2]]^2, -1, n ] + 1, n]; a7 = Mod[a6 a5[[1, 2]] PowerMod[n1, -1, n], n]; a8 = Mod[a7^2, n]; Return[{n1, a7, a6, a8}]] try some examples out getASquareRootN[61 73, 4]={4, 1071, 2620, 2620} and the root has been found after the square is established Mod[1071^2, 61 73]= 2620 getASquareRootN[89 29, 7]= {7, 295, 1852, 1852} Mod[295^2, 89 29]= 1852
Taking another example that after creating: and and also that . So our math still reveals the root of two squares, but, as I have said before, all roots mod p*q are the division of two squares.
Note that if we use this equation (which is entirely possible to do):
and this 1670 is:
so we can find the division of two roots.
If we take we can easily take if there is a modular square root of this. We can take this modular square root of and create a modular square root of the modulus . If we take the quotient of this square root squared against the then we can find the modular square root of
To generalize: where
The mathematica follows:
PowerMod[-1, 1/2, 67 73 - 2]= 730 PrimeQ[67 73 - 2]= True so we can easily take square roots of this modulus get the quotient N[730 730/(67 73 - 2)]= 109. create the new square in the p*q modulus Mod[-2 (109) - 1, 67 73]= 4672 confirm the root^2 = square Mod[730^2, 67 73]= 4672
In this way we can sorta go between the modulus and .
One may note that the root is decided before the square is found, so this may not actually be a nouvelle way to find a root, however, it does go between modula. This technique also works for cubes. Example to be shown later.
Here's some Mathematica which shows that the way to create the square other than squaring the root holds:
try123[p_, q_] := Module[{a1, a2, a3, a4, a5, a6, a7, a8, a9, a10}, a1 = NextPrime[p, 1]; For[a2 = 1, a2 < 100, a2++, a3 = NextPrime[q, 1]; For[a4 = 1, a4 < 100, a4++, If[a1 == a3, Continue[];]; If[PrimeQ[a1 a3 - 2], a5 = a1 a3 - 2; If[IntegerQ[PowerMod[-1, 1/2, a5]], a6 = PowerMod[-1, 1/2, a5]; a7 = Floor[N[a6^2/(a5)]]; If[EvenQ[a7], Print[{{a1, a3}, a5, a7, {a6}, {Mod[-2 a7 - 3, a1 a3], Mod[a6^2, a1 a3]}}]; ]; ]; ]; a3 = NextPrime[a3, 1]; ]; a1 = NextPrime[a1, 1]; ]; ]
try123[88, 28] P Q -2 Quot Root Square {{107,53},5669,192,{1046},{5284,5284}} {{107,89},9521,480,{2140},{8560,8560}} {{109,79},8609,388,{1830},{7832,7832}} {{113,47},5309,612,{1804},{4084,4084}} {{113,83},9377,864,{2848},{7648,7648}} {{131,29},3797,144,{742},{3508,3508}} {{131,89},11657,1992,{4820},{7672,7672}} {{137,59},8081,1920,{3940},{4240,4240}} {{137,83},11369,828,{3070},{9712,9712}} {{137,107},14657,900,{3634},{12856,12856}} {{139,109},15149,792,{3466},{13564,13564}} {{149,47},7001,204,{1198},{6592,6592}} {{151,61},9209,12,{346},{9184,9184}} {{157,79},12401,2976,{6076},{6448,6448}} {{157,127},19937,1824,{6032},{16288,16288}} {{163,97},15809,2688,{6520},{10432,10432}} {{167,53},8849,1012,{2994},{6824,6824}} {{179,29},5189,1152,{2446},{2884,2884}} {{181,163},29501,2376,{8374},{24748,24748}} {{191,101},19289,108,{1450},{19072,19072}} {{197,83},16349,964,{3972},{14420,14420}} {{211,181},38189,184,{2658},{37820,37820}} {{223,181},40361,444,{4238},{39472,39472}} {{229,79},18089,408,{2720},{17272,17272}} {{229,199},45569,292,{3654},{44984,44984}} {{233,191},44501,3276,{12076},{37948,37948}} {{239,101},24137,2104,{7128},{19928,19928}} {{241,151},36389,4524,{12832},{27340,27340}} {{241,211},50849,10564,{23178},{29720,29720}} {{251,41},10289,2272,{4836},{5744,5744}} {{251,233},58481,144,{2912},{58192,58192}} {{257,59},15161,1324,{4482},{12512,12512}} {{263,41},10781,520,{2370},{9740,9740}} {{263,101},26561,996,{5146},{24568,24568}} {{263,173},45497,4140,{13726},{37216,37216}} {{263,257},67589,13212,{29884},{41164,41164}} {{271,109},29537,1200,{5956},{27136,27136}} {{271,229},62057,1692,{10250},{58672,58672}} {{277,79},21881,264,{2408},{21352,21352}} {{277,139},38501,1024,{6282},{36452,36452}} {{281,131},36809,8988,{18190},{18832,18832}} {{281,239},67157,60,{2024},{67036,67036}} {{281,251},70529,2532,{13366},{65464,65464}} {{283,97},27449,4812,{11494},{17824,17824}} {{283,193},54617,1144,{7908},{52328,52328}} {{293,83},24317,5064,{11098},{14188,14188}} {{293,227},66509,7684,{22608},{51140,51140}} {{307,73},22409,1564,{5922},{19280,19280}} {{307,109},33461,5740,{13860},{21980,21980}} {{311,293},91121,11764,{32742},{67592,67592}} {{313,43},13457,0,{116},{13456,13456}} {{313,103},32237,4120,{11526},{23996,23996}} {{317,59},18701,276,{2276},{18148,18148}} {{317,167},52937,1564,{9102},{49808,49808}} {{331,229},75797,240,{4274},{75316,75316}} {{337,43},14489,12,{434},{14464,14464}} {{337,127},42797,4260,{13504},{34276,34276}} {{337,223},75149,17172,{35924},{40804,40804}} {{337,307},103457,8004,{28778},{87448,87448}} {{347,29},10061,2104,{4602},{5852,5852}} {{347,173},60029,14884,{29892},{30260,30260}} {{347,233},80849,7024,{23832},{66800,66800}} {{349,211},73637,3372,{15760},{66892,66892}} {{353,191},67421,9924,{25868},{47572,47572}} {{367,37},13577,444,{2458},{12688,12688}} {{367,97},35597,6340,{15024},{22916,22916}} {{373,67},24989,3972,{9964},{17044,17044}} {{373,367},136889,12,{1334},{136864,136864}} {{379,61},23117,2520,{7634},{18076,18076}} {{379,181},68597,432,{5450},{67732,67732}} {{383,257},98429,19668,{44000},{59092,59092}} {{383,281},107621,15456,{40786},{76708,76708}} {{383,353},135197,15732,{46120},{103732,103732}} {{389,71},27617,3120,{9284},{21376,21376}} {{389,131},50957,600,{5534},{49756,49756}} {{389,227},88301,7716,{26104},{72868,72868}} {{397,127},50417,2464,{11148},{45488,45488}} {{397,163},64709,14172,{30284},{36364,36364}} {{401,251},100649,21532,{46554},{57584,57584}} {{409,79},32309,3312,{10346},{25684,25684}} {{409,127},51941,60,{1780},{51820,51820}} {{409,151},61757,10024,{24882},{41708,41708}} {{409,211},86297,5160,{21104},{75976,75976}} {{421,31},13049,72,{976},{12904,12904}} {{421,199},83777,324,{5218},{83128,83128}} {{431,173},74561,10704,{28252},{53152,53152}} {{431,401},172829,3972,{26204},{164884,164884}} {{433,223},96557,16500,{39916},{63556,63556}} {{439,61},26777,12,{590},{26752,26752}} {{439,409},179549,564,{10072},{178420,178420}} {{443,101},44741,544,{4938},{43652,43652}} {{443,233},103217,84,{2962},{103048,103048}} {{449,59},26489,984,{5108},{24520,24520}} {{449,179},80369,628,{7110},{79112,79112}} {{449,347},155801,8076,{35474},{139648,139648}} {{457,307},140297,21304,{54672},{97688,97688}} {{461,59},27197,2532,{8300},{22132,22132}} {{461,83},38261,976,{6114},{36308,36308}} {{461,431},198689,25824,{71632},{147040,147040}} {{463,73},33797,540,{4276},{32716,32716}} {{463,97},44909,5988,{16400},{32932,32932}} {{463,397},183809,18832,{58836},{146144,146144}} {{467,137},63977,7912,{22500},{48152,48152}} {{467,197},91997,324,{5468},{91348,91348}} {{467,257},120017,23124,{52682},{73768,73768}} {{479,281},134597,9804,{36328},{114988,114988}} {{479,317},151841,1860,{16810},{148120,148120}} {{487,229},111521,6564,{27058},{98392,98392}} {{487,337},164117,29580,{69676},{104956,104956}} {{487,409},199181,20856,{64454},{157468,157468}} {{487,433},210869,492,{10196},{209884,209884}} {{491,53},26021,256,{2586},{25508,25508}} {{491,389},190997,29964,{75652},{131068,131068}} {{499,37},18461,40,{870},{18380,18380}} {{499,157},78341,15360,{34690},{47620,47620}} {{499,229},114269,18228,{45640},{77812,77812}} {{499,349},174149,672,{10826},{172804,172804}} {{503,293},147377,4980,{27094},{137416,137416}} {{509,59},30029,2712,{9026},{24604,24604}} {{509,71},36137,220,{2826},{35696,35696}} {{509,467},237701,796,{13764},{236108,236108}} {{521,179},93257,444,{6442},{92368,92368}} {{521,251},130769,1428,{13670},{127912,127912}} {{523,73},38177,1312,{7080},{35552,35552}} {{523,193},100937,2172,{14810},{96592,96592}} {{523,313},163697,9460,{39354},{144776,144776}} {{523,373},195077,34764,{82352},{125548,125548}} {{523,397},207629,29592,{78386},{148444,148444}} {{541,79},42737,1104,{6872},{40528,40528}} {{541,151},81689,8632,{26556},{64424,64424}} {{541,271},146609,9552,{37424},{127504,127504}} {{547,73},39929,5464,{14772},{29000,29000}} {{547,397},217157,0,{466},{217156,217156}} {{557,47},26177,100,{1626},{25976,25976}} {{557,479},266801,784,{14472},{265232,265232}} {{563,41},23081,424,{3132},{22232,22232}} {{563,53},29837,5784,{13138},{18268,18268}} {{563,173},97397,144,{3758},{97108,97108}} {{563,281},158201,844,{11562},{156512,156512}} {{563,557},313589,2832,{29806},{307924,307924}} {{569,59},33569,772,{5094},{32024,32024}} {{569,479},272549,66048,{134170},{140452,140452}} {{571,73},41681,1584,{8128},{38512,38512}} {{571,373},212981,1116,{15424},{210748,210748}} {{571,433},247241,7260,{42370},{232720,232720}} {{577,43},24809,5352,{11524},{14104,14104}} {{577,127},73277,11880,{29506},{49516,49516}} {{577,223},128669,11112,{37814},{106444,106444}} {{577,487},280997,19680,{74366},{241636,241636}} {{577,547},315617,100,{5646},{315416,315416}} {{587,197},115637,8272,{30930},{99092,99092}} {{587,233},136769,15312,{45764},{106144,106144}} {{587,269},157901,10500,{40720},{136900,136900}} {{587,389},228341,19804,{67248},{188732,188732}} {{587,449},263561,46044,{110162},{171472,171472}} {{593,71},42101,16,{846},{42068,42068}} {{593,227},134609,3888,{22880},{126832,126832}} {{593,443},262697,24924,{80918},{212848,212848}} {{593,467},276929,3652,{31806},{269624,269624}} {{599,89},53309,744,{6302},{51820,51820}} {{599,101},60497,4032,{15620},{52432,52432}} {{599,257},153941,13116,{44936},{127708,127708}} {{601,43},25841,2004,{7198},{21832,21832}} {{601,139},83537,5184,{20812},{73168,73168}} {{601,163},97961,18216,{42244},{61528,61528}} {{601,283},170081,1636,{16686},{166808,166808}} {{601,331},198929,48384,{98108},{102160,102160}} {{607,109},66161,1696,{10596},{62768,62768}} {{607,313},189989,684,{11408},{188620,188620}} {{607,577},350237,31144,{104442},{287948,287948}} {{613,31},19001,4504,{9252},{9992,9992}} {{613,43},26357,1692,{6680},{22972,22972}} {{613,127},77849,12,{1006},{77824,77824}} {{613,463},283817,36760,{102144},{210296,210296}} {{617,467},288137,1372,{19890},{285392,285392}} {{617,479},295541,50460,{122120},{194620,194620}} {{617,587},362177,9060,{57286},{344056,344056}} {{619,541},334877,27624,{96182},{279628,279628}} {{631,349},220217,7752,{41320},{204712,204712}} {{641,83},53201,3444,{13538},{46312,46312}} {{641,131},83969,15172,{35694},{53624,53624}} {{641,383},245501,36900,{95180},{171700,171700}} {{641,443},283961,39240,{105560},{205480,205480}} {{643,37},23789,3108,{8600},{17572,17572}} {{643,181},116381,1156,{11604},{114068,114068}} {{643,193},124097,1360,{12996},{121376,121376}} {{643,421},270701,30900,{91460},{208900,208900}} {{647,149},96401,1200,{10760},{94000,94000}} {{647,509},329321,72216,{154216},{184888,184888}} {{653,47},30689,484,{3858},{29720,29720}} {{653,167},109049,12012,{36194},{85024,85024}} {{653,227},148229,36864,{73922},{74500,74500}} {{653,251},163901,14436,{48644},{135028,135028}} {{653,563},367637,76924,{168168},{213788,213788}} {{659,257},169361,35476,{77514},{98408,98408}} {{659,269},177269,36828,{80800},{103612,103612}} {{659,281},185177,6700,{35226},{171776,171776}} {{659,509},335429,22668,{87200},{290092,290092}} {{661,163},107741,11460,{35140},{84820,84820}} {{661,223},147401,696,{10136},{146008,146008}} {{673,127},85469,2244,{13852},{80980,80980}} {{673,547},368129,52132,{138534},{263864,263864}}
My independent investigations into 1 mod 4 semiprimes show that while it is well known that there are only two sums of two squares per the p*q, there are actually many many more sums of three squares that equal p*q. Legendre's three-square theorem proves that there is a sum of three squares to describe most numbers, but it doesn't hint at how many three squares equal to 1 mod 4 semiprimes.
Showing the sums of three squares for the modulus 89*29 we find:
{{0, 9, 50}, {0, 30, 41}, {6, 12, 49}, {6, 32, 39}, {9, 14, 48}, {9, 30, 40}, {14, 33, 36}, {18, 24, 41}, {18, 31, 36}, {22, 24, 39}}
You'll notice that there are two sums of 2 squares in:
{0, 9, 50}, {0, 30, 41},
With these two sums of two squares you can factor 89*29 via the famous Euler's factorization method.
Looking at the list above you notice there are 8 sums of three squares, for larger numbers there are many more. In fact there seem to be as many sums of three squares as roughly .
Dickson's "History of the Theory of Numbers" vol 2 chapter 7 is entitled "Sums Of Three Squares" p259-274. On page 268 Dickson summarises the work of Eugène Charles Catalan who has a series of formulas that convert the roots of three squares into the roots of two squares:
E. Catalan[35] states that all solutions of are given without repetition by:
- where
- and and are relatively prime
- while
Taking the sums of three squares for , we can draw up the relevant Mathematica equation and see that these equations do get the two sums of squares from one set of three squares, and so then Euler's factorisation method can be employed to factor p*q:
In[10]:= Solve[ 6 == x + alpha && 49 == y - beta && x == s p + beta theta && y == s q + alpha theta && 2 s == alpha^2 + beta^2 + 12^2 && beta q - alpha p == 1, {x, y}, Integers] {{x -> ConditionalExpression[-41, alpha == 47 && beta == -79 && C[1] \[Element] Integers && p == 42 + 79 C[1] && q == -25 - 47 C[1] && s == 4297 && theta == 2285 + 4297 C[1]], y -> ConditionalExpression[-30, alpha == 47 && beta == -79 && C[1] \[Element] Integers && p == 42 + 79 C[1] && q == -25 - 47 C[1] && s == 4297 && theta == 2285 + 4297 C[1]]}, {x -> ConditionalExpression[-41, alpha == 47 && beta == -19 && C[1] \[Element] Integers && p == 2 + 19 C[1] && q == -5 - 47 C[1] && s == 1357 && theta == 145 + 1357 C[1]], y -> ConditionalExpression[30, alpha == 47 && beta == -19 && C[1] \[Element] Integers && p == 2 + 19 C[1] && q == -5 - 47 C[1] && s == 1357 && theta == 145 + 1357 C[1]]}, {x -> ConditionalExpression[-9, alpha == 15 && beta == 1 && C[1] \[Element] Integers && p == C[1] && q == 1 + 15 C[1] && s == 185 && theta == -9 - 185 C[1]], y -> ConditionalExpression[50, alpha == 15 && beta == 1 && C[1] \[Element] Integers && p == C[1] && q == 1 + 15 C[1] && s == 185 && theta == -9 - 185 C[1]]}, {x -> ConditionalExpression[9, alpha == -3 && beta == 1 && C[1] \[Element] Integers && p == C[1] && q == 1 - 3 C[1] && s == 77 && theta == 9 - 77 C[1]], y -> ConditionalExpression[50, alpha == -3 && beta == 1 && C[1] \[Element] Integers && p == C[1] && q == 1 - 3 C[1] && s == 77 && theta == 9 - 77 C[1]]}, {x -> ConditionalExpression[41, alpha == -35 && beta == -79 && C[1] \[Element] Integers && p == 70 + 79 C[1] && q == 31 + 35 C[1] && s == 3805 && theta == 3371 + 3805 C[1]], y -> ConditionalExpression[-30, alpha == -35 && beta == -79 && C[1] \[Element] Integers && p == 70 + 79 C[1] && q == 31 + 35 C[1] && s == 3805 && theta == 3371 + 3805 C[1]]}, {x -> ConditionalExpression[41, alpha == -35 && beta == -19 && C[1] \[Element] Integers && p == 6 + 19 C[1] && q == 11 + 35 C[1] && s == 865 && theta == 271 + 865 C[1]], y -> ConditionalExpression[30, alpha == -35 && beta == -19 && C[1] \[Element] Integers && p == 6 + 19 C[1] && q == 11 + 35 C[1] && s == 865 && theta == 271 + 865 C[1]]}}
I found a very quick way to find a sum of three squares for a large number, specificaly RSA230. See the next section! For instance for the modulus, there are at least 92 sums of three squares applicable, which is close to .
On page 274 of Dickson's History of Numbers vol2 there are two further references to mathematicians who gave formulas for converting
A. Gerardin and E Miot[36] gave many identities
He [A.S. Werebrusow][37] gave long formulas said to solve completely.
Neither A. Gerardin, E Miot, or A.S. Werebrusow (Веребрюсов А) seem to have wiki biops in any wiki. E. Catalan does.
A.S. Werebrusow's father seems to have a ruwiki article as an archeologist and there is another Werebrusow featured, a polar air pilot, perhaps A.S.'s son.
Please note that if you know and this sum is a 1 mod 4 prime number, then discovery of and can be known in log(n) time, basically instantly. This solves for the two squares that sum to p*q.
It is possible to obtain
It is easily possible to create large numbers of three squares that equal p*q. So some of them will have sums that are .
I have not been able to take this attack further, except to note that and that and that .
It is also possible to come up with the following equivalence:
After a second thought it does seem that three squares are not needed for Catalan's equations. You can substract 2*SQUARE1, as in:
As such:
So can be found for the mod that is a square root of this amount, rather larger than the figure I had in my post just above.
And Catalan's equations seem to work, at least for my example, as in:
(Debug) In[1]:= PowersRepresentations[2581, 2, 2] (Debug) Out[1]= {{9, 50}, {30, 41}} (Debug) In[13]:= Solve[ 25 == x + alpha && 25 == y - beta && x == s p + beta theta && y == s q + alpha theta && 2 s == alpha^2 + beta^2 + 1331 && beta q - alpha p == 1, {x, y}, Integers] (Debug) Out[13]= {{x -> ConditionalExpression[-50, alpha == 75 && beta == -34 && C[1] \[Element] Integers && p == 29 + 34 C[1] && q == -64 - 75 C[1] && s == 4056 && theta == 3461 + 4056 C[1]], y -> ConditionalExpression[-9, alpha == 75 && beta == -34 && C[1] \[Element] Integers && p == 29 + 34 C[1] && q == -64 - 75 C[1] && s == 4056 && theta == 3461 + 4056 C[1]]}, {x -> ConditionalExpression[-41, alpha == 66 && beta == 5 && C[1] \[Element] Integers && p == 4 + 5 C[1] && q == 53 + 66 C[1] && s == 2856 && theta == -2293 - 2856 C[1]], y -> ConditionalExpression[30, alpha == 66 && beta == 5 && C[1] \[Element] Integers && p == 4 + 5 C[1] && q == 53 + 66 C[1] && s == 2856 && theta == -2293 - 2856 C[1]]}, {x ->
Now, will yield possible answers that will be fully qualified, that is, the and the derived from the sum will not be residues but full answers. Therefore, will be fully qualified (not residues) as and , which can be manipulated to see if they equal a sum in the 25 modulus field. Therefore, some quick way to intersect the and between the and fields must be found if the problem is to be solved in the manner I have described above.
With known now (see above section), we can add a 1 mod 4 prime modulus to Catalan's Equations.
To get an answer almost instantly that is , you need to:
Solve[0 == x + alpha && 0 == y - beta && x == s p + beta theta && y == s q + alpha theta && 2 s == alpha^2 + beta^2 + (2000029 3000017 - 2 800029^2) && beta q - alpha p == 1 && alpha^2 + beta^2 == Mod[2000029 3000017, 800029] && alpha + beta == 3 && theta == 1 && beta alpha == ba, {x, y}, Modulus -> 800029] {{x -> ConditionalExpression[353438, alpha == 446591 && ba == 248018 && beta == 353441 && p == 539266 && q == 402359 && s == 304002 && theta == 1], y -> ConditionalExpression[353441, alpha == 446591 && ba == 248018 && beta == 353441 && p == 539266 && q == 402359 && s == 304002 && theta == 1]}, {x -> ConditionalExpression[446588, alpha == 353441 && ba == 248018 && beta == 446591 && p == 539266 && q == 397670 && s == 304002 && theta == 1], y -> ConditionalExpression[446591, alpha == 353441 && ba == 248018 && beta == 446591 && p == 539266 && q == 397670 && s == 304002 && theta == 1]}}
If you set correctly, then you get the correct answer.
PowersRepresentations[3000029 4000037, 2, 2] {{133708, 3461553}, {1975847, 2845392}} (Debug) In[1]:= Solve[ 0 == x + alpha && 0 == y - beta && x == s p + beta theta && y == s q + alpha theta && 2 s == alpha^2 + beta^2 + (2000029 3000017 - 2 800029^2) && beta q - alpha p == 1 && alpha^2 + beta^2 == Mod[2000029 3000017, 800029] && alpha + beta == 1593911 && theta == 1 && beta alpha == ba, {x, y}, Modulus -> 800029] (Debug) Out[1]= {{x -> ConditionalExpression[132505, alpha == 667524 && ba == 740151 && beta == 126358 && p == 684044 && q == 615227 && s == 304002 && theta == 1], y -> ConditionalExpression[126358, alpha == 667524 && ba == 740151 && beta == 126358 && p == 684044 && q == 615227 && s == 304002 && theta == 1]}, {x -> ConditionalExpression[673671, alpha == 126358 && ba == 740151 && beta == 667524 && p == 684044 && q == 184802 && s == 304002 && theta == 1], y -> ConditionalExpression[667524, alpha == 126358 && ba == 740151 && beta == 667524 && p == 684044 && q == 184802 && s == 304002 && theta == 1]}}
Figuring out what is will also solve the equation. There does seem to be a relationship between what you set to and but I haven't figured it out yet.
To conclude, if there was a way to figure out then you could use Catalan's equations to solve for 1 mod 4 semiprimes quite quickly.
We can take the square root of and establish a modular square root.
Then we can use Dickson's method of Pythagorean Triples described here. Therefore we can solve for the , and of such triples as in:
Find an equivalent and pair (ie., , ):
Solve[0 == x + alpha && 0 == y - beta && x == s p + beta theta && y == s q + alpha theta && 2 s == alpha^2 + beta^2 + (2000029 3000017 - 2 800029^2) && beta q - alpha p == 1 && alpha^2 + beta^2 == Mod[2000029 3000017, 800029] && alpha + beta == 3 && theta == 1 && beta alpha == ba, {x, y}, Modulus -> 800029] {{x -> ConditionalExpression[353438, alpha == 446591 && ba == 248018 && beta == 353441 && p == 539266 && q == 402359 && s == 304002 && theta == 1], y -> ConditionalExpression[353441, alpha == 446591 && ba == 248018 && beta == 353441 && p == 539266 && q == 402359 && s == 304002 && theta == 1]}, {x -> ConditionalExpression[446588, alpha == 353441 && ba == 248018 && beta == 446591 && p == 539266 && q == 397670 && s == 304002 && theta == 1], y -> ConditionalExpression[446591, alpha == 353441 && ba == 248018 && beta == 446591 && p == 539266 && q == 397670 && s == 304002 && theta == 1]}}
Then apply the following mathematica equation(noting that :
Solve[2 s t == r^2 && 446591 == (r + s) && 353441 == (r + t) && 379045 == (r + s + t), {r, s, t}, Modulus -> 800029] {{r -> 420987, s -> 25604, t -> 732483}}
climbs by the amount that is increased in Catalan's equations.
The correct answer happens when you set the correctly.
Solve[2 s t == r^2 && 667524 == (r + s) && 126358 == (r + t) && 379045 == (r + s + t), {r, s, t}, Modulus -> 800029] {{r -> 414837, s -> 252687, t -> 511550}}
We haven't progressed to the answer here, but we have showed that the intermediate values of Dickson's method can be ascertained, with help from Catalan's equations, and we have shown that when progresses to for the correct answer.
Miot's work[36] gives formulas that instantly create 2 squares from 3 squares, but only for certain 3 squares. I tried this out on RSA230 but several thousand 3 square sums did not get anywhere with Miot's formulas:
Miot gives 12 formulas that derive 2 squares from 3. They are given in the following mathematica function. These formulas will instantly find 2 squares if the main conditions hit.
miot[sq1_, sq2_, sq3_, pq_] := Module[{a1, a2, a3, a4, a5, a6, a7, a8, a9, a10, a11, a12, a13, a14, a15}, a1 = Solve[ sq1 == (p - m) && sq2 == (q - n) && sq3 == (2 m - 2 n) && x == (m + p - 2 n) && y == (m + q - 2 n) && m + n == p + q, {x, y}, Integers]; a2 = Solve[ sq1 == (n - m) && sq2 == (q - m + n - p) && sq3 == ( m - p) && x == (2 n - m - p) && y == (q - p) && m + n == p + q, {x, y}, Integers]; a3 = Solve[ sq1 == (p - m - q + n) && sq2 == (n - m) && sq3 == (m - q) && x == (2 n - m - q) && y == (p - q) && m + n == p + q, {x, y}, Integers]; a4 = Solve[ sq1 == (n - p) && sq2 == (n - m) && sq3 == ( m + q - p - n) && x == (q - p) && y == (2 m - n - p) && m + n == p + q, {x, y}, Integers]; If[a1 != {}, Print[a1];]; If[a2 != {}, Print[a2];]; If[a3 != {}, Print[a3];]; If[a4 != {}, Print[a4];]; a5 = Solve[ sq1 == (n - q) && sq2 == (m + p - n - q) && sq3 == (m - n) && x == (p - q) && y == (2 m - n - q) && m + n == p + q, {x, y}, Integers]; a6 = Solve[ sq1 == (2 n - 2 m) && sq2 == (p - m) && sq3 == ( q - m) && x == (p - 2 m + n) && y == (q - 2 m + n) && m + n == p + q, {x, y}, Integers]; a7 = Solve[ sq1 == (q - m) && sq2 == (p - q) && sq3 == (n + p - q - m) && x == (q - m) && y == (2 p - q - m) && m + n == p + q, {x, y}, Integers]; a8 = Solve[ sq1 == (q - n) && sq2 == (m + p - q - n) && sq3 == ( p - q) && x == (m - n) && y == (2 p + q - n) && m + n == p + q, {x, y}, Integers]; If[a5 != {}, Print[a5];]; If[a6 != {}, Print[a6];]; If[a7 != {}, Print[a7];]; If[a8 != {}, Print[a8];]; a9 = Solve[ sq1 == (2 q - q p) && sq2 == (m - p) && sq3 == (n - p) && x == (m + q - 2 p) && y == (n + q - 2 p) && m + n == p + q, {x, y}, Integers]; a10 = Solve[ sq1 == (m - q) && sq2 == (n - q) && sq3 == ( 2 p - 2 q) && x == (m + p - 2 q) && y == (n + p - 2 q) && m + n == p + q, {x, y}, Integers]; a11 = Solve[ sq1 == (q - p) && sq2 == (n + q - m - p) && sq3 == (p - m) && x == (2 q - m - p) && y == (n - m) && m + n == p + q, {x, y}, Integers]; a12 = Solve[ sq1 == (m + q - n - p) && sq2 == (q - p) && sq3 == ( p - n) && x == (2 q - n - p) && y == (m - n) && m + n == p + q, {x, y}, Integers]; If[a9 != {}, Print[a9];]; If[a10 != {}, Print[a10];]; If[a11 != {}, Print[a11];]; If[a12 != {}, Print[a12];]; Return[0]; ]
Try these for tests(these are examples from Miots work:
miot[3,2,10] miot[-5,6,2] miot[-4,-5,3] miot[4,5,-3] miot[5,-6,-2] miot[-3,-2,-10] miot[-3,1,-4] miot[2,6,1] miot[-2,2,3] miot[-1,-6,-2] miot[3,-1,4]
Werebruscow[37] gives a general formula to derive 2 squares from 3 but it only worked on his example. For almost any other 3 square combination it was too slow to use. The mathematica formula for his work is given below:
erebrussov[sq1_, sq2_, sq3_] := Module[{a1, a2, a3, a4, a5, a6, a7, a8, a9, a10, a11, a12, a13, a14, a15}, a1 = Solve[ sq1 == (a^2 - c^2) m - (b^2 - d^2) n + (a b + c d) t && sq2 == -(a d - b c) (m - n) + (a c - b d) t && sq3 == 2 (a c m - b d n) && x == (a^2 + c^2) m - (b^2 + d^2) n + (a b - c d) t && y == (a d - b c) (m + n) + (a c + b d) t && c*(x + sq1) == b (y + sq2) && m (y + sq2) == n (x - sq2), {x, y}, Modulus -> sq3]; Print[a1]; ]
WereBruscow's tests were:
a=3;b=c=2;d=1;m=2;n=1 werebrussov[7,1,20] werebrussov[9,2,20] werebrussov[11,3,20] werebrussov[13,4,20]
With some Internet research I was able to get the sums of three squares that equal RSA230, which still hasn't been factored yet. The sums, which were computed with both Mathematica and the Python2 interpreter on the Raspberry PI are as follows:
In[42]:= RSA230 Out[42]= 1796949159794106673291612844957324615636756180801260007088891\ 8835531726460341490933493372247868650755230855864199929221814436684722\ 8740520652579374956943483892631711525225256544109808191706117425097024\ 40718010364831638288518852689 In[44]:= cc1 Out[44]= 1059443675295336206903990032177460807418972848557933447798562\ 577562645416414595037181025050793827302992107472819164 In[45]:= cc2 Out[45]= 3776571573920219939515093763531383887422242718192208743361060\ 316544426926673520279457864260379607843037554625909088 In[46]:= cc3 Out[46]= 1607662229411243491074817949573445948811265336194645770178567\ 6314739439621472137233436060406493556443939160932757439 In[48]:= cc1^2 + cc2^2 + cc3^2 == RSA230 Out[48]= True
Using Rabin and Shallit's 1986 paper "Randomized Algorithms in Number Theory" [38] as a starting point I was able to scout some Python code on the web that efficiently find two squares to equal a prime. This code was attributed to the work of Moron, but looks to me as if it follows the algorithm specified by Rabin and Shallit.
Rabin and Shallit claim that most large numbers are the combination of a square and a prime. Therefore I was able to find the square and prime combination for RSA230 with the following Mathematica function:
gettriplesum[n_] := Module[{a1, a2, a3, a4, a5, a6a7, a8, a9, a10}, a2 = IntegerPart[n^(1/2)]; For[a1 = 1, a1 <= 10000, a1++, a3 = RandomInteger[{1, a2}]; a4 = n - a3^2; If[Mod[a4, 4] == 1 && PrimeQ[a4], Print[{a3, a4}]; Break[]; ]; ] ] gettriplesum[RSA230] { 1059443675295336206903990032177460807418972848557933447798562577562645416414595037181025050793827302992107472819164, 16847070696817776955023057830757895086859297723779890333200095426684361615676774916907649128657920475263571237974721202924734845958611847111565024073198103645771175940386211354906765850662429243724892455890188710147403230673193793} // the first number is the square and the second number is the prime n-x^2
For a 1 mod 4 prime number, the mathematica function, PowersRepresentations[n,2,2] will also find the two squares that the prime number equates to very quickly.
I then used the following Python code, on the Raspberry PI Python2 Interpreter to split the prime number found by mathematica routine above into the sum of two squares:[39]:
# code taken from web: Python code for sum of 2 squares for a prime number, author=Robin Chapman, url = # "https://math.stackexchange.com/questions/5877/efficiently-finding-two-squares-which-sum-to-a-prime", access-date=19/10/2017 def mods(a, n): if n <= 0: return "negative modulus" a = a % n if (2 * a > n): a -= n return a def powmods(a, r, n): out = 1 while r > 0: if (r % 2) == 1: r -= 1 out = mods(out * a, n) r /= 2 a = mods(a * a, n) return out def quos(a, n): if n <= 0: return "negative modulus" return (a - mods(a, n))/n def grem(w, z): # remainder in Gaussian integers when dividing w by z (w0, w1) = w (z0, z1) = z n = z0 * z0 + z1 * z1 if n == 0: return "division by zero" u0 = quos(w0 * z0 + w1 * z1, n) u1 = quos(w1 * z0 - w0 * z1, n) return(w0 - z0 * u0 + z1 * u1, w1 - z0 * u1 - z1 * u0) def ggcd(w, z): while z != (0,0): w, z = z, grem(w, z) return w def root4(p): # 4th root of 1 modulo p if p <= 1: return "too small" if (p % 4) != 1: return "not congruent to 1" k = p/4 j = 2 while True: a = powmods(j, k, p) b = mods(a * a, p) if b == -1: return a if b != 1: return "not prime" j += 1 def sq2(p): a = root4(p) return ggcd((p,0),(a,1))
It turns out to be quite easy to find sums of three squares for RSA numbers, even RSA numbers that have not been factored yet.
This above Python code, by the way, essentially does a complex Euclidean GCD function on . It also works for p*q modulus as in the following run of the GGCD(...) function
ggcd((2581,0),(945,1)) (-30, -41) 30*30+41*41 2581 ggcd((2581,0),(568,1)) (50, -9) 50*50+9*9 2581
where and . Since this function runs in log(n) time it is super quick to find the sums of squares of any size p*q when you know the corresponding .
It remains to be seen whether the Catalan set of linear equations, shown above this section, can efficiently reduce the three squares to two squares. (This assumes that RSA230 is a 1 mod 4 semiprime).
If you look at Dickson's method of generating Pythagorean Triples, (see Formulas_for_generating_Pythagorean_triples#Dickson's_method), you will see that modular pythagorean triples can easily be generated. Since:
Take for instance,
or in other words:
Note this doesn't work in continuous arithmetic but does work in modular arithmetic. Thus:
And this works since:
whereas:
Dickson treats Pythagorean Triples as the equation and treats the equation here[40]
Bottari, reported by Dickson on "History Of Numbers", vol 2, p169, extends Dicksons definitions of the intermediate terms: , , and :
A. Bottari[41] proved that all integral solutions of are given by , , where , , , and being relatively prime odd integers. Thus is not a square.
These equations above can be seen to jive with my own observation that a Pythagorean Triple can be described as:
If you set Bottari's and then the following equation can be seen:
This equals: , so any successful use of these equations will reveal one of the two sums of squares for p*q.
So it seems that Bottari's equations anticipate my own observation on how a Pythagorean Triple can be built, but the way I derive the equations (by use of the squareless number mod p*q) is probably unique, and thus a new proof on this matter.
Dickson reports Volpicelli's work on vol 2 p168 as:
- P Volpicelli[42] noted that imply that
- and
- are solutions of
A quick look with Mathematica shows this to be true:
In[1]:= PowersRepresentations[2581, 2, 2] Out[1]= {{9, 50}, {30, 41}} In[2]:= PowersRepresentations[2581 2581, 2, 2] Out[2]= {{0, 2581}, {781, 2460}, {900, 2419}, {1131, 2320}, {1780, 1869}} In[3]:= 9 30 + 50 41 Out[3]= 2320 In[5]:= 9 41 - 50 30 Out[5]= -1131
So it looks that if you can find the sum of two squares of you are on the way to finding out the sums of squares of . Thus if you can find the Pythagorean Triple that includes you should be in good shape.
In Euler's factorization method, the following quote occurs:
Euler's factorization method is a technique for factoring a number by writing it as a sum of two squares in two different ways. For example the number can be written as or as and Euler's method gives the factorization .
In addition to this is Euler's other factoring method, mentioned in p362 of vol 1 of Dickson's "History of Numbers"[43]:
- Euler[44] noted that imply
- , ,
- so that , or its half or quarter, is a factor of N.
It seems that finding two sets of is easier than finding two sets of .
The following equation shows this to work:
Solve[ a^2 + 5 b^2 == 8467 39343 && a > 0 && b > 0, {a, b}, Integers] {{a -> 16541, b -> 3450}, {a -> 17776, b -> 1851}} aa = Solve[16541 - 17776 == 5 m p && 3450 + 1851 == m q && 3450 - 1851 == n p, {m, n, p, q}, Integers] {{m -> -19, n -> 123, p -> 13, q -> -279}, {m -> 19, n -> -123, p -> -13, q -> 279}} now one of the factors is seen, 39343 (1/2) (5 p^2 + q^2) /. aa {39343, 39343}
This example shows the factoring algorithm works on 3 mod 4 semiprimes, and is thus more general than the more well known Euler factoring algorithm.
Knowing it is possible to find the two square roots of -5 and thus solve for the square root of 1. With the square root of 1 p*q can be factored.[45][46]
and
After some research I can point to a 1996 paper on Euler Factorization by James McKee[47]. In this paper he shows how to instantly solve when . In this case and, if D is a prime number, then you can take the modular square root easily giving . If then is not a residue but the actual square root. Therefore and so b is easy to find. However, for most large values of D there is no solution and certainly not two solutions. However, if there are two solutions, then the differing square roots of will provide the two answers necessary for Euler's algorithm to work. D usually needs to be a composite number before there are two solutions.
McKee provides an algorithm that determines in operations.
P. Tchebychef[48], which is referenced on p 363 vol 1 of Dickson's History Of Numbers, provides a workable method to create quickly . In this algorithm he uses mathematical sequences that are alike to his famous T and U sequences. Since the D's are different in these sequences they can't be used with Euler factorization, but Tchebychef does have math that limits the number of possible factors, but I haven't translated the German for this yet, so I can't report more on it.
Another source that extends Euler's work to is at url [49].
For the more general equation, it is easily possible to get a second equation with the same coefficients but different squares. However, this second equation does not help solve the modular square root problem of better than the first such equation.
The work for this second general equation is in Mathematica below:
create a first equation Solve[2 2^2 + y 3^2 == 0, {y}, Modulus -> 337 577] {{y -> 43210}} Use Mathematica to get our answer for the set of squares, assuming that (x+z)^2 and (y+z)^2 holds Solve[2 (2 2 x) + 43210 (2 3 x ) + (2 + 43210) (x^2) == 0, {x}, Modulus -> 337 577] {{x -> 0}, {x -> 116667}, {x -> 141942}, {x -> 169174}} convert the equation to the equation below (where x is the same increase in square for both earlier squares Solve[2 (2 2 ) + 43210 (2 3 ) + (2 + 43210) (x) == 0, {x}, Modulus -> 337 577] {{x -> 116667}} confirm second equation has been found Mod[2 (2 + 116667)^2 + 43210 (3 + 116667)^2, 337 577] 0
If you have the sum of three squares that equal p*q as in:
(This equation is rather easy to come by). You can easily turn the above equation into
See the following Mathematica for how:
try555[p_, q_, sq1_, sq2_, sq3_] := Module[{a1, a2, a3, a4, a5, a6, a7, a8, a9, a10, d1, d2}, make the first coefficient for the third square d1 = Mod[(sq2 PowerMod[sq3, -1, p q])^2 + 1, p q]; make the second coefficient for the second square d2 = Mod[(sq3 PowerMod[sq2, -1, p q])^2 + 1, p q]; create the two a^2+D*b^2===0 equations (a1 and a2 should be 0) a1 = Mod[sq1^2 + d1 sq3^2, p q]; a2 = Mod[sq1^2 + d2 sq2^2, p q]; now make the square root of -d1 a3 = Mod[d1 sq3 PowerMod[sq1, -1, p q], p q]; now make the square root of -d2 a4 = Mod[d2 sq2 PowerMod[sq1, -1, p q], p q]; Print[{d1,d2,a1, a2, a3, a4}]; ]
I was able to get a second equation:
and
where
via the following Mathematica procedure
try555a[pq_, sq1_, sq2_, sq3_] := Module[{a1, a2, a3, a4, a5, a6, a7, a8, a9, a10, a11, d1, d2, aa, aa1},(* make the first coefficient for the third square *) d1 = Mod[(sq2 PowerMod[sq3, -1, pq])^2 + 1, pq]; (* make the second coefficient for the second square d2= *) d2 = Mod[(sq3 PowerMod[sq2, -1, pq])^2 + 1, pq]; (* create the two a^2+D*b^2===0 equations (a1 and a2 should be 0) *) a1 = Mod[sq1^2 + d1 sq3^2, pq]; a2 = Mod[sq1^2 + d2 sq2^2, pq]; a3 = Mod[d1 sq3 PowerMod[sq1, -1, pq], pq]; (* now make the square root of-d2*) a4 = Mod[d2 sq2 PowerMod[sq1, -1, pq], pq]; (* create new sq1 value for new equation with d1 as coefficient *) a10 = Mod[sq1 PowerMod[a4, -1, pq] a3, pq]; (* create second lambda equation with d1 as coefficient *) a9 = Mod[(a10)^2 + d1 sq2^2, pq]; (*now make the square root of-d1 *) a8 = Mod[d1 sq2 PowerMod[a10, -1, pq], pq]; (* show all equations === 0 *) Print[{a1, a2, a9}]; (* show square roots for each, will be the same number *) Print[{a3, a8}]; ] xx = gettriplesum[RSA250] Out[54]= \ {165860061048452763122039049657801862112488124844426769348338381761838\ 14044125663241348400613753473490541580331600292633724766, \ {{25944870035655880693470184661269460904056949255968992822389092893715\ 074425420651767658631053048013008721569909941245307881395, 3452669649074040512807064992216570444848151505579000402143700132129\ 6114351445158713082710689537165522558482742515055457347034}}} try555a[RSA250, xx[[1]], xx[[2, 1, 1]], xx[[2, 1, 2]]] {0,0,0} {1314918825722326266553810724613655705450573430361780650965255219994346873009830842936478043044889827565960168693343635958715548336143856317630304562317098246478476883836301907222798067314919038129210689957690416029268511846909871046833022463555902835, 1314918825722326266553810724613655705450573430361780650965255219994346873009830842936478043044889827565960168693343635958715548336143856317630304562317098246478476883836301907222798067314919038129210689957690416029268511846909871046833022463555902835}
I was successful in getting the second lambda equation with the same D set, but these are equivalences and I could not apply Euler's equations. And the calculation of was always the same.
As it works out, from reading the last section, the square root of (-d1)^2 + sq1^2 mod p*q==-1!
So the difficult sum of two squares (for big modula) can be solved quite quickly and easily.
First, get a sum of three squares for RSA250.
Here is RSA250 RSA250 = 2140324650240744961264423072839333563008614715144755017797754\ 9208814180234471401366433455190958046796109928518724709145876873962619\ 2155736304745477052080511905649310668769159001975940569345745223058932\ 5976697471681738069364894699871578494975937497937 Here is the Mathematica function to quickly get a sum of three squares gettriplesum[n_] := Module[{a1, a2, a3, a4, a5, a6, a7, a8, a9, a10}, a2 = IntegerPart[n^(1/2)]; For[a1 = 1, a1 <= 10000, a1++, a3 = RandomInteger[{1, a2}]; a4 = n - a3^2; If[Mod[a4, 4] == 1 && PrimeQ[a4],(*Print[{a3,PowersRepresentations[ a4,2,2]}];*) Break[];];]; Return[{a3, PowersRepresentations[a4, 2, 2]}]] Call these Mathematica function with RSA250 as a parameter In[26]:= xx = gettriplesum[RSA250] Get the three squares as in {sq1 {{sq2, sq3}}} Out[26]= \ {243380194038096721134728635329583049374302758780918783047778468000204\ 08951489652005729084735517130026118580586677733557228650, \ {{15571417391916781570313932870412914878875779562929051747073116333550\ 958978301349252861839216717338401458664855976888733005331, 3613193078354989362361048454753033207443616957247130450038451637022\ 7361689326905007008354298940632858505779761105701152682626}}} Verify that a sum of three squares has been found. Mod[ xx[[1]]^2 + xx[[2, 1, 1]]^2 + xx[[2, 1, 2]]^2, RSA250]= 0
Now use the following Mathematica function to find two equations that match
Use this function to find the sum of two squares equivalent to -1 (there will be two of the many possible equations) try333[pq_, sq1_, sq2_, sq3_] := Module[{a1, a2, a3, a4, a5, a6, a7, a8, a9, a10}, a1 = Mod[sq2 PowerMod[sq3, -1, pq], pq]; a2 = Mod[sq3 PowerMod[sq2, -1, pq], pq]; a3 = Mod[(a1^2 + 1) sq3 PowerMod[sq1, -1, pq], pq]; a4 = Mod[(a2^2 + 1) sq2 PowerMod[sq1, -1, pq], pq]; Print[{a3, a1, "the square of these equiv to -1 mod RSA250"}]; Print[Mod[a3^2 + a1^2, pq] == pq - 1]; Print[{a4, a2, "the square of these equiv to -1 mod RSA250"}]; Print[Mod[a4^2 + a2^2, pq] == pq - 1]; ] Call the function with the result of the sum of three squares try333[RSA250, xx[[1]], xx[[2, 1, 1]], xx[[2, 1, 2]]] {20531750694324444278194615633359107622786730656405815811283334282496438825649004986807633314 192758485080501459280012835625675591324044290554905379578360681668877793625098111587991587524 3402636647648989593183240107441157037970834906371969195115706045, 137234074163171487327487258017935715874463146065821660277962023202104067985790892654907939069 435476500304347602923900594193201340378557021828650433051727667994046506106923369059570452647 8985786660883769985144804512456179268024201827582795664492962038, the square of these equiv to -1 mod RSA250} True {2058939105332570506966632459210337476578836982622628151064611190716985403292889078279085904619 26232867822101211765799749379103106513053574742158632737358346149165543679778796790432858491397 9880613119683180870284399038454516995333555882941337370020246, 125861236994699879978009154578085 19341562919317725704551392290765423337011029727993120835287383385603162629789031453667054584801 26589343477937166793364831484318881166117013009465590110340260791300136907101768344999800459542 228308110158167680555421897, the square of these equiv to -1 mod RSA250} True
Please remember that if you run this equation through Mathematica with that needs be taken, and this is beyond all computers to do. So this procedure, outlined above, does successfully solve, for two instances, the sum of two squares equaling -1.
It follows that is easy to derive, so the sum of two squares for any negative square can be established.
Also, Catalan[50]
has an equation that can be used to derive
Specifically, the identity[50]
can be used with . So a can be applied to the powers in the left of the equation, and a can be added to the right of the equation.
Working with the above Mathematica functions, it can be seen that they can be extended to do the equation:
By subtracting we can find the equation above. See the Mathematica functions below, and how they are called:
try333N[pq_, sq3_, sq2_, sq1_, n1_] := Module[{a1, a2, a3, a4, a5, a6, a7, a8, a9, a10}, a1 = Mod[sq2 PowerMod[sq3, -1, pq], pq]; a3 = Mod[(a1^2 + n1) sq3 PowerMod[sq1, -1, pq], pq]; Print[{a3, a1, "the square of these equiv to", -n1, " mod RSA250"}]; Print[Mod[a3^2 + a1^2, pq] == pq - n1]; ] gettriplesumN[n_, n1_] := Module[{a1, a2, a3, a4, a5, a6, a7, a8, a9, a10}, a2 = IntegerPart[n^(1/2)/n1]; For[a1 = 1, a1 <= 10000, a1++, a3 = RandomInteger[{1, a2}]; a4 = n - n1 a3^2; If[Mod[a4, 4] == 1 && PrimeQ[a4],(*Print[{a3,PowersRepresentations[ a4,2,2]}];*) Break[];];]; Return[{n1, a3, PowersRepresentations[a4, 2, 2]}]] sumsnsquares[pq_, n1_] := Module[{a1, a2, a3, a4}, a1 = gettriplesumN[pq, n1]; a2 = try333N[pq, a1[[2]], a1[[3, 1, 1]], a1[[3, 1, 2]], a1[[1]]] ] sumsnsquares[RSA250, 5] {12939728750111234257608962548126805776280714145554311976952887652105665290942880515065286493785 653843091970592009510256347174358060619053312425943588008089095230469479676915168784093627987660 27342046542651976916986106637392512950954851030663913587187, 351447907186317343211642979258329126954320918895828050722989458375280300598192867940472019229055 623179931493542366555481983148460724299015966829980417810494952735245566934627686727636686064413 750607290779073735925537404456002481645847848869157806977, the square of these equiv to,-5, mod RSA250} True sumsnsquares[RSA250, 2] {149221662643548489728763750083153100747820875206356872791620279621720311536699163799339067932479 5326563195006058544921285012535390688241249394387155902358869565967616289835595632867566977496990 474814940243132116887666175813509631645946313567741074806, 751908899528113220927249272500819163126 2333367079610125023903372548930596605058754106617309459820814518188930241795525440170088468397198 6425264697557251207834869894201082148795543387681679243685978474259170298361096443566595348441341 1344994168981130, the square of these equiv to,-2, mod RSA250} True
If we manipulate the gettriplesumN[] mathematica routine shown just above, and change the sign within it, we can create:
and from there we can get
At this point, just like the math shown above, we can take the modular square root and come up with
Now if we set and increase our roots by each, then we can come up with
and this is equivalent to:
So while obtaining is really hard the similar but slightly different equation above only takes a few seconds, no matter how big the number is:
Here is the mathematica to obtain
try333N1[pq_, sq3_, sq2_, sq1_, n1_] := Module[{a1, a2, a3, a4, a5, a6, a7, a8, a9, a10}, a1 = Mod[sq2 PowerMod[sq3, -1, pq], pq]; a3 = Mod[(a1^2 - n1) sq3 PowerMod[sq1, -1, pq], pq]; Print[{a3, a1, "the square of these equiv to", n1, " mod RSA250"}]; Print[Mod[a3^2 + a1^2, pq] == n1]; a8 = Mod[a3 + PowerMod[2, -1, pq], pq]; a9 = Mod[a1 + PowerMod[2, -1, pq], pq]; Print[{{a8, a9}, Mod[a8^2 + a9^2, pq] == Mod[a8 + a9, pq]}];] gettriplesumN1[n_, n1_] := Module[{a1, a2, a3, a4, a5, a6, a7, a8, a9, a10}, a2 = IntegerPart[n^(1/2)]; For[a1 = 1, a1 <= 10000, a1++, a3 = RandomInteger[{1, a2}]; a4 = n + n1 a3^2; If[Mod[a4, 4] == 1 && PrimeQ[a4],(*Print[{a3,PowersRepresentations[ a4,2,2]}];*)Break[];];]; Return[{n1, a3, PowersRepresentations[a4, 2, 2]}]] sumsnsquares[pq_, n1_] := Module[{a1, a2, a3, a4}, a1 = gettriplesumN1[pq, n1]; a2 = try333N1[pq, a1[[2]], a1[[3, 1, 1]], a1[[3, 1, 2]], a1[[1]]]] sumsnsquares[337 577, 97225] {110610,75342,the square of these equiv to,97225, mod RSA250} True {{13386,172567},True} Mod[(13386 13385) + (172567 172566), 337 577] = 0 Here is the RSA250 equation for x^2+y^2 mod p*q===x+y sumsnsquares[RSA250, PowerMod[2, -1, RSA250]] {2094270975834518249162826924456669790774040145778878109638331489597260246292415443852225987841131 00517929898398881631794003738057259169123297843871838208407375537019410168737914825570285839917952 705150903661104412013108290750556186049399607111225965, 70653300607618580031176408112794637852756330094007676495780155382933744894865974883920761996452593 05470074951769838581635593362421356811137522604332832547596149502075690596674222812195287293573416 70997725563516418218455582760034662497839268347466776,the square of these equiv to, 10701623251203724806322115364196667815043073575723775088988774604407090117235700683216727595479023 39805496425936235457293843698130960778681523727385260402559528246553343845795009879702846728726115 294662988348735840869034682447349935789247487968748969, mod RSA250} True Here is x and y for x^2+y^2 mod RSA250 === x+y {{1279589422703824305548494228865333760581711372150265319862710609400435036352811612706895358332015 440323426324335117089087847436188219947804821571257098610966903783572754014532924705273132568644067 999813892009840252882142973197906121838647095079974934, 177669533119655828094397561754761316003187065851245427385667901427004646067222981716088037951242827 035250392111321931545740303437309645979527598781854365731914319676091290546243216092237545808345696 5660713912252259087490265207384598287086756316215745},True}
With two items equalling 0, it is possible to divide elements of each against the other, and often the square root of one can be obtained. With I show an example and then show the three square roots that can be obtained from the example:
sumsnsquares[337 577, 97225] {142305,118403,the square of these equiv to,97225, mod 337*577} True 45081(45080)+21179(21178) mod 337*577 equiv 0 {{45081,21179},True} Mod[-45081 PowerMod[21179, -1, 337 577], 337 577]=7756 PowerMod[-(45081 21178 PowerMod[21179 45080, -1, 337 577]), 1/2, 337 577]=7756 Mod[-45080 PowerMod[21178, -1, 337 577], 337 577]=52774 PowerMod[-(45080 21179 PowerMod[21178 45081, -1, 337 577]), 1/2, 337 577]=52774 Mod[45080 PowerMod[21179, -1, 337 577], 337 577]=32522 PowerMod[-(45080 21178 PowerMod[21179 45081, -1, 337 577]), 1/2, 337 577]=32522
Extrapolating from the section just above, we now show that square roots can be taken from any equation
More specifically, the modular square root of:
can be taken.
Examples follow:
set the equation = to 0 Mod[2049 100 + 98 1649, 89 29]= 0 divide two of the components Mod[-2049 PowerMod[1649, -1, 89 29], 89 29]= 1085 Use Mathematica to get the modular square of the following components of the zero equation PowerMod[-2049 98 PowerMod[100 1649, -1, 89 29], 1/2, 89 29]= 17 Now multiply 17 by the square root of 1 mod 89 29 to get the other square root. Mod[17 2493, 89 29]=1085
Combining this new definition of a square root with work previously done at User:Endo999#A_Close_Call_ON_RSA, which shows that given:
that
we can use the two equations on the same numbers to get
The mathematica follows:
1034, 5^23, y, and 11^23 must have modular square roots y1 = Solve[1034 5^23 + y 11^23 == 0, {y}, Modulus -> 8501 9001] {{y -> 37670000}} Now use the first equation (from this section) to get a type of square root Mod[-1034 PowerMod[11^23, -1, 8501 9001], 8501 9001]=7288984 Mathematica shows this square root is correctly taken PowerMod[-1034 37670000 PowerMod[5^23 11^23, -1, 8501 9001], 1/2, 8501 9001]=7288984 Now set up the second equation (from the A Close Call On RSA section) Mod[1034 5^22 PowerMod[37670000 11^22, -1, 8501 9001], 8501 9001]=15303498 Mathematica confirms this equation is correct. Mod[PowerMod[1034, 1/23, 8501 9001] PowerMod[37670000, -1/23, 8501 9001], 8501 9001]=15303498 Another definition of the first equation(306035 is the square root of 1 mod 8501*9001) AA=Mod[306035 PowerMod[-1034, 23/46, 8501 9001] PowerMod[37670000, 23/46, 8501 9001] PowerMod[ PowerMod[5^23, 1/2, 8501 9001] PowerMod[11^23, 1/2, 8501 9001], -1, 8501 9001] , 8501 9001]=7288984 get rid of some of the powers Mod[7288984 5^11 11^11 , 8501 9001]=51923275 we now have Mod[PowerMod[-1034, 23/46, 8501 9001] PowerMod[37670000, 23/46, 8501 9001] PowerMod[ PowerMod[5, 1/2, 8501 9001] PowerMod[11, 1/2, 8501 9001], -1, 8501 9001] , 8501 9001]=51923275 now reduce some more powers Mod[51923275 PowerMod[15303498, -11, 8501 9001], 8501 9001]=68983501 Mathmatica confirms again what we have created BB=Mod[306035 PowerMod[-1034, 1/46, 8501 9001] PowerMod[37670000, 45/46, 8501 9001] PowerMod[ PowerMod[5, 1/2, 8501 9001] PowerMod[11, 1/2, 8501 9001], -1, 8501 9001] , 8501 9001]=68983501 BB is, for the most part, the 23rd root of AA(see previous equation)(I leave it to the reader to divide BB by 37670000 so that PowerMod[37670000, 45/46, 8501 9001] becomes PowerMod[37670000, -1/46, 8501 9001])
So, by algebraic manipulation we have managed to take the 23rd root of the first equation, which only had square roots within it.
There is a possibility that this last equation is a combination of the roots of 11 and 5 but I have not been able to ascertain what that equation might be at the present moment.
If we call our Mathematica routine smsnsquares with the sum 4+1/2 and we add one to the x and y returned, we then have
or
sumsnsquares[337 577, 4 + PowerMod[2, -1, 337 577]] {41259,97442,the square of these equiv to,97229, mod RSA250} Add one to the numbers below to get x^2+y^2 mod 337*577 equiv 3(x+y) {{138484,218},False} Mod[138485^2 + 219^2, 337 577]= 27214 Mod[3 (138485 + 219), 337 577]= 27214 Mod[138485 (138485 - 3) + 219 (219 - 3), 337 577]= 0
We can easily create the sum of four squares equivalent to 0 for any size p*q modulus via the following math(Please see Mathematica routines in sections above):
sumsnsquares[337 577, PowerMod[-2, -1, 337 577]] {124557,79914,the square of these equiv to,97224, mod 337*577} True {{27333,177139},False} Mod[27332^2 + 27333^2 + 177138^2 + 177139^2, 337 577]= 0
Since the
then we are close to having a way to create modular Pythagorean Quadruples, however, we have to deal with sign issues.
It is unusual to have the sum of two adjacent squares equivalent to 0 mod p*q. I am unaware if this is new math.
can yield the modular square root of . This is done by creating the sum and then adding this to the to create From there a modular square root can easily be taken.
The mathematica with an example of this follows:
sumsnsquares[ 337 577, 1] {73974,127344,the square of these equiv to,1, mod RSA250} True Thus 73974^2+127344^2 mod 337*577 equiv 1 Mod[73974^2 + 127344^2, 337 577]= 1 Now make the D term in D*x^2+y^2==0 Mod[PowerMod[73974^2, -1, 337 577] (-1) + 1, 337 577]= 193668 Prove the 0 equation holds Mod[193668 73974^2 + 127344^2, 337 577]= 0 Now get the modular square root of the -D term Mod[193668 73974 PowerMod[127344, -1, 337 577], 337 577]= 122213 see that the square root mod 337*577 of -193668 has been found Mod[-122213^2, 337 577]= 193668 The same procedure can be done for the 127344^2 as well.
This works for any size modulus in very quick time. Thus lots of modular square roots can be found, from the square to the root, but we still cannot determine the square to have its root taken.
Taking the idea of converting to as in the previous section, we can therefore take, given the following equation:
we can derive the following cube root
via
The following Mathematica example shows this to be true:
make the sum of cubes equation, any n will do Mod[101^3 + 205^3, 89 29]= 229 create the D in D*x^2+y^2 mod p*q===0 Mod[PowerMod[101^3, -1, 89 29] (-229)+1, 89 29]= 702 confirm the equation is set Mod[702 101^3 + 205^3, 89 29]= 0 derive the cube root of 702 Mod[702 101^2 PowerMod[205^2, -1, 89 29], 89 29]= 1889 ensure that 1889^3 is 702, as it is Mod[1889^3, 89 29]= 702
This method could happen for high powers, even powers used as the public keys of RSA.
Using RSA260 as the modulus I will obtain the cube root of
RSA260 = 2211282552952966643528108525502623092761208950247001539441374\ 8319128822941402001986512729726569746599085900330031400051170742204560\ 8592763579537571859542988389587092292384910067030341246205457845664136\ 64540684214361293017694020846391065875914794251435144458199 In[2]:= Mod[(PowerMod[2, -3, RSA260] (-9) + 1) 2^3 + 1, RSA260] Out[2]= 0 In[3]:= root = (PowerMod[2, -3, RSA260] (-9) + 1) Out[3]= -2487692872072087473969122091190450979356360069027876731871546\ 6859019925809077252234826820942390964923971637871285325057567084980130\ 9666859026979768341985861938285478828933023825409133901981140076372153\ 72608269741156454644905773452189949110404143532864537515474 In[4]:= Mod[root, RSA260] Out[4]= 19348722338338458130870949598147952061660578314661263470112029\ 7792377200737267517381986385107485282742001627887774750447743994289907\ 5186681320953753771001148408887057558367963086515485904297756149561195\ 6473098687566131390482268240592182641425444970005751400924 In[7]:= f1 = Mod[(root 2^2), RSA260] Out[7]= 11056412764764833217640542627513115463806044751235007697206874\ 1595644114707010009932563648632848732995429501650157000255853711022804\ 2963817897687859297714941947935461461924550335151706231027289228320683\ 2270342107180646508847010423195532937957397125717572229099 In[9]:= Mod[f1^3, RSA260] == Mod[root, RSA260] Out[9]= True
Repeating the same equation as just above, this time with the RSA power of 23:
In[10]:= n = Mod[2^23 + 1^23, RSA260] Out[10]= 8388609 In[11]:= Mod[(PowerMod[2, -23, RSA260] (-n) + 1) 2^23 + 1, RSA260] Out[11]= 0 In[16]:= rsa = (PowerMod[2, -23, RSA260] (-n) + 1) Out[16]= -\ 1823036614912868011712788026285598289907112664939832406605855746395330\ 5566418939802808400542422831632117602012801069837273093805236506512125\ 1801795511752469924336751658952653852057231684651411662361016592378816\ 749576517216160535917358794858457784435830494823917971195 In[17]:= Mod[rsa, RSA260] Out[17]= 3805381513377872844851901753342547023867551837548099699404447\ 4287046405684922356662404431707833791366785067149913345336758579896786\ 2258467168551258278748586904196775629954257397251522922050639261510719\ 084671572744963395445500749989052758071563694875589134555 In[18]:= f1 = Mod[(rsa 2^22), RSA260] Out[18]= 1105641276476483321764054262751311546380604475123500769720687\ 4159564411470701000993256364863284873299542950165015700025585371102280\ 4296381789768785929771494194793546146192455033515170623102728922832068\ 32270342107180646508847010423195532937957397125717572229099 In[19]:= Mod[f1^23, RSA260] == Mod[rsa, RSA260] Out[19]= True Thus the 23rd root of ((1/(2^23)(-8388609))+1 is found mod a large number.
Using Pythagorean Triples as the two squares such as:
we can find the square roots of adjacent squares:
The mathematica showing an example of this follows:
set up the Pythagorean Triple Mod[3^2 + 4^2, 89 29]=25 Determine the root to be found Mod[PowerMod[3^2, -1, 89 29] (-25) + 1, 89 29]=285 Ensure the sums of squares equaling zero is met Mod[285 3^2 + 4^2, 89 29]=0 Ensure the sums of squares equaling zero is met for the number previous. (use the third square of the Pythorgorean Triple for this) Mod[284 3^2 + 5^2, 89 29]=0 Find the root of -285 Mod[285 3 PowerMod[4, -1, 89 29], 89 29]=859 Ensure the root is correct Mod[-859^2, 89 29]=285 Find the root of the square previous to this (-284) Mod[284 3 PowerMod[5, -1, 89 29], 89 29]=1719 ensure the root is correct Mod[-1719^2, 89 29]=284 Show this root is result of two squares Mod[PowerMod[3, -1, 89 29] (-5), 89 29]=1719
Dickson says at Vol II p 420[51]:
Matsunago,[52] in the first half of the eighteenth century, noted that has the solution , , . If , has the solution , , provided , which is of the preceding type.
I have verified through Mathematica that given given one that is easily made.
Dickson says at Vol II p 433[53]:
This math looks too difficult to set for p*q, but by setting it should be possible to establish a N and factor this with the Euler factorisation algorithm shown above that works with .
Theoretically, any large but random number could be factored this way, but I tried Gerardin's equations in Mathematica and there was no solution:
Solve[ x == m^2 + n^2 + h p^2 - 2 m (n + h p) && z == m^2 + n^2 - h p^2 + 2 n (h p - m) && x == n^2 + h p^2 - h m^2 && z == n^2 - h p^2 + h m^2 + 2 h n (p - m) & y == n^2 + h p^2 - m^2 && t == m^2 + h p^2 - n^2 + 2 p (n - m) && y == n^2 + h p^2 + h m^2 - 2 m (n + h p) && t == h p^2 + h m^2 - n^2 + 2 p (n - h m) && nn == x^2 + h y^2 && nn == z^2 + h t^2 && m == 100 && n == 201 && p == 307 && h == 7 , {nn, x, y, h, z, t}, Integers] {}
This often happens with Girardin's work. He offers exciting solutions but they don't actually work for any but very small numbers.
Again, in Dickson's "History Of The Theory Of Numbers" vol 1 p 367, Dickson writes:
E. Barbette[56] noted that has a divisor if and only if has that divisor. Set , . Then
- ,
Eliminating , we get a quadratic for . Its discriminant is a quadratic function of which is to be made a square. Similarly for , .
A. Gerardin[57] developed Barbette's method
Let's get examples for this and see that method works not just for but for
Now, by symmetry, lets try for a
So when and , when is low, then p*q is vulnerable!
Let's try out a modulus that is not , for instance.
Mod[11287, 83]= 82 20113 11287= 227015431 Mod[227015431, 83]= 56 (227015431 - 56)/83= 2735125 (11287 + 1)/83= 136 GCD[2735125 + 56 136, 20113 11287]= 11287
So Barbette's method can be used for any modulus where
Taking we can see that a change in sign from + to - effects the change.
12119 mod 83 === 1 12118/83= 146 12119 20113= 243749447 Mod[243749447, 83]= 27 (243749447 - 27)/83= 2936740 note the change in sign from + to - GCD[2936740 - 27 146, 12119 20113]= 12119
Since any factor of x=(p-1) will ensure that and common factors of p-1 and q-1 are always in the factorisation of then candidates for are available this way, although b still needs to be small as in ()
In [58]Dickson states:
C. G. J. Jacobi,[59] as an application of cyclotomy, found that if is a prime, we have , where a is the absolutely least residue (between and modulo p of , and that this residue is . If is a prime, then , where L is the absolutely least residue modulo p of and this residue is .
This hints that is solvable for four times large 1 mod 12 primes. Accordingly I show the Mathematica routine below that successfully derives this equation for 1000 bit 1 mod 12 primes. It takes a few seconds to do.
try11[] := Module[{a1, a2, a3, a4, a5, a6, a7, a8, a9, a10}, For[a1 = 2^1000 + 1, a1 < 2^1000 + 1000, a1++, a2 = a1 12 + 1; If[! PrimeQ[a2], Continue[];]; a3 = PowersRepresentations[a2, 2, 2]; a4 = Solve[x^2 + 27 y^2 == 4 a2 && x > 0 && y > 0, {x, y}, Integers]; Print[{"Prime", a2}]; Print[{"Sum Of Squares", a3}]; Print[{"X^2+27 y^2", a4}]; ]; ] {Prime,128581032862352078513811005887200217267368577404664032893250046604442126134992334699183805457883502975311360750106 3776190224574342830776852318149308963828976472148132978907718250528952607484537025354501858365576998029832952087852107099 86527352924754974854357732238506011925157979831492642046468016843589} {Sum Of Squares,{{626176556066997691854450532831018756333590716455819271880741717469457186893346652690094266532709590547645302626723583717 2409867108904549850010086427758,9453640829096453890954090946807600146759773306685861265129667222548049489226855908180620573389745817858848 929834172863446342124609028102267697002796545}}} {X^2+27 y^2,{{x->125780689710630818693710076905385131316601197830306628212917333498816475920212405629607290620564189949504158377333248044938167781187041823 28458326488897,y->363173416595569966074036281225052388948457559288277127129856887502803553005372934246598348106154270506157103803816458892861203322612907285 8313084955731}}}
The above routine will work with the square of the 4*prime as well, in other words a2*a2*16 instead of a2*4.
Showing that Mathematica can also do the equation quickly when note the following Mathematica procedure and its invocation.
try112[] := Module[{a1, a2, a3, a4, a5, a6, a7, a8, a9, a10}, For[a1 = 2^1000 + 1, a1 < 2^1000 + 1000, a1++, a2 = a1 28 + 1; If[! PrimeQ[a2], Continue[];]; a3 = PowersRepresentations[a2, 2, 2]; a4 = Solve[x^2 + 7 y^2 == a2 && x > 0 && y > 0, {x, y}, Integers]; Print[{"Prime", a2}]; Print[{"Sum Of Squares", a3}]; Print[{"X^2+7 y^2", a4}]; Break[]; ]; ] try112[] {Prime,3000224100121548498655590137368005069571933472775494100842501087436982943149821142980955460683948402757265084169148811110524006 79993847932207568172091560094510167897695078467591790088941746391972582717100285301299540294355487165491656635230490157761607993501375 223180694492035286273482831441758705949137} {Sum Of Squares,{{1150806314968068727146123357056885619469649979028849850844196453181801798217270923100224969011009351667664622170718763364665983851966 1133366287153343544,1294553562256565224483621421076232660055995172660705961188957840298454705954113931007696103856465599582733326595695 7131164756911083919843754054197876649}}} {X^2+7 y^2,{{x->157304830171714332605677866092018027280370023779927555463574103219979718292899144978579620380536264818784075565328449845301220705470 13154003170125103375,y->274055036335602726761027521599993587003300808005972618065115577057055135899598819194386061044300944545681499566865221260921239568918 9280816958899288596}}}
The above routine will work with the square of the prime as well, in other words a2^n instead of a2.
I was unable to get a quick answer for the following in Mathematica. Mathematica returned a nil answer quickly:
a4 = Solve[x^2 + 10001 y^2 == a2 && x > 0 && y > 0, {x, y}, Integers];
In an unpublished proof by Euler which is shown by the Mathematica help pages put together by Eric Weisstein [60]
In an unpublished proof, Euler showed that the quadratic Diophantine equation
has a unique solution for every positive n>=3 in which x and y are both odd and positive (Engel 1998, p. 126)[61]. Rather amazingly, these can be given analytically by
which is related to the norms of elements of the ring of integers in the quadratic field Q(sqrt(-7)) which exhibits unique factorization (Hickerson 2002). [62] The first few solutions (x,y) for n=1, 2, 3, ... are (1, 1), (1, 3), (1, 5), (3, 1), (1, 11), (5, 9), (7, 13), (3, 31), ... (OEIS A077020 and A077021).
I was able to derive this equation using Mathematica. If Mathematica can, as seen above, can derive .
So you can derive Euler's equation above in the modular domain, in Mathematica for large primes, via the following Mathematica procedure:
try113[pq_] := Module[{a1, a2, a3, a4, a5, a6, a7, a8, a9, a10}, a6 = 0; a7 = 0; a8 = 0; a9 = 0; For[a1 = 2^10 + 1, a1 < 2^10 + 1000, a1++, a2 = 7 pq + 2^(4 + a6); a6 += 2; a9++; a2 = 7 pq + 2^(2 + a6); If[Mod[a2, 7] != 1, Continue[];]; a7++; If[! PrimeQ[a2], Continue[];]; a8++; a4 = Solve[x^2 + 7 y^2 == a2 && x > 0 && y > 0 , {x, y}, Integers]; Print[{"Prime", a2, (2 + a6)}]; Print[{"X^2+7 y^2", a4}]; (*Return[a4]; Break[];*)]; Print[{a9, a7, a8}];] ensure that p*q has square root of 7 try113[401 113] {Prime,281474977027847,48} {X^2+7 y^2,{{x->11020820,y->4781161}}} {{x -> 11020820, y -> 4781161}} now divide by 2^24 to get trigometric sums this is supposed to be |sin[ntan^{-1}(\sqrt{7})]|/squarerootof7 Mod[4781161 PowerMod[2, -24, 401 113], 401 113]=41533 this is suppose to be |cos[ntan^{-1}(\sqrt{7})]| Mod[11020820 PowerMod[2, -24, 401 113], 401 113]=38882 get square root of 7 to check sums PowerMod[7, 1/2, 401 113]=4326 now make sure that sin^2[alpha]+cos^2[alpha]==1 Mod[(4326 41533)^2 + 38882^2, 401 113]= 1
I was unable to go further into the complicated trigonmetic identity shown. Also, I was able to do something similar with the code that finds . But I have been unable to prove it is a trigonmetric identity.
With Euler's unpublished identity shown above, it seems that this may not be a trigometric identity in modular arithmetic.
If the Sin is a real number then the norm of it is itself. Thus we should have a value.
With knowledge of we can easily create
We can also use Chebychev polynomials, which I have verified work in modular arithmetic.
Since we now have and we should be able to divide and get the modular square root of 7.
I have done this equations and we do not get anything that is the modular square root of 7. I have either misapplied the equations, or the norm of the trigonometric identities is not themselves, or Euler's math does not work in modular numbers.
Ah, my mistake is that one of the squares is even, they both have to be odd, according to Weiss.
This math may not work for modular arithmetic as is the ARCTAN function and the resulting Sin[\Theta] may not be expressable as a rational number and thus may not be part of the p*q field.
As far as the Weiss quote goes, it has two references for the unpublished Euler equation. I have checked the Engel[63] reference and it does not have the trigometric identity claim that Weiss gives. I was unable to get a hold of the Hickerson reference[64]. It is in an email group and I couldn't retrieve it. It would be interesting to see what that reference had to say regarding the trigometric identities because I cannot get them to work in mod p*q space.
With sought then possibly the sides of the triangle are and the sine of this triangle would be or . I used p*q combinations that had both square roots of both 7 and 8, but could not make the trigometric identity in p*q space.
Get \sqrt{7}*sin[2*\Theta] Mod[7 41533 2 38882, 401 113]=27890 Use Chebychev polynomials to get Sin[2*\Theta] Mod[((41533 7)^2 4 - 7) PowerMod[7, -1, 401 113], 401 113]=6722 try to get \sqrt{7}\bmod{p*q} Mod[(27890 PowerMod[6722, -1, 401 113]), 401 113]= 24083 show we don't have square root of 7 Mod[24083^2, 113 401]= 29802
On the possibility that symmetry is available here, I have been able to get two odd X and Y values for the equation: which is the other equation Jacobi said could be solved.
However, the math shown above, replicated onto the does not work either. Either I have misapplied the math, the math does not work for , the math does not work for modular arithmetic, or the norm of the trigometric identities is not the same as the identities.
Dickson says at [65] that Jacobi stated:
C. G. J. Jacobi[66] stated that, if p is a prime 4*n+1, and then:
- ,
where ranges over the quadratic residues, between 0 and p/2, of p. If q is a prime 8n+3, and , then
This is a difficult statement to read. Dickson actually means by "ranges over the quadratic residues" include only the nonquadratic numbers.
I have confirmed that the first of the two equations has analogues in modular arthmetic. And also that Mathematica can find integer solutions to the problem. Mathematica cannot find integer solutions to the second problem.
Here is an example of the first equation:
Solve[x^2 - 5 y^2 == -4 && x > 0 && y > 0, {x, y}, Integers] {{x -> 1, y -> 1}, {x -> 4, y -> 2}, get modular square root of 5 mod 89*29 PowerMod[5, 1/2, 89 29]=337 2 is the only nonquadratic between 1 and 2 inclusive for p=5/2 Sin[2 Pi/5]^2 5/8 + Sqrt[5]/8 make the right side of the equation above Mod[8 (5 + 337) PowerMod[8, -1, 89 29], 89 29]=342 make the left side of the equation above Mod[ 337 (1 + 1 337) , 89 29]= 342
I can't find the Hickerson reference for the original equation of this section. However, Jacobi's equation above is pretty similar, and can be made to work. The answer (5+5^(1/2)) has some resonnance with Hickerson's claim that the trigonmetic identity is in the field of
Adolf Kunerth's little known 1878 Modular Square Root Algorithm, as detailed in his paper[67][68]. Dickson's reference isn't enough to reconstruct the algorithm, but Kunerth's 1878 paper is. I was able to get copies of these two papers (one on the Quadratic Equation, and the other on the Modular Quadratic problem) from the Ernest Mayr Library at Harvard University. Thanks to Mary Sears for obtaining the copies.
I was able to confirm that Kunerth's four examples of solving the modular quadratic problem do work, and I have been able to create four examples where his algorithm does work. One such example that actually finds the square root of B mod (P*Q mod B) instead of B mod P*Q is shown below. I have been able to find the modular square root of B mod N in 3 other examples. All four examples require that C in the quadratic (A*x^2+B*x+C) be a natural square. You do not need to factor the modulus N to get the modular square root.
The algorithm is a fascinating algorithm in that it would be practible for large numbers if one can solve a quadratic equation of , which is often hard to solve. However, most of the equations are not modular and the one modular computation for the problem is . So the residue becomes the modulus and this is often much easier to factor than the hard semiprime of the original problem. Thus, I conclude, this equation would be solvable, for large numbers, and it is the resulting quadratic equation which makes the computation infeasible.
A naiive explanation of the algorithm follows:
As I said, the algorithm is a fascinating algorithm as it involves mostly sums and quadratic equations. If you can solve the quadratic equation the algorithm does seem to work. (An attempt of mine to solve the quadratic equation by making it modular did not work).
It looks as if is a square then the algorithm is feasible, even for large numbers.
I found an example that fits this qualification for when Kunerth's algorithm can work. the square root of 4289 mod 2048764 === 4049. The square root of -2048764 mod 4289 is 2095. If we take the quadratic that this produces, we, indeed, see that C in the Quadratic is a square.
Expand[((4289 z + 2095)^2 + Mod[2048764, 4289])/4289] 1024 + 4190 z + 4289 z^2
So W=32 and V=2095.
Solving for alpha and beta we get
Solve[a == 32 (2095 + 32 b), {a, b}, Integers] {{a -> ConditionalExpression[480 + 1024 C[1], C[1] \[Element] Integers], b -> ConditionalExpression[-65 + C[1], C[1] \[Element] Integers]}}
Thus alpha can be 480 and beta -65.
We do get a factor for the equation given above to discover X.
alpha =480 beta = -65 xx = Factor[alpha^2 x^2 + (2 alpha beta - Mod[2048764, 4289]) x + (beta^2 - 4289)] (-64 + 225 x) (1 + 1024 x) However, this X does not recover Y or the modular square root 4289^(1/2) mod 2048764 Mod[alpha 64 PowerMod[225, -1, 2048764] + beta, 2048764] 1775667
Therefore, my first attempt to make an example of Kunerth's algorithm, besides his examples, didn't work.
Good news, I was able to make Kunerth's algorithm work, for my example, when I changed the modulus from 2848764 to 2911 or Mod[2048764, 4289]=2911.
The math follows:
alpha=480 beta=-65 Mod[alpha 64 PowerMod[225, -1, 2911] + beta, 2911] = 1430 Mod[alpha (-1) PowerMod[1024, -1, 2911] + beta, 2911] = 1481 Mod[1481^2, 2911]= 1378 Mod[1430^2, 2911]= 1378 and 1378 + 2911= 4289 which is the original square so my example works for 4289^(1/2) Mod(2848764 mod 4289] so two roots are found 1481 and 1430 So I have found an example where Kunerth's method does work in a sense. If I had found a quadratic that worked with the full original modulus, 2848764 instead of mod[2848764, 4289]=2911 then I would have found the square root of 4289^(1/2) mod 2848764. 2911 is a semiprime so it would normally have to be factored before the square root could be found by other methods. FactorInteger[2911]= {{41, 1}, {71, 1}}
If the modula is of the form, no matter how big it is,
then the resulting associated quadratic will have C as a square and you can take the modular square root of 5 easily.
If the modula is of the form, no matter how big it is,
then the resulting associated quadratic will have C as a square and you can take the modular square root of 3 easily.
Details and examples at[69]
The talk page of Talk:Kunerth's_algorithm shows how to get the modular square root of 67*y mod RSA260. Here we will show how to get the square root of y*89 29 mod 89 29 (89 29+13) (in small numbers).
It's quite complicated but here is the mathematica with some notes
How to find square root of 139 mod 89 29 (89 29+13) times 89 29 given: square root of 67*139 mod 89 29 square root of 67 mod 89 29+13 square root of 139 mod 89 29+13 Output: square root of 139*89*29 mod 89 29(89 29+13) take square roots in modulus near 89 29 (which is hopefully a prime) In[5]:= PowerMod[67, 1/2, 89 29 + 13] Out[5]= 135 we know this, it is given by Kunerth's modified routine In[4]:= PowerMod[67 139, 1/2, 89 29] Out[4]= 694 In[6]:= PowerMod[67 139, 1/2, 89 29 (89 29 + 13)] Out[6]= 151407 take chinese remainder and get a sum for combined modulus In[6]:= x3 = ChineseRemainder[{694, 135}, {89 29, 89 29 + 13}] Out[6]= 111677 we don't know this but will get this sum times 89 29 at end of procedure In[15]:= PowerMod[139, 1/2, 89 29 (89 29 + 13)] Out[15]= 557621 Show the equation that chinese remainder theorum has gotten us In[2]:= Mod[ PowerMod[67, 1/2, (89 29 + 13) ( 89 29)] + PowerMod[67 , 1/2, ( 89 29) (89 29 + 13)] (( (557621 - 1)) (89 29 + 13)) PowerMod[13, -1, (89 29) (89 29 + 13)], (89 29) (89 29 + 13)] Out[2]= 111677 get a sum for 67*139 in full modulus(we can do this) In[26]:= Mod[PowerMod[67 , 1/2, 89 29 (89 29 + 13)] (557621), 89 29 (89 29 + 13)] Out[26]= 978893 redo the sum In[25]:= Mod[ PowerMod[67, 1/2, 89 29 (89 29 + 13)] + PowerMod[67 , 1/2, 89 29 (89 29 + 13)] (557620), 89 29 (89 29 + 13)] Out[25]= 978893 multiply by difference between the two modula In[36]:= Mod[ 13 PowerMod[67, 1/2, (89 29 + 13) ( 89 29)] + PowerMod[67 , 1/2, ( 89 29) (89 29 + 13)] (( (557621 - 1)) (89 29 + 13)), (89 29) (89 29 + 13)] Out[36]= 1451801 substract two sums In[37]:= Mod[1451801 - 13 978893, 89 29 (89 29 + 13)] Out[37]= 2116420 get the new answer In[35]:= Mod[PowerMod[67 , 1/2, 89 29 (89 29 + 13)] (557620) 89 29, 89 29 (89 29 + 13)] Out[35]= 2116420 square In[40]:= Mod[2116420^2 PowerMod[67, -1, 89 29 (89 29 + 13)], 89 29 (89 29 + 13)] Out[40]= 2720374 this is result of squaring after dividing by 67 In[44]:= Mod[557620^2 (89 29)^2, 89 29 (89 29 + 13)] Out[44]= 2720374 multiply by former sum and divide by 67 In[42]:= Mod[2116420 978893 PowerMod[67, -1, 89 29 ( 89 29 + 13)], 89 29 (89 29 + 13)] Out[42]= 588468 this is the new equation In[43]:= Mod[557620 557621 89 29, 89 29 ( 89 29 + 13)] Out[43]= 588468 subtract two sums to get In[45]:= Mod[588468 89 29 - 2720374, 89 29 ( 89 29 + 13)] Out[45]= 3019770 we have 1 less than square root of 139 with 89 29 square as multiplier In[46]:= Mod[557620 (89 29)^2, 89 29 ( 89 29 + 13)] Out[46]= 3019770 play with the modulus In[51]:= Mod[ 2 3019770 PowerMod[89 29 - 13, -1, 89 29 ( 89 29 + 13)/2], 89 29 (89 29 + 13)/2] Out[51]= 3115267 we now have 1 less than the square root of 139 times 89 29 In[52]:= Mod[557620 89 29, 89 29 ( 89 29 + 13)/2] Out[52]= 3115267 add 89 29 to get square root of 139 times 89 29 In[53]:= Mod[557620 89 29 + 89 29, 89 29 ( 89 29 + 13)/2] Out[53]= 3117848 we have final sum In[55]:= Mod[557621 89 29, 89 29 ( 89 29 + 13)/2] Out[55]= 3117848
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.
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 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
I finally found out how to get the two roots of 5 mod 89*29, which allows the p*q modulus to be factored easily.
Any 1 mod 4 prime (which is the sum of two squares) can be used to factor p*q, if you can solve two equations (that I admit I can't solve for big numbers yet).
There are two equations to solve for the root of 5, which is the sum of two squares, 1 and 4.
and
If you solve for x in the two equations so that the two modula are both multiples of P*Q, then you will often get the two different square roots of 5 (in this case). With the two different roots of 5, factoring p*q is easy.
Look at the mathematica below where these equations are solved and then used in the Kunerth method to get the two different roots of 5 mod 89*29, which are 1265 and 337.
In[2]:= Solve[((x)^2 - 1)^2 + 5 (2* 1 *x)^2 == 89 29, Modulus -> 89 29] Out[2]= {{x -> 134}, {x -> 269}, {x -> 311}, {x -> 443}, {x -> 714}, {x -> 888}, {x -> 1023}, {x -> 1113}, {x -> 1468}, {x -> 1558}, {x -> 1693}, {x -> 1867}, {x -> 2138}, {x -> 2270}, {x -> 2312}, {x -> 2447}} In[3]:= Solve[4 ((x)^2 - 1)^2 + 5 (2 1 x)^2 == 89 29, Modulus -> 89 29] Out[3]= {{x -> 73}, {x -> 217}, {x -> 317}, {x -> 495}, {x -> 607}, {x -> 785}, {x -> 1029}, {x -> 1262}, {x -> 1319}, {x -> 1552}, {x -> 1796}, {x -> 1974}, {x -> 2086}, {x -> 2264}, {x -> 2364}, {x -> 2508}} In[7]:= w1 = ((5 (134^2 - 1)^2 + 5 (2* 1* 134)^2)/5)^(1/2) Out[7]= 17957 In[8]:= w2 = ((5 (73^2 - 1)^2 + 5 (2 *1 *73)^2)/5)^(1/2) Out[8]= 5330 In[6]:= v1 = 2 (134^2 - 1) Out[6]= 35910 In[26]:= v2 = (73^2 - 1) Out[26]= 5328 In[15]:= mod1 = (134^2 - 1)^2 + 5 (2 *1* 134)^2 Out[15]= 322741145 In[13]:= Mod[mod1, 89 29] Out[13]= 0 In[16]:= mod2 = 4 (73^2 - 1)^2 + 5 (2 *1* 73)^2 Out[16]= 113656916 In[17]:= Mod[mod2, 89 *29] Out[17]= 0 In[27]:= Solve[a == w2 (v2 + w2 b), {a, b}, Integers] Out[27]= {{a -> ConditionalExpression[28398240 + 28408900 C[1], C[1] \[Element] Integers], b -> ConditionalExpression[C[1], C[1] \[Element] Integers]}} In[19]:= alpha1 = 322382021 Out[19]= 322382021 In[20]:= beta1 = -1 Out[20]= -1 In[28]:= alpha2 = 28398240 Out[28]= 28398240 In[29]:= beta2 = 0 Out[29]= 0 In[24]:= Timing[ xx1 = Factor[ alpha1^2 x^2 + (2 alpha1 beta1 - mod1) x + (beta1^2 - (((5))))]] Out[24]= {0.001582, (-4 + 322310209 x) (1 + 322453849 x)} In[30]:= Timing[ xx2 = Factor[ alpha2^2 x^2 + (2 alpha2 beta2 - mod2) x + (beta2^2 - (((5))))]] Out[30]= {0.000982, (-5 + 28387584 x) (1 + 28408900 x)} In[31]:= y201 = Mod[alpha1 (-1 PowerMod[322453849, -1, 89 29]) + beta1, 89 *29] Out[31]= 1265 In[32]:= Mod[y201^2, 89 *29] Out[32]= 5 In[33]:= y201 = Mod[alpha2 (-1 PowerMod[28408900, -1, 89 29]) + beta2, 89 *29] Out[33]= 337 In[34]:= Mod[337^2, 89* 29] Out[34]= 5 In[35]:= GCD[Mod[1265 PowerMod[337, -1, 89 *29], 89* 29] + 1, 89 *29] Out[35]= 89 In[36]:= GCD[Mod[1265 PowerMod[337, -1, 89* 29], 89* 29] - 1, 89* 29] Out[36]= 29
This procedure above is not a deterministic way to get the two modular square roots. Sometimes it returns the same root.
Is the Kunerth method a case of equivalent squares, in that the quadratic equation essentially presents as two equivalent squares.
My current answer is: Usually no, but close, sometimes it is.
For instance to take the root of 5 the quadratic is but the modulus for this quadratic is either or . Thus Kunerth's method is not usually equivalent squares. It may be equivalent squares for actual natural squares as in .
If you set x so that the modulus is mod 0 for the modulus you are seeking to solve for, then
I conclude that Kunerth's algorithm is an important, although limited in scope, modular square root algorithm.
It requires that C in the resulting quadratic Ax^2+Bx+C be a natural square, but I have shown that once you get this result that the square root can be found, in my example of a residue of the original modulus.
I have also shown in the example given above that Kunerth's algorithm can find one square root of a semiprime without factoring the semiprime. And once the quadratic with the natural square concerning C is found, it is probably quick to find the root.
The Quadratic equation that must be solved is equivalent to p*z^2-x^2 mod x*y===0, and so the square root associated can be solved in other ways than Kunerth's. However, with the Pythagorean Theorum it can be shown, for instance, that certain formula for modula can make taking the root of certain residues easy. Such as modula of x^2+x-1 allow the root of residue 5 to be taken easily using Kunerth. Endo999 (talk) 21:06, 26 February 2023 (UTC)
There is very little information on Adolf Kunerth. He was an Austrian, active between 1870s and 1880s. He was a professor of a German/Austrian university as well as being an engineer. Apparently he built a bridge in the former Yugoslavia.
Apparently, in 1869 he was an instructor at a training institute in Troppau, in today's Czech republic. Then this was a German speaking area of Austria. He may have been a professor of engineering at Brun (perhaps the Karlo university) in the 1870s when he published his mathematics, for which he is known today. After this he became a head engineer in Bosnia. So it is possible that his math was a second career for him and he was primarily an engineer.
Because there is so little personal information on Adolf Kunerth, and because his method is the most powerful modular square root algorithm known, it is possible that Kunerth is an alias for a more well known person.
However, Mary Sears, of the Ernest Mayr Library at Harvard University, who knows German, says the journal the paper is published in became the Royal Austrian Society journal, so it is a prestigious journal and it was meant to be seen. The publication is not meant to be kept from the academic world. It appeared at Harvard University in 1906.
The modular square root algorithm would have been an obvious diplomatic or military cipher in the precomputer age, since a mechanical calculator could have computed it.
It is strange that the only English language reference to the Kunerth algorithm is in Dickson's 1921 Theory of Numbers(vol ii, p382-384). 144 years have passed since its publication, and you could help your career by publicising it. As it is the only algorithm known to take the modular square root of composite modula without factoring the modulus.
Translating from the German at [70]
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 Petzel used his name for various reasons that are unknown, to publish Petzel's math on the modular square root algorithm. Petzel 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. The Theory of Numbers by Dickson only has J. Petzval once in the author's index and this is only in a footnote. J. Petzval wasn't known for number theory. He did have a mathematician brother, named Petrol. It is possible that the math is Petrol Petzval's and not Joseph Petzval's. Petrol, better known as [| Otto Petzal] wrote several high school mathematical books in Hungaria, so it is more likely that Otto gave the lecture in Brun to a high school audience than Joseph, but Otto is not known for independent math. Endo999 (talk) 00:56, 31 October 2022 (UTC)
and , if x can be found then with Kunerth the modular square root of 5 can be found.
Both are unsolvable in the P*Q modula space.
We however can get an answer for if the modulus is a prime (often we can do this).
The two answers that will be found will be and . I can't get further than this however, this happens for both quadratic equations shown above. One of them, the first, will have and actually.
The mathematica shown below will show this effect.
In[28]:= Solve[x^4 + 18 x^2 == 0, {x}, Modulus -> 12 89 29 - 1] Out[28]= {{x -> 0}, {x -> 0}, {x -> 4528}, {x -> 26443}} In[2]:= Solve[x^4 + 18 x^2 + 1 == 0, {x}, Modulus -> 89 29] Out[2]= {{x -> 134}, {x -> 269}, {x -> 311}, {x -> 443}, {x -> 714}, {x -> 888}, {x -> 1023}, {x -> 1113}, {x -> 1468}, {x -> 1558}, {x -> 1693}, {x -> 1867}, {x -> 2138}, {x -> 2270}, {x -> 2312}, {x -> 2447}} In[3]:= Mod[4528, 89 29] Out[3]= 1947 In[5]:= Mod[26443, 89 29] Out[5]= 633 In[6]:= 714 - 633 Out[6]= 81 In[4]:= 1947 - 1867 Out[4]= 80 Note that it is possible to find x_1+n and x_2-n-1 for big numbers as well. In[17]:= Solve[x^4 + 18 x^2 == 0, {x}, Modulus -> 998 RSA260 - 1] Out[17]= {{x -> 0}, {x -> 0}, {x -> 2716082610274971337694474899142218136748963550135500602361031437724\ 1148029498527233843245349186917213241417399133612721259249692585804181\ 9818630648952854721813303764099692665262595635447345263101006568774477\ 6819639057085831464289459835504443854332275069363102750}, {x -> 1935251726819563576471604818537396032900790177332957476126388938476\ 6450492569345259155379732197915384563586789457975978942475750893157139\ 6070515431820538430231477541697830873720636717018978520619872151494668\ 26026293513345827168515238448239719110330657204806179851}}
Dickson says[71]
in fact, only when
This assertion is not true in modular arithmetic. I give the following Mathematica which shows 3 counter examples in 30 tries.
Table[{x, IntegerQ[PowerMod[x^3 + 1, 1/2, 89 29]]}, {x, 1, 30}] // Grid { {1, False}, {2, True}, {3, False}, {4, False}, {5, False}, {6, False}, {7, False}, {8, True}, {9, True}, {10, False}, {11, False}, {12, False}, {13, False}, {14, False}, {15, False}, {16, False}, {17, False}, {18, False}, {19, False}, {20, False}, {21, False}, {22, False}, {23, False}, {24, False}, {25, False}, {26, False}, {27, False}, {28, False}, {29, True}, {30, False} }
Dickson[72] says that a Raoul Bricard has proven that all primes can always be decomposed into
Dickson says that at vol 2 p255 of his work the method for proving this is explained.
I was not able to get Mathematica to obtain for a big 1000 bit prime number in quick time.
Henri Brocard, who is mentioned in Dickson's work studied and published a bibliography of Pell's Equation.
Pell's Equation is: .
R. Bricard, in the section above, generalised Pell's equation by proving that all 1 mod 8 primes numbers are of the form
Brocard was a noted geometer, like Bricard. They were both French, and were born only 25 years apart. Much of their mathematical work could be described as complimentary. They could almost have been father and son, except that they were actually from different families with no relation between them.
In the History vol 2 p571 Dickson states:
H. Brocard[73] noted that has the special solution
- and
I was unable to get this equation to work. I tried it out in mathematica several times. There may be a special solution for this, but it is not a general solution. This is unusual because Dickson usually gets it right.
An amusing passage, from the point of distance of 100 years since the book was published, is the leveling of | N. Beguelin's reputation by Dickson at History of the Theory of Numbers, vol 2, p13-15 (Chelsea Publishing, 1952). Some elipsed quotes of this:
Nicholas Beguelin attempted to prove Fermat's theorem that every integer is a sum of s polygonial numbers of s sides. ... On p411 Beguelin states without proof the erroneous generalization ... Thus Beguelin contradicts himself in his generalisation of Fermat's theorem ... N. Beguelin made a puerile illogical attempt to prove that every number is the sum of three triangular numbers. ... Beguelin next attempted, but failed completely, to deduce
Dickson was known to be a hard man and he shows his metal against the reputation of Nicholas Beguelin, a Swiss mathematician of the 18th Century.
Another disparraging Beguelin quote for Dickson is at vol 1 p 381
N. Beguelin states that has a triniary divisor only when although his examples (p249) contradict this statement.
D.S. Hart[74] [75] gave a "new" method to solve . Set . Then Set . Then
- ,
But the solutions are not in general integers.
This works in modular arithmetic, even for big numbers. The solutions being fractions are not a problem for modular arithmetic. For instance,
<math>x^{2}-7*y{2}=1</math> In[1]:= A = 4 + 3 Out[1]= 7 In[16]:= yy = Mod[2 2 PowerMod[3, -1, RSA260], RSA260] Out[16]= 1474188368635311095685405683668415395174139300164667692960916\ 5546085881960934667991008486484379831066057266886687600034113828136373\ 9061842386358381239695325593058061528256606711353560830803638563776091\ 09693789476240862011796013897594043917276529500956762972134 In[17]:= xx = Mod[1 + 2 4 PowerMod[3, -1, RSA260], RSA260] Out[17]= 7370941843176555478427028418342076975870696500823338464804582\ 7730429409804673339955042432421899155330286334433438000170569140681869\ 5309211931791906198476627965290307641283033556767804154018192818880455\ 4846894738120431005898006948797021958638264750478381486070 show x^-7*y^2=1 found for RSA260 modulus In[18]:= Mod[xx^2 - 7 yy^2, RSA260] Out[18]= 1
This works for .
In[19]:= yy = Mod[2 2 PowerMod[-3, -1, RSA260], RSA260] Out[19]= 7370941843176555478427028418342076975870696500823338464804582\ 7730429409804673339955042432421899155330286334433438000170569140681869\ 5309211931791906198476627965290307641283033556767804154018192818880455\ 4846894738120431005898006948797021958638264750478381486065 In[20]:= xx = Mod[1 + 2 4 PowerMod[-3, -1, RSA260], RSA260] Out[20]= 1474188368635311095685405683668415395174139300164667692960916\ 5546085881960934667991008486484379831066057266886687600034113828136373\ 9061842386358381239695325593058061528256606711353560830803638563776091\ 09693789476240862011796013897594043917276529500956762972131 In[21]:= Mod[xx^2 - 1 yy^2, RSA260] Out[21]= 1
According to Dickson:
This allows the finding of the modular imaginary number for modula of powers of primes once the I number for the Prime modula is known.
This also seems to work for modula of (p*q) and (p*q)^m, as the following example shows. (this works for large numbers as well)
In[1]:= Expand[(568 + I)^5] Out[1]= 59119154872088 + 520428000641 I In[2]:= PowerMod[520428000641, -1, (89 29)^5] Out[2]= 77612584756845935 In[3]:= Mod[-(59119154872088 77612584756845935)^2, (89 29)^5] Out[3]= 1
This is a very powerful finding since the Pythagorean Bridge, mentioned elsewhere in this blog, between squares and roots can be used for powers of (P*Q)^m as well as (P*Q).
This works for powers of 2 as well, I checked on this.
The author's index of History Of Theory Of Numbers (Chelsea Publishing, 1952) is often the best way to navigate around the three volume reference. Normally, it is extremely accurate, however, in volume 3, p 304, the author's index for Chapter 3 says that R. Dedekind is mentioned at p76. I was unable, after looking several times, to find this mention, although Dedekind is mentioned on the previous page, p75, and perhaps the math extends onto p76. In this case the index reference should be p75-76, but it is instead p75, p76.
An unusual mistake in the Index volume, normally it is very accurate.
After some time, I have reread p75 and p76 of vol 3. Dedekind is definitely mentioned in p75 and a rather long half page proof is given of his, however at the end of p75 Dickson says "we can prove" and then goes on from Dedekind's math to another proof that continues onto p76, and which I assume is Dickson's, but which he assumes follows from Dedekind's earlier proof. Dedekind is not mentioned by name on p76.
Dickson says at Theory of Numbers vol ii p629 that Joseph Bertrand has a treatment of but the reference at p244 does not have this treatment. The reference is at[78] and is Traite Elementaire d'Algebra 1850, p 244. This is quite unusual for a bad reference to Appear in Dickson.
Also the line where Bertrand is mentioned has an asterick footnote, but there is no asterick footnote on p629.
However, a treatment of the equation can be found at p224-7 of the said math book.
As a possibility of a fault, it is to be mentioned that in the author's index vol ii, p 205 that he is mentioned on p205 but not on p206. However, his math starts in p205 and goes into the first paragraph of p206. I think the author's index requires the name be on the page, however,in this case the math laps over from p205 to p206.
People reading my math blog may notice I spend a lot of effort on the rational square root of -1 mod p*q, or the modular imaginary number.
With knowledge of the 2 square roots of -1 it is trivial to factor p and q since the addition of both square roots will be a nontrivial multiple of p or q and the minus of the two square roots will be a multiple of either p or q.
However, it is possible to factor p*q with knowledge of only one square root of -1 mod p*q in the three following ways:
If there were any easy way to factor p*q with knowledge of only one then this would extend Euler who needs two sums of squares to do his factoring algorithm. Sums of Squares and the are interchangeable and easily convertible into the other.
In these treatments the square is determined first and the root is then determined. The square whose root is made known is not known in advance, so these algorithms are not general modular square root algorithms. However, they do establish a bridge between the square and the root. The square can be determined before the root is found.
A quick example where the imaginary component of the is cancelled out and where and and and follows:
the square is 8+5+6*i, find the inverse of 6 PowerMod[6, -1, 89 29]=2151 find the square using the pythagorean triple: 3,4,5 and the modified SQUARE equation shown above Mod[(8 + 5 + 6 2), 89 29]=25 find C in the quadratic equation Mod[2151 25 - 5, 89 29]=2150 make the quadratic equation Mod[2151 25 - 5 - 2150, 89 29]= 0 make the square as per GAUSS equation 2151=A -1=B -2150=C Mod[1 - 4 2151 (-2150), 89 29]=574 now make the root as per GAUSS equation Mod[2 2151 5 - 1, 89 29]= 861 Note the root has been found Mod[861^2, 89 29]= 574
Thus, this method can be used with any Pythagorean Triple and within each use of a Pythagorean triple any I can be used, and the I can be a rational number.
After quite a bit of reduction it appears that and thus that the root is
After some work on this the matter is still inconclusive as the following math shows the case where i=11
find C for quadratic equation Mod[2151 121 - 11, 89 29]= 2160 find the square Mod[1 - 2151 4 (-2160), 89 29]= 1441 find the root Mod[2 2151 (11) - 1, 89 29]= 863 confirm the root works Mod[863^2, 89 29]= 1441 note that 11/3 is 1 off the root, unlike the example for 2 Mod[11 PowerMod[3, -1, 89 29], 89 29]= 864