# Endo999

Joined 25 February 2007
Wikipedia:Babel
 en This user is a native speaker of the English language.
 fr-2 Cet utilisateur peut contribuer avec un niveau intermédiaire en français.
 es-1 Este usuario puede contribuir con un nivel básico de español.
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.

## Install

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

## Features

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

a) a '->FRENCH', as an example. This means translation is happening from English to French.
If you click on this link you get to change the language translation pair
b) a source link which takes you to the Google translation web page.
c) A 'X' link, just in case moving the cursor away from the popup does not get rid of the popup.

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.

Others

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)

## Selected Text Translation

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.

## Open Source Project

GoogleTrans is now an open source project hosted at

The code there is the code running at Wikipedia with some extras:

1) on IE text within input fields and textareas can be translated and replaced
2) a Wikipedia? link within the popup will bring up a list of Wikipedia links (can get a wikipedia article up on a term within a webpage without selecting it).
3) just include 1 12k javascript file and a link within your website to get the dictionary/wikipedia lookup effect. A second 80k javascript file is dynamically loaded if the GoogleTrans option is clicked on.
4) two Perl scripts are included that
b) change every link within that webpage to be a link to itself (with the original link URL as a data parameter)
c) inject the javascript files within the website that is presented to the user, so that every URL called by the Perl script suddenly has the cursor hover dictionarylookup effect.
d) one of the Perl scripts is an introductory page that tells the user how to do cursor lookup and how to get other websites to have this effect.

The open source code allows anyone to effect the cursor hover dictionary/wikipedia lookup on any website. The Perl scripts can get 99 percent of the websites out there and massage the website so the effect happens on it. This should be good on online newspapers (any body can do Wikipedia lookups easily) and language schools (students can read other language websites and get help on words or phrases they don't understand).

## Math Blog

The following material is Endo999's math blog.

## Fun Mathematical Observations

For fun, consider the following:

Everybody knows the following is true:

${\displaystyle {\frac {r^{3}}{r^{2}}}==r^{1}}$

However, the following analogue for ${\displaystyle r^{x}+r^{-x}}$  is also true:

${\displaystyle {\frac {r^{3}+r^{-3}}{r^{2}+r^{-2}-1}}==r^{1}+r^{-1}}$

So:

${\displaystyle {\frac {8+{\frac {1}{8}}}{4+{\frac {1}{4}}-1}}==2+{\frac {1}{2}}}$

and

${\displaystyle {\frac {27+{\frac {1}{27}}}{9+{\frac {1}{9}}-1}}==3+{\frac {1}{3}}}$

Viola! Make sure to remember the ${\displaystyle -1}$  in the denominator.

### Redrafting Cubes

With the equation in the section above, we can take a cube and draft the equation as:

${\displaystyle 2^{8*3}+2^{-8*3}{\bmod {89*29}}\equiv 2385\equiv (2^{8}+2^{-8})(2^{16}+2^{-16}-1)}$

or

${\displaystyle 2^{5*3}+2^{-5*3}{\bmod {89*29}}\equiv 2013\equiv (2^{5}+2^{-5})(2^{10}+2^{-10}-1)}$

or

${\displaystyle 2^{4*3}+2^{-4*3}{\bmod {89*29}}\equiv 670\equiv (2^{4}+2^{-4})(2^{8}+2^{-8}-1)}$

Thus,

${\displaystyle 2^{x*3}+2^{-x*3}{\bmod {p*q}}\equiv (2^{x}+2^{-x})(2^{2*x}+2^{-2*x}-1)}$

This is a redrafting of any cube or power of cubes.

You can also redraft the cube as:

${\displaystyle (2^{x}-2^{-x})(2^{2*x}+2^{-2*x}+1){\bmod {p*q}}\equiv 2^{x*3}-2^{-x*3}}$

### Redrafting an RSA cipher to the 23rd power

As ${\displaystyle m^{23}{\bmod {p*q}}\equiv c}$ , in our RSA cipher, then ${\displaystyle 2^{23/3}{\bmod {89*29}}\equiv 1529}$ , therefore,

${\displaystyle (1529+1529^{-1})(1529^{2}+1529^{-2}-1){\bmod {89*29}}\equiv 2^{23}+2^{-23}\equiv 1115}$

If ${\displaystyle m^{e}{\bmod {p*q}}}$  has a cube power then the equation holds.

You can solve for ${\displaystyle 2^{23/3}+2^{-23/3}}$  by solving the cubic modular equation:

${\displaystyle x(x^{2}-3){\bmod {89*29}}\equiv 1115}$

where ${\displaystyle x=1924\equiv 1529+1529^{-1}{\bmod {89*29}}}$

Or

${\displaystyle (1529-1529^{-1})(1529^{2}+1529^{-2}+1){\bmod {89*29}}\equiv 2^{23}-2^{-23}\equiv 2182}$

## Back To Fun Facts On Math

How about the 2 modular square roots of a modular power. For instance,

${\displaystyle 2^{31}{\bmod {8}}03}$  is the modular square root for ${\displaystyle 2^{62}{\bmod {8}}03}$ . So is ${\displaystyle 2^{14}{\bmod {8}}03}$  because ${\displaystyle 2^{90}{\bmod {8}}03\equiv 1}$ .

As the power cycle is ${\displaystyle 90}$  for the modulus ${\displaystyle 803}$ , then ${\displaystyle 2^{62}{\bmod {8}}03\equiv 2^{-28}{\bmod {8}}03}$  since ${\displaystyle 62+28=90}$ . As such ${\displaystyle 2^{62/2}\equiv 2^{31}}$  and ${\displaystyle 2^{-28/2}\equiv 2^{-14}}$

So

${\displaystyle {\frac {2^{31}+2^{-31}{\bmod {8}}03}{2^{14}+2^{-14}{\bmod {8}}03}}{\bmod {8}}03\equiv {\sqrt {1}}{\bmod {8}}03\equiv 2^{45}{\bmod {8}}03}$

and

${\displaystyle {\frac {2^{31}-2^{-31}{\bmod {8}}03}{2^{14}-2^{-14}{\bmod {8}}03}}{\bmod {8}}03\equiv -{\sqrt {1}}{\bmod {8}}03\equiv -2^{45}{\bmod {8}}03}$

Also,

${\displaystyle {\frac {x^{2}-y^{2}}{x-y}}{\bmod {n}}\equiv (y+x){\bmod {n}}}$

Also,

${\displaystyle (g^{p*q+1})^{p*q-1}+(g^{p*q+1})^{-(p*q-1)}{\bmod {p}}*q\equiv g^{p^{2}-q^{2}}+g^{q^{2}-p^{2}}{\bmod {p}}*q}$

Also,

${\displaystyle g^{p*q-1}+g^{-(p*q-1)}{\bmod {p}}*q\equiv g^{p-q}+g^{q-p}{\bmod {p}}*q}$

and

${\displaystyle g^{p*q-1}-g^{-(p*q-1)}{\bmod {p}}*q\equiv {\sqrt {1}}(g^{p-q}-g^{q-p}){\bmod {p}}*q}$

Also,

${\displaystyle g^{p*q}+g{\bmod {p}}*q\equiv g^{p}+g^{q}{\bmod {p}}*q}$

and

${\displaystyle g^{p*q}-g{\bmod {p}}*q\equiv {\sqrt {1}}(g^{p}-g^{q}){\bmod {p}}*q}$

Also,

${\displaystyle (({\sqrt {1}}+1)^{2}+({\sqrt {1}}-1)^{2}))^{evenpower}{\bmod {p}}q\equiv (({\sqrt {1}}+1)^{2}-({\sqrt {1}}-1)^{2}))^{evenpower}{\bmod {p}}q}$

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,

${\displaystyle g^{pq}{\bmod {p}}q\equiv g^{p}{\bmod {q}}}$

${\displaystyle g^{pq-1}{\bmod {p}}q\equiv g^{p-q}{\bmod {q}}}$

Most of the above equations of sums of powers can be split up in the manner shown just above.

Also, ${\displaystyle (pq-1){\bmod {p}}q\equiv {\sqrt {1}}{\bmod {q}}}$  This seems obvious since ${\displaystyle (pq-1){\bmod {p}}q\equiv -1{\bmod {q}}}$  and ${\displaystyle -1*-1{\bmod {n}}\equiv 1{\bmod {n}}}$  ,however, ${\displaystyle g^{(q-1)/2}{\bmod {q}}\equiv -1{\bmod {q}}}$  many times

