Open main menu
Wikipedia:Babel
enThis user is a native speaker of the English language.
fr-2Cet utilisateur peut contribuer avec un niveau intermédiaire en français.
es-1Este 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.

Contents

InstallEdit

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

FeaturesEdit

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 TranslationEdit

 

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 ProjectEdit

GoogleTrans is now an open source project hosted at

"http://code.google.com/p/googletrans"

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
a) read a webpage
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 BlogEdit

The following material is Endo999's math blog.


Fun Mathematical ObservationsEdit

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.

Redrafting CubesEdit

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:

 

Redrafting an RSA cipher to the 23rd powerEdit

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

 

Back To Fun Facts On MathEdit

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  .

Fun Math Observations for Modular Square RootsEdit

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.

 
After which:
 


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.

Sum Of SquaresEdit

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.

 

Sum of Powers and RSAEdit

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

An Equation For A Modular Square RootEdit

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:

 
 

A Link Between The Two Equivalent Modular Square RootsEdit

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.

Square Root Of 1 mod P*Q DefinitionEdit

Quoting from Wilson's theorem:

Gauss proved[2] that if m > 2

 

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

Definition Of Square Root Of -1 Mod P*QEdit

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.

Another Definition Of The Square Root of 1 Mod P*QEdit

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

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

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:

 

Constructing the Squareless Number and Algebra With The Squareless NumberEdit

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:

 

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:

 ,  
The Relationship Between The Squareless Number And The Square Root Of -1Edit

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.

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

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.

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

Since,   and   are squareless numbers mod  , and   then

 . Remember that since   and   any multiplication by   will keep the mod equivalents. In other words
  and  

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:

where   then  
where   then  

Implications For RSAEdit

In another section of this blog there is the claim that

 
where  

With knowledge of the self-square numbers for   of   and   then the above equation can be turned into:

 
where  

or

 

Another equation that can be made from this melange is:

 
all powers can be redrawn as sums of powers using P and QEdit
 

where  

The Base Can Be ChangedEdit

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

The Product To Sum theorum of RSA semiprimesEdit

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.

Even RSA can be manipulated with the Product To Sum TheorumEdit

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.

With A Public Key of 23Edit

Using  ,  modulus of  , (which is known) and noting that   then, after some steps of algebra I am not showing:

 
where  

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:

 
where   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*qEdit

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.

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

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.

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 knownEdit

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:

6 possibilities for   and   when   and   or vice versa. Of these 6 possibilities there will be agreement on   and either   or   will be definitely known.
8 possibilities for   and   when   and   or when   and  .

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:

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

Since   and:
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 problemEdit

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

1)  
2) the resulting   residue is a square (as a product, not necessarily as a residue).
3) Combined Divisor Methods

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:

  where   and  

and

  where   and   and where  

When P And Q Are Close Enough TogetherEdit

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:

Take   and  
  (around  ).
Next take the first number that is 3 mod 4 before the square root of 5003*4831 (that's the modulus we are studying)
  is close enough.
Then we do the following simple equation (expressed in mathematica)
Mod[-4831 5003 PowerMod[16, -1, 4903], 4903]=450
 , in this case, is the product:  
As such the following equation is true:
 
or
 
so   and  
As such we can take
 
or
 

When B*E Is A SquareEdit

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:

   
 
 
 
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):
 
Now, simply, square this above number to get our B*E as a product, not a residue
  (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   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.

Combined Divisor MethodsEdit

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.

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

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.

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

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.

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

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

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

If you take a factor of  , a factor of  , and divide them, you get the following:

when   and   then
 

Since:

 

and

 

and

  thus the switch between the denominator and the numerator of the other factors.

If you square this then you get:

  which are the other factors of (p-q) and (p+q) besides 5 and 12.

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.

Equivalent Square ConsiderationsEdit

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  .

Example 1Edit

Given:

1)  
2)  
3)  
4)  

Now make the modulus,  , via

  and  

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:

 
 


Example 2: When Y Is A Factor Of P-QEdit

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:

1)  
2)  
3)   is a divisor of  
4)  
5)  

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!

When X Is A Factor Of P-QEdit

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

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

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  

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

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:

Example 1Edit

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]

The Implications For RSAEdit

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]

Looking At The Openssl RSA Key Generation Code For Common FactorsEdit

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 cipherEdit

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!.

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



The RSA cipher can now be attacked by a Discrete Logarithm AlgorithmEdit

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.

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

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

  where  

Therefore, since  ,

  where  

(Note that   and   are known).

Thus, you can apply Pollard's Kangaroo Algorithm to any RSA Cipher to get  .

General Equation AppliedEdit

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.

Every Base Can Be Used In This EquationEdit

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.

A Close Call ON RSAEdit

According to [10] 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