Also, ${\displaystyle {\frac {g^{3x}+g^{-3x}}{g^{x}-g^{-x}}}-{\frac {g^{x}+g^{-x}}{g^{x}-g^{-x}}}==g^{2x}-g^{-2x}}$

${\displaystyle i+1}$  as the base or generator for modular powers is also fun to do

${\displaystyle \alpha =(i+1)^{pq}-(i+1){\bmod {p}}q}$

will equal a complex number with the real or imaginary numbers sometimes being ${\displaystyle \alpha =-((2^{(p-1)/2})(-+)(2^{(q-1)/2}))+{\sqrt {1}}((2^{(p-1)/2})(+-)(2^{(q-1)/2}))i}$  or ${\displaystyle \alpha =-((2^{(p-1)/2})(-+)(2^{(q-1)/2}))i+{\sqrt {1}}((2^{(p-1)/2})(+-)(2^{(q-1)/2}))}$

It seems to vary with the semi-prime looked at.

${\displaystyle (i+1)}$  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 ${\displaystyle 2}$ .

## Fun Math Observations for Modular Square Roots

1)

${\displaystyle {\frac {2^{p-q}+2^{q-p}}{2^{pq-1}+2^{-(pq-1)}}}{\bmod {p}}q\equiv 1}$
${\displaystyle {\frac {2^{p-q}-2^{q-p}}{2^{pq-1}-2^{-(pq-1)}}}{\bmod {p}}q\equiv {\sqrt {1}}{\bmod {p}}q}$

2)

As the power cycle is ${\displaystyle 90}$  for the modulus ${\displaystyle 803}$ , then ${\displaystyle 2^{62}{\bmod {8}}03\equiv 2^{-28}{\bmod {8}}03}$  since ${\displaystyle 62+28=90}$ . As such ${\displaystyle 2^{62/2}\equiv 2^{31}}$  and ${\displaystyle 2^{-28/2}\equiv 2^{-14}}$

So

${\displaystyle {\frac {2^{31}+2^{-31}{\bmod {8}}03}{2^{14}+2^{-14}{\bmod {8}}03}}{\bmod {8}}03\equiv {\sqrt {1}}{\bmod {8}}03\equiv 2^{45}{\bmod {8}}03}$

and

${\displaystyle {\frac {2^{31}-2^{-31}{\bmod {8}}03}{2^{14}-2^{-14}{\bmod {8}}03}}{\bmod {8}}03\equiv -{\sqrt {1}}{\bmod {8}}03\equiv -2^{45}{\bmod {8}}03}$

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.

${\displaystyle i*i*modularsquare{\bmod {p}}*q\equiv }$
After which:
${\displaystyle root{\bmod {p}}*q\equiv {\frac {\sqrt {}}{i}}{\bmod {p}}*q}$

I have a way, which is similar but more complex, which introduces ${\displaystyle \alpha }$  and ${\displaystyle \beta }$  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 ${\displaystyle {\sqrt {modulus}}}$  steps.

### Sum Of Squares

Interestingly the sum of all the squares in a modulus is ${\displaystyle 0}$ . Thus:

${\displaystyle \sum _{x=1}^{x=p*q-1}x^{2}{\bmod {p*q}}\equiv 0}$

This means that:

${\displaystyle x^{2}{\bmod {p*q}}\equiv -(\sum _{y=1}^{y=x-1}y^{2}+\sum _{y=x+1}^{y=p*q-1}y^{2}){\bmod {p*q}}}$

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 ${\displaystyle t}$  squares.

${\displaystyle t*(t+1)*(2*t+1)/6}$

The sum of all numbers in a modulus field is also 0. Since every number ${\displaystyle N}$  in a semiprime modulus field is countered by ${\displaystyle -N}$  on the other side of the field then this has to be.

${\displaystyle \sum _{x=1}^{x=p*q-1}x{\bmod {p*q}}\equiv 0}$

#### Sum of Powers and RSA

Even though we don't know what ${\displaystyle m}$  is, when we are given ${\displaystyle m^{e}{\bmod {p*q}}}$ , we do know that

${\displaystyle m^{e}{\bmod {p*q}}\equiv -(\sum _{x=1}^{x=m-1}x^{e}+\sum _{x=m+1}^{x=p*q-1}x^{e})}$

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]];
];


## An Equation For A Modular Square Root

Since

${\displaystyle {\frac {2^{3x}-1}{2^{x}-1}}{\bmod {p}}*q\equiv 2^{2x}+2^{x}+1}$

then every modular square is equivalent to:

${\displaystyle {\frac {(2^{3x}-1)}{(2^{x}-1)}}-2^{x}-1{\bmod {p}}*q\equiv 2^{2x}}$

and every power root is defined as:

${\displaystyle {\frac {(2^{3x}-1)}{(2^{x}-1)}}-2^{2x}-1{\bmod {p}}*q\equiv 2^{x}}$

Now viewers may say that ${\displaystyle {\frac {(2^{3x}-1)}{(2^{x}-1)}}}$  is a hard term to come up with, however, terms like this are possible. Note:

${\displaystyle {\frac {2^{804-402-3}}{2^{401}}}{\bmod {8}}03\equiv {\frac {2^{15}(2^{93}-1)}{2^{5}(2^{31}-1)}}}$

So terms like the one needed are almost instantly possible to generate from moduli of ${\displaystyle p*q}$ .

The general equation is a polynomial where:

${\displaystyle {\frac {(2^{4x}-1)}{(2^{x}-1)}}{\bmod {p}}*q\equiv 2^{3x}+2^{2x}+2^{x}+1}$

The general equation is (Neal Koblitz reports this as well in [1]):

${\displaystyle {\frac {(2^{\alpha x}-1)}{(2^{x}-1)}}{\bmod {p}}*q\equiv 2^{(\alpha -1)x}+2^{(\alpha -2)x}+2^{2x}+2^{x}+1}$

As well:

${\displaystyle {\frac {(2^{3x}-1)}{(2^{2x}-1)}}{\bmod {p}}*q\equiv {\frac {(2^{2x})}{(2^{x}+1)}}+1}$
${\displaystyle {\frac {(2^{4x}-1)}{(2^{3x}-1)}}{\bmod {p}}*q\equiv {\frac {(2^{2x}+1)}{{\frac {(2^{2x})}{(2^{x}+1)}}+1}}}$

## A Link Between The Two Equivalent Modular Square Roots

If you take one modular square root, let's say ${\displaystyle 16*16{\bmod {9}}49\equiv 256}$ , you can get the other square root (in this case ${\displaystyle 673*673{\bmod {9}}49\equiv 256}$ , by:

${\displaystyle ChineseRemainder[\{16,Mod[-16,949]\},\{73,13\}]=673}$

You can get the modular square root of 1 by

${\displaystyle ChineseRemainder[\{1,Mod[-1,p*q]\},\{p,q\}]={\sqrt {1}}{\bmod {p}}*q}$

You can get a quad root of 1 by

${\displaystyle ChineseRemainder[\{{\sqrt {1}}{\bmod {p}}*q{\bmod {p}},{\sqrt {-1}}{\bmod {p}}*q{\bmod {q}}\},\{p,q\}]=1^{1/4}{\bmod {p}}*q}$

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.

## Square Root Of 1 mod P*Q Definition

Quoting from Wilson's theorem:

Gauss proved[2] that if m > 2

${\displaystyle \prod _{k=1 \atop \gcd(k,m)=1}^{m}\!\!k\ \equiv {\begin{cases}-1{\pmod {m}}&{\text{if }}m=4,\;p^{\alpha },\;2p^{\alpha }\\\;\;\,1{\pmod {m}}&{\text{otherwise}}\end{cases}}}$

where p is an odd prime, and ${\displaystyle \alpha }$  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:

${\displaystyle \prod _{k=1 \atop \gcd(k,m)=1}^{(m-1)/2}\!\!k\ \equiv {\begin{cases}\;\;\,{\sqrt {1}}{\pmod {m}}&\end{cases}}}$

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


### Definition Of Square Root Of -1 Mod P*Q

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 ${\displaystyle {\sqrt {-1}}{\bmod {p}}}$ . 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.

### Another Definition Of The Square Root of 1 Mod P*Q

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 ${\displaystyle {\sqrt {-1}}_{1}*{\sqrt {-1}}_{2}{\bmod {p*q}}\equiv {\sqrt {1}}}$  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


### P/(P-Q) mod P*Q Seems To Be A Special Number In the MOD P*Q Field

If you take ${\displaystyle p(p-q)^{-1}{\bmod {p*q}}}$  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


${\displaystyle -1335{\bmod {89*29}}\equiv 1246}$  which is one off 1247.

This number has unusual properties.

By and large, any number that is ${\displaystyle 0{\bmod {p}}}$  and ${\displaystyle 1{\bmod {q}}}$  will be its own square or square root.

The difference between 1335 and 1247 is 88 which is ${\displaystyle -{\sqrt {1}}{\bmod {89*29}}\equiv 88}$ . Thus:

${\displaystyle -(p*(p-q)^{-1})+1{\bmod {p*q}}\equiv (q*(q-p)^{-1})}$

and

${\displaystyle (p*(p-q)^{-1})-(q*(q-p)^{-1}){\bmod {p*q}}\equiv -{\sqrt {1}}}$

Moreover, ${\displaystyle (p*(p-q)^{-1}){\bmod {p*q}}\equiv (p*(p+q)^{-1})}$

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:

${\displaystyle 2^{p*q-1}\equiv 2^{p+q-2}{\bmod {p*q}}\equiv 2^{88+28}{\bmod {89*29}}\equiv 1247(2^{28})+1335(2^{88})\equiv 509\equiv 1247(2^{28})-1246(2^{88})}$

where ${\displaystyle 2*1247-1{\bmod {89*29}}\equiv -2*1335+1\equiv {\sqrt {1}}}$ . This is another way to unwind the multiplication!

Because ${\displaystyle 1247*1355{\bmod {89*29}}\equiv 0}$  then:

${\displaystyle (1247(2^{14})-1335(2^{44}))^{2}{\bmod {89*29}}\equiv 1247(2^{28})+1335(2^{88})}$

and by switching the sign of one of the numbers the other square root is found. Thus:

${\displaystyle 1247(2^{14})-1335(2^{44}){\bmod {89*29}}\equiv {\sqrt {1}}*(1247(2^{14})+1335(2^{44}))}$

#### Constructing the Squareless Number and Algebra With The Squareless Number

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 ee = e. Both of these elements are null:

${\displaystyle \lVert e\rVert =\lVert e^{*}\rVert =e^{*}e=0.}$

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:

${\displaystyle (i-j)^{2}{\bmod {p*q}}\not {\!\!\equiv }0\equiv (568-2493)^{2}{\bmod {89*29}}\equiv 1890}$

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. ${\displaystyle j}$  in the above equations equals ${\displaystyle {\sqrt {1}}{\bmod {p*q}}}$

According to [3] you can construct the squareless number via:

${\displaystyle 89*(89^{-1}{\bmod {2}}9){\bmod {89*29}}\equiv 1335\equiv 89*15}$

or

${\displaystyle p*(p^{-1}{\bmod {q}}){\bmod {p*q}}}$

Moreover, these is a type of definition of any square with regard to the squareless number. If ${\displaystyle \alpha _{i}}$  are the two squareless numbers of ${\displaystyle p*q}$  then:

${\displaystyle (\alpha _{1}+\beta )*(\alpha _{2}+\beta ){\bmod {p*q}}\equiv \beta ^{2}+\beta }$

Thus, since the difference between the two squareless numbers is ${\displaystyle \pm {\sqrt {1}}{\bmod {p*q}}}$  then

${\displaystyle (x^{2}){\bmod {p*q}}\equiv (\alpha _{1}+\beta )(\alpha _{2}\pm {\sqrt {1}}+\beta )\equiv \beta ^{2}+\beta \pm {\sqrt {1}}*x}$

This is a type of algebra. An example:

${\displaystyle 1360=1335+25}$ , ${\displaystyle 1360^{2}{\bmod {89*29}}\equiv 1604\equiv 25^{2}+25-2493*1360}$
##### The Relationship Between The Squareless Number And The Square Root Of -1

The relationship between the Squareless number and the two Square Roots of -1 mod p*q are shown in the following equations:

${\displaystyle 568+2*1247*945{\bmod {89*29}}\equiv 945}$
${\displaystyle -945+2*1335*568{\bmod {89*29}}\equiv 568}$

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:

${\displaystyle \pm {\sqrt {-1}}_{1}+2*\alpha _{1}*{\sqrt {-1}}_{2}{\bmod {p*q}}\equiv {\sqrt {-1}}_{2}}$

where ${\displaystyle \alpha }$  is one of the squareless numbers.

##### The Relationship Between The Squareless Number And The Quad Root Of 1

Also, ${\displaystyle (1335+1247*568)^{2}{\bmod {89*29}}\equiv 88\equiv -{\sqrt {1}}}$

Thus this is the definition of the quad root of 1. The other quad root ${\displaystyle {\sqrt[{4}]{1}}{\bmod {p*q}}}$  is:

${\displaystyle (1335-1247*568){\bmod {89*29}}}$

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.

##### The Relationship Between The Squareless Number And g^(p-1)-1 mod p*q

Since, ${\displaystyle 6060}$  and ${\displaystyle 1314}$  are squareless numbers mod ${\displaystyle 101*73}$ , and ${\displaystyle 6060+1314{\bmod {101*73}}\equiv 1}$  then

${\displaystyle (6060+1314)*\alpha {\bmod {101*73}}\equiv \alpha \equiv 6060*\alpha +1314*\alpha }$ . Remember that since ${\displaystyle 6060{\bmod {101}}\equiv 0}$  and ${\displaystyle 1314{\bmod {73}}\equiv 0}$  any multiplication by ${\displaystyle \alpha }$  will keep the mod equivalents. In other words
${\displaystyle 6060*\alpha {\bmod {101}}\equiv 0}$  and ${\displaystyle 1314*\alpha {\bmod {73}}\equiv 0}$

Thus since ${\displaystyle g^{p-1}-1{\bmod {p}}\equiv 0}$  and ${\displaystyle g^{q-1}-1{\bmod {q}}\equiv 0}$ , and since ${\displaystyle g^{p*q-1}-1{\bmod {p*q}}\equiv (g^{p-1}-1)+(g^{q-1}-1)}$  then

${\displaystyle SQUARELESS_{{\bmod {p}}\equiv 0}*(g^{p*q-1}-1){\bmod {p*q}}\equiv g^{p-1}-1}$
${\displaystyle SQUARELESS_{{\bmod {q}}\equiv 0}*(g^{p*q-1}-1){\bmod {p*q}}\equiv g^{q-1}-1}$

or

${\displaystyle 6060*(2^{101*73-1}-1){\bmod {101*73}}\equiv 2^{100}-1}$
${\displaystyle 1314*(2^{101*73-1}-1){\bmod {101*73}}\equiv 2^{72}-1}$

Thus, probably all of the sums of ${\displaystyle x_{x{\bmod {p}}\equiv 0}+y_{y{\bmod {q}}\equiv 0}}$  are derivable from the squareless numbers. This is a conjecture but if each ${\displaystyle sum=X+Y}$  only has one ${\displaystyle x_{x{\bmod {p}}\equiv 0}+y_{y{\bmod {q}}\equiv 0}}$ , 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: ${\displaystyle x_{i{\bmod {p}}\equiv 0}+y_{y{\bmod {q}}\equiv 0}}$ .

As well as ${\displaystyle g^{p-1}-1{\bmod {p*q}}\equiv X*p}$  and ${\displaystyle g^{q-1}-1{\bmod {p*q}}\equiv Y*q}$  then the equation for ${\displaystyle X_{i}}$  and ${\displaystyle Y_{i}}$  is now known:

where ${\displaystyle g^{p-1}-1{\bmod {p*q}}\equiv X*p}$  then ${\displaystyle X{\bmod {p*q}}\equiv \pm (p^{-1}{\bmod {q}})*(g^{p*q-1}-1){\bmod {q}}}$
where ${\displaystyle g^{q-1}-1{\bmod {p*q}}\equiv Y*q}$  then ${\displaystyle Y{\bmod {p*q}}\equiv \pm (q^{-1}{\bmod {p}})*(g^{p*q-1}-1){\bmod {p}}}$

#### Implications For RSA

In another section of this blog there is the claim that

${\displaystyle 1145^{1010}{\bmod {89*29}}\equiv 37*(37^{9*89}+37^{9*29}-37^{9})\equiv 2458}$
where ${\displaystyle (23*1010-1)/(89*29)=9}$

With knowledge of the self-square numbers for ${\displaystyle 89*29}$  of ${\displaystyle 1247}$  and ${\displaystyle 1335}$  then the above equation can be turned into:

${\displaystyle 1145^{1010}{\bmod {89*29}}\equiv 37^{10}*(1335*37^{9*88}+1247*37^{9*28})\equiv 2458}$
where ${\displaystyle (23*1010-1)/(89*29)=9}$

or

${\displaystyle 1145^{1010}{\bmod {89*29}}\equiv 37^{10}*(1335*37^{88}+1247*37^{28})^{9}\equiv 2458}$

Another equation that can be made from this melange is:

${\displaystyle 1335*37^{9*29}+1247*37^{9*89}{\bmod {89*29}}\equiv 37^{9}\equiv 1639}$
##### all powers can be redrawn as sums of powers using P and Q
${\displaystyle 1335*37^{3*29}+1247*37^{3*89}{\bmod {89*29}}\equiv 37^{3}\equiv 1614}$

where ${\displaystyle 1335*37+1247*37{\bmod {89*29}}\equiv 37}$

##### The Base Can Be Changed

or we can change the base of the powers to ${\displaystyle 1247*37}$  and ${\displaystyle 1335*37}$

${\displaystyle 1145^{1010}{\bmod {89*29}}\equiv 37^{10}*((1335*37)^{88}+(1247*37)^{28})^{9}\equiv 2458}$

In other words:

${\displaystyle 1335*37^{88}{\bmod {89*29}}\equiv (1335*37)^{88}}$

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


## The Product To Sum theorum of RSA semiprimes

If ${\displaystyle p}$  and ${\displaystyle q}$  are odd primes and

${\displaystyle 2^{x}{\bmod {p}}\equiv 1or-1}$

and

${\displaystyle 2^{y}{\bmod {q}}\equiv 1or-1}$

then the product of these

${\displaystyle 2^{x}2^{y}{\bmod {p}}*q\equiv \pm 2^{x}\pm 2^{y}\pm 1{\bmod {p}}*q}$

The sum or subtraction of the powers will be one off the product of the powers. This type of equivalence happens for

${\displaystyle 2^{p-1}|2^{(p-1)/2}|2^{q-1}|q^{(q-1)/2}|{\sqrt {1}}}$

Basically, any combination of the ${\displaystyle p}$  and ${\displaystyle q}$  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 ${\displaystyle 1}$  or ${\displaystyle -1}$ .

Normally, the ${\displaystyle {\sqrt {1}}}$  is:

${\displaystyle {\sqrt {1}}{\bmod {p}}*q{\bmod {p}}\equiv 1}$
${\displaystyle {\sqrt {1}}{\bmod {p}}*q{\bmod {q}}\equiv -1}$

so it partakes of this relationship (theorum) as well.

Sometimes the quad root of 1 (${\displaystyle 1^{1/4}{\bmod {p}}*q}$  and ${\displaystyle 1^{3/4}{\bmod {p}}*q}$ ) and also the square root of -1 (${\displaystyle {\sqrt {-1}}_{x}{\bmod {p}}*q}$ ) also partake of this theorum as well.

Thus,

${\displaystyle 2^{p-q}{\bmod {p}}*q\equiv \pm 2^{p-1}\pm 2^{-(q-1)}\pm 1}$

or

${\displaystyle 2^{72}+2^{-10}-1{\bmod {7}}3*11\equiv 2^{73-11}}$

as

${\displaystyle 2^{72}{\bmod {7}}3\equiv 1}$
${\displaystyle 2^{-10}{\bmod {1}}1\equiv 1}$

so both signs will be pluses.

Since

${\displaystyle 2^{36}{\bmod {7}}3\equiv 1}$
${\displaystyle 2^{5}{\bmod {1}}1\equiv -1}$

so

${\displaystyle -2^{36}+2^{5}{\bmod {7}}3*11\equiv 2^{36+5}-1{\bmod {7}}3*11}$

as the sign of the terms is switched among the terms due to polynomial expansion since:

${\displaystyle 2^{36}{\bmod {7}}3=\alpha 73+1}$
${\displaystyle 2^{5}{\bmod {1}}1=\beta 11-1}$

and

${\displaystyle 2^{36}2^{5}\equiv (\alpha 73+1)(\beta 11-1){\bmod {7}}3*11}$

Now

${\displaystyle (\alpha 73)(\beta 11){\bmod {7}}3*11\equiv 0}$

The other three terms of the multiplication are:

${\displaystyle (-1)(2^{36}-1)+(1)(2^{5}+1)-1=-2^{36}+2^{5}+1}$

This resulting residual is equal to ${\displaystyle 2^{41}}$

This theorum is a type of analogue, among modular powers, to the Parallelogram law, which works on squares.

### Even RSA can be manipulated with the Product To Sum Theorum

If we take ${\displaystyle e=3}$  and ${\displaystyle p*q=89*29}$  then ${\displaystyle e^{-1}{\bmod {89*29}}\equiv 1721}$

Please note that ${\displaystyle (3*1721-1)/(89*29)=2}$  and for this example ${\displaystyle m=37}$ :

${\displaystyle m^{3}{\bmod {89*29}}\equiv 1614}$
${\displaystyle 1614^{1721}{\bmod {89*29}}\equiv 37^{1+2(89+29-1)}\equiv 902}$

If we divide the cipher, ${\displaystyle 37^{3}}$ , which we know, away from ${\displaystyle 902}$  then:

${\displaystyle 37^{1+2(89+29-1)-3}{\bmod {89*29}}\equiv 37^{2(88+28)}\equiv 2137}$

This is perfect for the Product To Sum theorum shown in the just previous section. As such

${\displaystyle 37^{2*88}+37^{2*28}{\bmod {89*29}}\equiv 2137+1}$

So either ${\displaystyle m^{2*(p-1)+2*(q-1)}{\bmod {p*q}}}$  or ${\displaystyle m^{2*(p-1)}+m^{2*(q-1)}{\bmod {p*q}}}$  can be derived from a public encryption key of 3.

With the example given, note that ${\displaystyle 2*88{\bmod {3}}\equiv 2}$  and ${\displaystyle 2*28{\bmod {3}}\equiv 2}$  as well, although ${\displaystyle 2*(89*29-1)-3{\bmod {3}}\equiv 0}$

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.

#### With A Public Key of 23

Using ${\displaystyle e=23}$ ,${\displaystyle m=37}$  modulus of ${\displaystyle 89*29}$ ,${\displaystyle c=37^{23}{\bmod {89*29}}\equiv 1145}$ (which is known) and noting that ${\displaystyle 23^{-1}{\bmod {89*29}}\equiv 1010}$  then, after some steps of algebra I am not showing:

${\displaystyle 1145^{1010}{\bmod {89*29}}\equiv 37*(37^{9*89}+37^{9*29}-37^{9})\equiv 2458}$
where ${\displaystyle (23*1010-1)/(89*29)=9}$

Thus, it looks like the general equation where any nth root, given ${\displaystyle root^{power}{\bmod {p*q}}}$  can be rewritten in terms of the powers of p and q is:

${\displaystyle c^{e^{-1}{\bmod {p*q}}}{\bmod {p*q}}\equiv m*(m^{x*p}+m^{x*q}-m^{x})}$
where ${\displaystyle (e*(e^{-1}{\bmod {p*q}})-1)/(p*q)=x}$  and x and c are known.

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!

#### A definition of One mod p*q

By the Product To Sum theorum given above, it follows that one is:

${\displaystyle g^{P-1}+g^{Q-1}-g^{P+Q-2}{\bmod {p*q}}\equiv 1}$

It thus follows that all bases of powers, ie.,${\displaystyle g^{1}{\bmod {p*q}}}$ , can be defined as:

${\displaystyle g^{P}+g^{Q}-g^{P+Q-1}{\bmod {p*q}}\equiv g}$

and that all powers of ${\displaystyle g^{n}{\bmod {p*q}}}$  can be defined as:

${\displaystyle g^{P-1+n}+g^{Q-1+n}-g^{P+Q-2+n}{\bmod {p*q}}\equiv g^{n}}$

Since ${\displaystyle g^{e}{\bmod {p*q}}}$  is an RSA operation, this has implications for RSA.

## All Modular Powers are the sum or subtraction of three powers (of moduli RSA Semiprimes)

As in the preceding section:

${\displaystyle 2^{p-q}{\bmod {p}}*q\equiv \pm 2^{p-1}\pm 2^{-(q-1)}\pm 1}$

or

${\displaystyle 2^{72}+2^{-10}-1{\bmod {7}}3*11\equiv 2^{73-11}}$

it follows that any power can be expressed via ${\displaystyle 2^{p-q}2^{x}}$ . Thus,

${\displaystyle 2^{p-q}2^{x}{\bmod {p}}*q\equiv \pm 2^{p-1+x}\pm 2^{-(q-1)+x}\pm 2^{0+x}}$

or

${\displaystyle 2^{72+20}+2^{-10+20}-2^{20}{\bmod {7}}3*11\equiv 2^{62+20}}$

As such, since ${\displaystyle 2^{90}{\bmod {8}}03\equiv 1}$  and ${\displaystyle 2^{41}\equiv 2^{31}+2^{5}-2^{-5}{\bmod {8}}03}$  then:

${\displaystyle 1{\bmod {8}}03\equiv 2^{80}+2^{54}-2^{44}{\bmod {8}}03}$
${\displaystyle {\sqrt {1}}{\bmod {8}}03\equiv 2^{35}+2^{9}-2^{-1}{\bmod {8}}03}$

This result seems to be like, for modular numbers, Legendre's_three-square_theorem.

## With the Use of a Small Third Prime, X, you can find candidates of the equivalency of (p-1 mod (x-1)) and (q-1 mod (x-1)) when only p*q is known

Iterate all the possibilities of ${\displaystyle x_{1}}$  and ${\displaystyle x_{2}}$  through the equivalency:

${\displaystyle x_{1}x_{2}+x_{1}+x_{2}{\bmod {(}}x-1)\equiv pq-1{\bmod {(}}x-1)}$

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 ${\displaystyle p-1{\bmod {x}}-1}$  and ${\displaystyle q-1{\bmod {(}}x-1)}$  are shown of ${\displaystyle p*q}$  where ${\displaystyle p}$  and ${\displaystyle q}$  are not known. Among this list of candidates for ${\displaystyle p-1}$  and ${\displaystyle q-1}$  , ${\displaystyle 1/4}$  of these number of possibilities will be the candidates for ${\displaystyle p-q{\bmod {x}}-1}$ .

Thus for ${\displaystyle x=37}$  there will be:

6 possibilities for ${\displaystyle p-1{\bmod {x}}-1}$  and ${\displaystyle q-1{\bmod {x}}-1}$  when ${\displaystyle p-1{\bmod {6}}=4}$  and ${\displaystyle q-1{\bmod {6}}=0}$  or vice versa. Of these 6 possibilities there will be agreement on ${\displaystyle p+q{\bmod {1}}2}$  and either ${\displaystyle p-q{\bmod {3}}6}$  or ${\displaystyle q-p{\bmod {3}}6}$  will be definitely known.
8 possibilities for ${\displaystyle p-1{\bmod {x}}-1}$  and ${\displaystyle q-1{\bmod {x}}-1}$  when ${\displaystyle p-1{\bmod {6}}=4}$  and ${\displaystyle q-1{\bmod {6}}=4}$  or when ${\displaystyle p-1{\bmod {6}}=0}$  and ${\displaystyle q-1{\bmod {6}}=0}$ .

My question is: in the case of the 6 possibilities for the ${\displaystyle x=37}$  is definite knowledge of ${\displaystyle p}$  and ${\displaystyle q}$  known since ${\displaystyle p+q{\bmod {1}}2}$  is known and either ${\displaystyle p-q{\bmod {3}}6}$  or ${\displaystyle q-p{\bmod {3}}6}$  is known.

As it turns out, ${\displaystyle 5077+857{\bmod {1}}2}$  can be derived from ${\displaystyle p*q}$  via:

${\displaystyle 5077*857{\bmod {4}}=1}$  or ${\displaystyle 1*1}$  or ${\displaystyle 3*3}$
${\displaystyle 5077*857{\bmod {3}}=2}$  or ${\displaystyle 1*2}$
by taking the Chinese Remainder of mods 4 and 3 (to get 12 as the result mod) you will get 6 for both possibilities.

So while this algorithm knows ${\displaystyle p+q{\bmod {1}}2}$  this is not new knowledge. That means that the claim that either ${\displaystyle p-q{\bmod {3}}6}$  or ${\displaystyle q-p{\bmod {3}}6}$  remains possible new knowledge.

By decomposing ${\displaystyle p-q{\bmod {3}}6}$ , using the Chinese Remainder Theorum, into ${\displaystyle p-q{\bmod {4}}}$  and ${\displaystyle p-q{\bmod {9}}}$  it can be shown that ${\displaystyle p-q{\bmod {3}}}$  or ${\displaystyle q-p{\bmod {3}}}$  is derivable from examination of ${\displaystyle p*q\mod 3}$ . As such, it appears any new knowledge from the algorithm above would be in the form of ${\displaystyle p-q{\bmod {9}}}$  or ${\displaystyle q-p{\bmod {9}}}$ . Since ${\displaystyle p-q{\bmod {3}}}$  is known therefore the new knowledge would either be ${\displaystyle (p-q{\bmod {3}})+0}$ , ${\displaystyle (p-q{\bmod {3}})+3}$  or ${\displaystyle (p-q{\bmod {3}})+6}$ . If there is a way to derive ${\displaystyle p-q{\bmod {9}}}$  and/or ${\displaystyle q-p{\bmod {9}}}$  then the algorithm I show above would not have new knowledge in the case of ${\displaystyle x=37}$ . But if this sum were not derivable from examination of ${\displaystyle p*q}$ , then this algorithm would show new knowledge.

By solving the following problem in Mathematica:

Since ${\displaystyle 5077*857{\bmod {9}}=2}$  and:
Solve[a b == 2, {a, b}, Modulus -> 9]

{{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 ${\displaystyle a-b}$  and ${\displaystyle b-a}$  resolve to ${\displaystyle 1}$  or ${\displaystyle -1}$ . This is what we get from ${\displaystyle 8{\bmod {3}}6}$  or ${\displaystyle -8{\bmod {3}}6}$ , so, amazingly, there is NO new knowledge in the case of ${\displaystyle x=37}$  that is not derivable from ${\displaystyle p*q}$ .

There is still the reduced set of ${\displaystyle p}$ 's and ${\displaystyle q}$ 's.

## A Third Modulus Transforms the Hard P*Q division problem into a B*E modular residue problem

A Third Modulus Transforms the Hard P*Q division problem into a B*E modular residue problem[4] that is solvable when

1) ${\displaystyle (p-q)/4<{\sqrt {q}}}$
2) the resulting ${\displaystyle B*E{\bmod {p}}-b*4}$  residue is a square (as a product, not necessarily as a residue).
3) Combined Divisor Methods

Considering that all RSA semiprimes are ${\displaystyle 3{\bmod {4}}}$  you can pick a modulus between ${\displaystyle P}$  and ${\displaystyle Q}$  (try the ${\displaystyle 3{\bmod {4}}}$  number closest to ${\displaystyle {\sqrt {p*q}}}$ ). The resulting new modulus, ${\displaystyle x}$ , is ${\displaystyle x=p-b*4=q+e*4}$ . Given this new modulus, the following equation holds:

${\displaystyle -P*Q*16^{-1}{\bmod {X}}\equiv B*E{\bmod {X}}}$  where ${\displaystyle X=P-B*4}$  and ${\displaystyle X=Q+E*4}$

and

${\displaystyle (P*Q)^{2}*64^{-1}{\bmod {X}}^{2}\equiv B*E(-2*b*q-12*b*e+2*e*p){\bmod {X}}^{2}}$  where ${\displaystyle X=P-B*4}$  and ${\displaystyle X=Q+E*4}$  and where ${\displaystyle (p*q-x^{2})/4==-b*q+e*p-4*b*e}$

### When P And Q Are Close Enough Together

When P and Q are close together, ${\displaystyle (p-q)/4<{\sqrt {q}}}$ , then ${\displaystyle B*E{\bmod {X}}}$  is a product, not a residue. As such it can be factored and two of the divisors of this factorisation will either be ${\displaystyle B}$  and the other ${\displaystyle E}$ . With ${\displaystyle B}$  known and ${\displaystyle P-B*4}$  known, it is easily possible to discover ${\displaystyle P}$ .

Example:

Take ${\displaystyle P=5003}$  and ${\displaystyle Q=4831}$
${\displaystyle (5003-4831)=172<{\sqrt {4831}}}$  (around ${\displaystyle 220}$ ).
Next take the first number that is 3 mod 4 before the square root of 5003*4831 (that's the modulus we are studying)
${\displaystyle 4903}$  is close enough.
Then we do the following simple equation (expressed in mathematica)
Mod[-4831 5003 PowerMod[16, -1, 4903], 4903]=450
${\displaystyle 450}$ , in this case, is the product: ${\displaystyle 18*25=450}$
As such the following equation is true:
${\displaystyle 4903=4831+4*18=5003-25*4}$
or
${\displaystyle Q+4*e=P-B*4=4903}$
so ${\displaystyle E=18}$  and ${\displaystyle B=25}$
As such we can take
${\displaystyle 4903-18*4=4831}$
or
${\displaystyle 4903+25*4=5003}$

### When B*E Is A Square

When ${\displaystyle B*E{\bmod {X}}}$  is a square (the product which the residue represents is a square, the residue doesn't need to be a square), ${\displaystyle P}$  and ${\displaystyle Q}$  are often discoverable as well.

Example:

${\displaystyle Q=4003}$  ${\displaystyle P=221603}$
${\displaystyle X=Q+120*120*4=P-200*200*4=61603}$
${\displaystyle E=120*120}$
${\displaystyle B=200*200}$
The Mathematica for this is:
Mod[-4003 221603 PowerMod[16, -1, 61603], 61603] = 11950 (in mathematica)
(notice the residue, 11950, is not a square but it represents a product that is a square)
Now take the modular square root (which we can do because 61603 is a prime):
${\displaystyle {\sqrt {11950}}{\bmod {6}}1603\equiv 24000}$
Now, simply, square this above number to get our B*E as a product, not a residue
${\displaystyle 24000*24000=57600000=120*120*200*200=b*e}$  (as a product, not a residue).

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 ${\displaystyle {\sqrt {P-Q}}}$  attempts you will have a product, ${\displaystyle B*E}$ , that is a square and you will have your answer (if ${\displaystyle B*E{\bmod {X}}}$  does have a modular square root!).

I roughly estimate that when ${\displaystyle P}$  is approximately 2 times ${\displaystyle Q}$  that the numbers of modulus you need to try is ${\displaystyle (P*Q)^{1/4}}$ . 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.

### Combined Divisor Methods

According to [5] once either ${\displaystyle p{\bmod {Y}}_{1}}$  and ${\displaystyle q{\bmod {Y}}_{2}}$  is known, one can pick a modulus, ${\displaystyle X}$ , which is both ${\displaystyle X{\bmod {Y}}_{1}\equiv p{\bmod {Y}}_{1}}$  and ${\displaystyle X{\bmod {Y}}_{2}\equiv q{\bmod {Y}}_{2}}$ . When this happens then ${\displaystyle p-X}$  will be a multiple of ${\displaystyle Y_{1}}$ , and ${\displaystyle X-q}$  will also be a multiple of ${\displaystyle Y_{2}}$ . As such it will be possible to divide by ${\displaystyle Y_{1}*Y_{2}}$  and reduce, or implode, the product. If ${\displaystyle Y_{1}*Y_{2}}$  is big enough, then the remainder of ${\displaystyle b_{1}*e_{1}}$  stops being a remainder and starts being a product. At this point you can factor ${\displaystyle b_{1}*e_{1}}$  and reconstitute

${\displaystyle p=X+b_{1}*Y_{1}}$
${\displaystyle q=X-e_{1}*Y_{2}}$

Note: This method of deriving ${\displaystyle p}$  or ${\displaystyle q}$  is equivalent to the traditional Chinese Remainder Methods where ${\displaystyle p{\bmod {Y}}_{1}}$  and ${\displaystyle p{\bmod {Y}}_{2}}$  are known and used to derive ${\displaystyle p{\bmod {Y}}_{1}*Y_{2}}$ . This is because, knowing ${\displaystyle q{\bmod {Y}}_{2}}$  one can always derive ${\displaystyle p{\bmod {Y}}_{2}}$  via the equation:

${\displaystyle (p_{x1}-1)(q_{x2}-1)+(p_{x1}-1)+(q_{x2}-1){\bmod {Y}}\equiv P*Q-1}$

However, there are two cases where this method of imploding the product is superior to traditional Chinese Remainder methods.

#### Factors of X can't divide B*E, except P and Q

Besides ${\displaystyle p}$  and ${\displaystyle q}$  no factor of the modulus, ${\displaystyle X}$ , can evenly divide ${\displaystyle b*e}$  in the following equation:

${\displaystyle -p*q{\bmod {X}}\equiv b*e}$

As a factor of the modulus, ${\displaystyle X}$ , is by definition ${\displaystyle 0{\bmod {X}}}$  and only ${\displaystyle p}$  and ${\displaystyle q}$  are ${\displaystyle 0{\bmod {p}}*q}$  where ${\displaystyle p}$  and ${\displaystyle q}$  are both primes.

People may legitimately ask whether it is possible for a factor of modulus ${\displaystyle X}$  to divide a sum under that modulus. This is true, but the theorum is still relevant because the factor of ${\displaystyle X}$  can't be a factor, not just that it can be a factor that can't be divided by.

#### Factors Of P*q-1 Are Candidates To Divide B*E

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 ${\displaystyle X\equiv 1{\bmod {Y}}}$  where ${\displaystyle Y}$  is a common factor of (p-1) and (q-1), and thus also a factor of p*q-1.

##### How To Find Common Factors Of P-Q or P+Q At Twice The Random Rate

As it works out

${\displaystyle (p-m)(q-n)+(p+m)(q+n)==2*p*q+2*m*n}$

and

${\displaystyle (p-m)(q+n)+(p+m)(q-n)==2*p*q-2*m*n}$

Most times, though you are interested in the case where ${\displaystyle m*n}$  is a square as in ${\displaystyle n*n}$ . In this case

${\displaystyle (p-n)(q-n)+(p+n)(q+n)==2*p*q+2*n^{2}}$

and

${\displaystyle (p-n)(q+n)+(p+n)(q-n)==2*p*q-2*n^{2}}$

In the first equation when there is a common factor between ${\displaystyle (p-n)}$  and ${\displaystyle (q+n)}$  this common factor will appear in the whole sum: ${\displaystyle 2*p*q+2*n^{2}}$ . This common factor will also be a factor of ${\displaystyle p+q}$  since ${\displaystyle p-n+q+n==p+q}$ .

Likewise when there is a common factor between ${\displaystyle (p+n)}$  and ${\displaystyle (q-n)}$  this common factor will also appear in ${\displaystyle 2*p*q+2*n^{2}}$ .

Since there are two possible common factors at play, then it is twice as common as random that a factor of ${\displaystyle (p+q)}$  will appear in an iteration of, say, ${\displaystyle 2*p*q+2*n^{2}}$  where ${\displaystyle n=1}$  to ${\displaystyle 30}$ . In this way it is quite easy to come up with a small factor of ${\displaystyle (p+q)}$ , although a big factor is still hard to obtain.

Likewise, taking the equation:

${\displaystyle (p-n)(q+n)+(p+n)(q-n)==2*p*q-2*n^{2}}$

it is twice as likely that a factor of ${\displaystyle (p-q)}$  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 ${\displaystyle (p-n)}$  and ${\displaystyle (q-n)}$ . The subtraction of these: ${\displaystyle (p-n)-(q-n)==(p-q)}$ .

Both factors of ${\displaystyle (p+q)}$  and ${\displaystyle (p-q)}$  can be evenly divided from the sum ${\displaystyle -p*q{\bmod {X}}}$ . Factors of ${\displaystyle (p+q)}$  can be divided once and factors of ${\displaystyle (p-q)}$  can be divided twice (by the square).

##### A Factor Of (p-q) and A Factor of (p+q) combined together is the following

If you take a factor of ${\displaystyle (p-q)}$ , a factor of ${\displaystyle (p+q)}$ , and divide them, you get the following:

when ${\displaystyle (89-29)=60=12*5}$  and ${\displaystyle (89+29)=118=2*59}$  then
${\displaystyle 59*5^{-1}{\bmod {89*29}}\equiv -2493*(12)*2^{-1}{\bmod {89*29}}\equiv 528}$

Since:

${\displaystyle ((89-60)/12)^{-1}*(89+29)/2){\bmod {89*29}}\equiv 5^{-1}*59}$

and

${\displaystyle (89-60)^{-1}*(89+29){\bmod {89*29}}\equiv 2493\equiv {\sqrt {1}}}$

and

${\displaystyle 2^{-1}*(12^{-1})^{-1}==2^{-1}*12}$  thus the switch between the denominator and the numerator of the other factors.

If you square this then you get:

${\displaystyle 12^{2}*2^{-2}{\bmod {89*29}}\equiv 36}$  which are the other factors of (p-q) and (p+q) besides 5 and 12.

As well:

${\displaystyle {\sqrt {1}}{\bmod {89*29}}\equiv \pm (p-q)(p+q)^{-1}\equiv \pm (p+q)(p-q)^{-1}}$

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.

##### Equivalent Square Considerations

Take a mathematica equation showing the iteration of ${\displaystyle p*q+n^{2}}$  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 ${\displaystyle n^{2}}$  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 ${\displaystyle p}$  and ${\displaystyle q}$ .

#### Example 1

Given:

1) ${\displaystyle p=50021}$
2) ${\displaystyle q=45007}$
3) ${\displaystyle 50021{\bmod {5}}3\equiv 42}$
4) ${\displaystyle 45007{\bmod {5}}9\equiv 49}$

Now make the modulus, ${\displaystyle X}$ , via

${\displaystyle 46364{\bmod {5}}3\equiv 42}$  and ${\displaystyle 46364{\bmod {5}}9\equiv 49}$

Taking the naiive equation:

${\displaystyle -50021*45007{\bmod {4}}6364\equiv 3657*1357\equiv 1601}$

Now take the augmented equation:

${\displaystyle -50021*45007*(53*59)^{-1}{\bmod {4}}6364\equiv 69*23\equiv 1587}$ \

Note that ${\displaystyle 69*53=3657}$  and that ${\displaystyle 23*59=1357}$

Thus, the product (not the remainder) has been successfully divided, or imploded, to a smaller product and that:

${\displaystyle p=46364+69*53}$
${\displaystyle q=46364-23*59}$

#### Example 2: When Y Is A Factor Of P-Q

This method of imploding the product is superior to Traditional Chinese Remainder Methods when the divisor, ${\displaystyle Y}$ , is a divisor of ${\displaystyle p-q}$ . In this situation then ${\displaystyle p{\bmod {Y}}\equiv q{\bmod {Y}}}$  and ${\displaystyle Y^{2}}$  can be used as the divisors. Thus, if ${\displaystyle Y\approx {\sqrt {p-q}}}$  then ${\displaystyle p}$  and ${\displaystyle q}$  can be determined from ${\displaystyle p*q}$

Given:

1) ${\displaystyle p=50021}$
2) ${\displaystyle q=45007}$
3) ${\displaystyle 46}$  is a divisor of ${\displaystyle 50021-45007}$
4) ${\displaystyle 50021{\bmod {4}}6\equiv 19}$
5) ${\displaystyle 45007{\bmod {4}}6\equiv 19}$

Now make the modulus, ${\displaystyle X}$  where ${\displaystyle X{\bmod {4}}6\equiv 19}$  then ${\displaystyle 47445}$  will do.

Now note that the naiive equation is:

${\displaystyle -50021*45007{\bmod {4}}7445\equiv 2576*2438\equiv 17548}$

and the augmented equation is:

${\displaystyle -50021*45007*46^{-2}{\bmod {4}}7445\equiv 56*53\equiv 2968}$

and that:

${\displaystyle p=47445+56*46}$
${\displaystyle q=47445-53*46}$

Note that you cannot determine ${\displaystyle p}$  and ${\displaystyle q}$  solely from knowledge of ${\displaystyle 50021-45007{\bmod {4}}6\equiv 0}$  and ${\displaystyle 50021{\bmod {4}}6\equiv 19}$  solely using the Chinese Remainder Theorum!

##### When X Is A Factor Of P-Q

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 ${\displaystyle -B*E{\bmod {X}}}$ .

${\displaystyle 5003-2003=3000=2^{3}*3*5^{3}}$

As such let's take ${\displaystyle 125=5^{3}}$  to be the modulus, which is a factor of P-Q:

${\displaystyle -5003*2003{\bmod {125}}\equiv 116}$

Note that

${\displaystyle (5003-125)=4878=b}$
${\displaystyle (125-2003)=-1878=e}$
${\displaystyle 4878*(-1878){\bmod {125}}\equiv 116}$

Since ${\displaystyle b+e=p-q}$  and ${\displaystyle 5003-2003{\bmod {125}}\equiv 0}$ then ${\displaystyle 4878+(-1878){\bmod {125}}\equiv 0}$  then,

${\displaystyle -4878{\bmod {125}}\equiv -1878}$

and so:

${\displaystyle -116{\bmod {125}}\equiv 4878^{2}\equiv (-1878)^{2}}$

As such we can take the modular square root of the modulus, since it's prime factorisation is known, and:

${\displaystyle {\sqrt {-116}}{\bmod {125}}\equiv 3}$

Thus, ${\displaystyle b\equiv 3}$ and ${\displaystyle e\equiv (-3){\bmod {125}}\equiv 122}$ .

Thus, if a factor of ${\displaystyle P-Q}$  is known then ${\displaystyle B}$  and ${\displaystyle E}$  can be worked out. Note that it is possible to find at twice the random rate the factors of ${\displaystyle P-Q}$ . This is worked out in the section Common Factors of P-Q at twice the random rate

##### When X Is A (Factor Of P-Q)^2

Let's take, from the above example, the case where ${\displaystyle 125*125}$  is the modulus, ${\displaystyle X}$  for ${\displaystyle P=5003}$  and ${\displaystyle Q=2003}$ .

Since ${\displaystyle 125*125-5003*2003=(-4878+(-1878))*125+4878*(-1878)=-10005384}$ , then ${\displaystyle b=4878}$  and ${\displaystyle e=-1878}$ .

Since ${\displaystyle 4878{\bmod {125}}\equiv 3}$  and ${\displaystyle -1878{\bmod {125}}\equiv -3}$  then the equation above can be rewritten for the modulus: ${\displaystyle 125*125}$  as: ${\displaystyle (-3-3)*125+4878*(-1878){\bmod {125*125}}\equiv 10241}$ . So adding ${\displaystyle 6*125+10241{\bmod {125*125}}\equiv 4878*(-1878)\equiv 10991\equiv b*e}$ .

From ${\displaystyle b*e{\bmod {125*125}}\equiv 10991}$  we can construct ${\displaystyle b-e{\bmod {125*125}}}$  by the following manner:

${\displaystyle b{\bmod {125*125}}\equiv 39*125+3}$
${\displaystyle e{\bmod {125*125}}\equiv -15*125-3}$

Thus:

${\displaystyle 10991{\bmod {125*125}}\equiv (39*125+3)(-15*125-3)}$

So:

${\displaystyle 10991-(-3)(3){\bmod {125*125}}\equiv (-3)*(39*125)+3*(-15*125)\equiv 11000}$

If we divide by the common term, 3, and minus by 6 (the addition of 3 and 3) then we get:

${\displaystyle -(39*125)-3+(-15*125)-3{\bmod {125*125}}\equiv 8869\equiv -4878+(-1878)\equiv -b+e}$

As such we can minus ${\displaystyle -10005384-8869*125{\bmod {125^{3}}}\equiv 604741\equiv 4878*(-1878){\bmod {125^{3}}}\equiv b*e{\bmod {125^{3}}}}$

##### The Bad Stuff That Happens When There Are Common Factors Between (P-1) and (Q-1)

If there is a common factor between ${\displaystyle p-1}$  and ${\displaystyle q-1}$ , then this will also be a factor of ${\displaystyle p*q-1}$ , since

${\displaystyle p*q-1==(p-1)*(q-1)+(p-1)+(q-1)}$

Accordingly, any common factor of ${\displaystyle p-1}$  and ${\displaystyle q-1}$  will appear also in ${\displaystyle p*q-1}$ . Many factors of ${\displaystyle p*q-1}$  will not be factors of ${\displaystyle p-1}$  and ${\displaystyle q-1}$  but all common factors will be.

As well any common factor of ${\displaystyle p-1}$  and ${\displaystyle q-1}$  will also be a factor of ${\displaystyle p-q}$ ! 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 ${\displaystyle p*q}$ , 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:

###### Example 1

Given:

${\displaystyle P=39343}$  ${\displaystyle P-1=2*3*79*83}$
${\displaystyle Q=8467}$  ${\displaystyle Q-1=2*3*17*83}$
${\displaystyle P*Q=39343*8467}$  ${\displaystyle P*Q-1=2^{2}*3^{2}*5*11*83*2027}$

As you can see above, ${\displaystyle 83}$  is the common factor. Common factors will always appear in the factorisation of ${\displaystyle p*q-1}$  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]

###### The Implications For RSA

This common factor will have implications for RSA.

Given:

${\displaystyle e=23}$
${\displaystyle n=8467*39343}$
${\displaystyle 8466=102*83}$
${\displaystyle 39342=474*83}$
${\displaystyle d{\bmod {(}}83*83)\equiv 23^{-1}{\bmod {(}}83*83)\equiv 6290}$
${\displaystyle totient=8466*39342=48348*(83*83)}$
${\displaystyle d=318588095{\bmod {3}}9342*8466}$
${\displaystyle 318588095{\bmod {(}}83*83)\equiv 6290}$
${\displaystyle 46245*83*83+6290==318588095}$
${\displaystyle 8467*39343+1{\bmod {(}}83*83)\equiv 8467+39343{\bmod {(}}83*83)\equiv 6476}$

So some information about the private key is leaked, specifically ${\displaystyle d{\bmod {C}}ommonFactor^{2}}$ . As well, a factor of ${\displaystyle p-q}$  is revealed so my product implosion scheme is invoked.

So it is never a good idea to have a common factor between ${\displaystyle p-1}$  and ${\displaystyle q-1}$  except perhaps 2 or 3. I have looked at current RSA key generation methods and none of them explicitly mention that common factors between ${\displaystyle p-1}$  and ${\displaystyle q-1}$  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]

###### Looking At The Openssl RSA Key Generation Code For Common Factors

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

n-1 = 2 * 3^3 * 7 * 13 * 67 * 2399 * 28559 *

5485062554686449262177590194597345407327047899375366044215091312099734701911004226037445837630559113651708968440813791318544450398897628 67234233761906471233193768567784328338581360170038166729050302672416075037390699071355182394190448204086007354388034161296410061846686501 4941425056336718955019

Any rsa key generation in SAFE mode will always have a gcd(p-1,q-1)=2, so SAFE mode always avoids common factors. The conclusion is that openssl code can have common factors (must be above 17863) in its rsa keys every 20,000 key generations or so when not generated in SAFE mode, and that at this time approximately 30 bits of the totient will be revealed out of the 1024 bits of the full totient. There is, of course, no way of knowing which of the 20,000 key generations will have the common factors, but since OpenSource SSL generates at least 20,000 rsa keys each week, it can be surmised, from the test above, that 30 bits of the rsa totient are leaked every week somewhere around the world.
##### Splitting the message into two products of the cipher

Let's say that the message is ${\displaystyle 37}$  and that the cipher is ${\displaystyle 37^{23}{\bmod {8467*39343}}\equiv 148815052}$ , because ${\displaystyle 6290{\bmod {83*83}}\equiv d}$  and that ${\displaystyle d\equiv 46245*(83*83)+6290}$  then the message, ${\displaystyle 37}$  can be split into two powers based on the cipher such as:

${\displaystyle 148815052^{6290}*148815052^{46245*83*83}{\bmod {8467*39343}}\equiv 37}$

Therefore:

${\displaystyle 148815052*148815052^{-6290}{\bmod {8467*39343}}\equiv 37^{22}*148815052^{46245*83*83}\equiv 146993011}$

or

${\displaystyle 148815052*148815052^{-13*6290}{\bmod {8467*39343}}\equiv 37^{10}*148815052^{13*46245*83*83}\equiv 285574110}$

or

${\displaystyle 148815052*148815052^{-23*6290}{\bmod {8467*39343}}\equiv 148815052^{23*46245*83*83}\equiv 253503289}$

Now:

${\displaystyle 148815052*148815052^{-22*6290}{\bmod {8467*39343}}\equiv 37*148815052^{22*46245*83*83}\equiv 82921582}$

and ${\displaystyle 22*46245*83*83*23+1{\bmod {23}}\equiv 1}$  note- not a power multiple of 23!.

Since ${\displaystyle 2^{2}}$  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:

${\displaystyle 23^{-1}{\bmod {4}}\equiv 3}$
${\displaystyle 148815052*148815052^{-(22*3)}{\bmod {8467*39343}}\equiv 331864148}$
${\displaystyle 37*148815052^{22*4*79647023}{\bmod {8467*39343}}\equiv 331864148}$

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 ${\displaystyle c^{e*x}{\bmod {p*q}}}$  and the ${\displaystyle m*c^{(e-1)*x}{\bmod {p*q}}}$  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

###### The RSA cipher can now be attacked by a Discrete Logarithm Algorithm

Now that we have

${\displaystyle 148815052^{23*46245*83*83}\equiv 253503289}$

and we know the cipher, or ${\displaystyle 148815052}$  we can use Pollard's Kangaroo Discrete Logarithm Algorithm to solve the log (which is a factor of ${\displaystyle 23*83*83}$ ). As such we can take the base for the discrete logarithm algorithm to be ${\displaystyle 148815052^{23*83*83}{\bmod {39343*8467}}\equiv 134420949}$  and that ${\displaystyle 134420949^{46245}\equiv 253503289}$  (with us knowing ${\displaystyle 134420949}$  and ${\displaystyle 253503289}$ ) , we can solve for ${\displaystyle 46245}$  in ${\displaystyle {\sqrt {46245}}}$ . 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 ${\displaystyle 46245*83*83+6290==d}$ , so the decryption key can be determined using this method.

###### 2 is always a Common Factor of (p-1) and (q-1) so Pollard's Algorithm Can Always Be Applied to Any RSA Cipher

Since ${\displaystyle e*d{\bmod {2}}\equiv 1}$  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 ${\displaystyle e=23}$  and ${\displaystyle d{\bmod {2}}\equiv 1}$ , then

${\displaystyle 148815052*148815052^{-23*1}{\bmod {39343*8467}}\equiv 152505560}$

and

${\displaystyle 148815052^{(318588095-1)*23}{\bmod {39343*8467}}\equiv 152505560}$  where ${\displaystyle 318588095==d}$

Therefore, since ${\displaystyle 148815052^{23}\equiv 158806108}$ ,

${\displaystyle 158806108^{(318588095-1)}{\bmod {39343*8467}}\equiv 152505560}$  where ${\displaystyle 318588095==d}$

(Note that ${\displaystyle 158806108}$  and ${\displaystyle 152505560}$  are known).

Thus, you can apply Pollard's Kangaroo Algorithm to any RSA Cipher to get ${\displaystyle d}$ .

###### General Equation Applied

Take ${\displaystyle c*c^{-e}{\bmod {p*q}}\equiv f}$  then ${\displaystyle (c^{e})^{(d-1)}{\bmod {p*q}}\equiv f}$  is true. Since ${\displaystyle c^{e}}$  and ${\displaystyle f}$  are known then ${\displaystyle d-1}$  can be found using Pollard's Kangaroo Discrete Logarithm Algorithm.

Since ${\displaystyle c^{e}{\bmod {p*q}}\equiv m^{e*e}}$  then ${\displaystyle c^{e}}$  is in the same power ring as ${\displaystyle m}$  and the power ring length for both sums will be the same. In fact the power ring length for 37 (${\displaystyle m}$ ), 148815052 (${\displaystyle m^{23}}$ ) and 158806108 (${\displaystyle m^{23*23}}$ ) is the same: 668814. Since ${\displaystyle 318588094{\bmod {668814}}\equiv 232630}$ , then the actual logarithm to be found by the Kangaroo algorithm will be ${\displaystyle 232630}$ . However, ${\displaystyle (37^{23})^{232630+1}{\bmod {39343*8467}}\equiv 37}$ , so finding ${\displaystyle (d-1)}$  for ${\displaystyle m^{e*e}}$  is also finding the ${\displaystyle (d-1)}$  for ${\displaystyle m^{e}}$ .

Seeing that the power ring length of the message, in this example, is ${\displaystyle 668,814}$  and the modulus is ${\displaystyle 333,117,181}$ , 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, ${\displaystyle 232630}$ ). Thus, properly calibrated, the Kangaroo algorithm will often be a ${\displaystyle \Omega (1/3)}$  algorithm, and not ${\displaystyle \Omega (1/2)}$  as you would naively think.

###### Every Base Can Be Used In This Equation

It's always possible to get an equation like that above with any base. Take ${\displaystyle 2}$  for instance.

${\displaystyle 2^{e}*2^{-e*e}{\bmod {p*q}}\equiv (2^{e*e})^{(d-1)}}$

The math in this section is totally theroretical since you can always use Pollard's RHO method to factor P*Q in ${\displaystyle N^{1/4}}$  time.

#### A Close Call ON RSA

According to [10] if:

${\displaystyle 1010*2^{23}+1652*3^{23}{\bmod {89*29}}\equiv 0}$

then

${\displaystyle 1010*2^{22}(1652*3^{22})^{-1}{\bmod {89*29}}\equiv 1289}$

which is both

${\displaystyle 1010^{1/23}*1652^{-1/23}{\bmod {89*29}}\equiv 1289}$

as well as being

${\displaystyle -3*2^{-1}{\bmod {89*29}}\equiv 1289}$

It is remarkable that such a humdrum equivalence as ${\displaystyle -3*2^{-1}{\bmod {89*29}}}$  could also have such a remarkable equivalence as