Part 3 a - Odd (x+n) - Overview
(x+n)(x+n) = nn + 2d(n-1) + f - 1
What does this look like?
(x+n)(x+n) is odd
All odd squares = 1 + 8T
All odd square = 1 + the product of 8 triangles that are the same.
Visualise.
2d(n-1)
Why is (n-1) important?
Odd (x+n) - Examples
Let's use some real examples.
One odd (x+n) known, one odd (x+n) unknown
Rsa 100 has odd x+n and is the smallest.
Homework.
Of the unsolved RSA numbers, which is the largest that has an odd (x+n)?
We will use that one.
Hint:
Divide c by four.
The remainder tells you whether (x+n) is odd or even.
0,1 = even
2,3 = odd
This pattern in respect of the difference of two squares where c is odd.
Thank you!
Sounds good.
We'll walk through RSA 100
and then RSA 490
The factor tree is used to factor d and e.
Factoring these (and down the tree) allow for the factoring of c.
For odd (x+n) we'll walk through how each of the eight triangles (+1) are constructed to make (x+n)(x+n) and build an algorithm.
Once that is demonstrated, we'll look at the short cuts using the grid.
Thanks!
The key here is first understanding how the (x+n) square being added to c is constructed in terms of also being analogous to an L shape on the side of the square of d sides which must incorporate the remainder e in the L shape (or incorporates the 'gap' made by f).
We will build up the code a sub steps of Part 3.
After demonstrating with with odd (x+n), we will factorise the examples, the remaining RSA odd (x+n) numbers, then show Part 3 b which are the even (x+n).
Once the factorisation methods are complete, the short cuts via patterns in The Grid (e,n) will be clearer.
What we're going to do is walk through RSA 100.
It's big enough to make "irrelevant" patterns disappear, since it's factorisation is known, it allows us to follow the explanation more clearly.
For those interested in symbolism, you'll see a bunch to do with pyramids (square base) and triangular numbers, with the tops of triangles missing or "detached".
The process for producing the first algorithm is clearly ancient.
Here is the code in C# for handling creating triangles of arbitrary size.
/// <summary>
/// Tn = (nn + n)/2
/// </summary>
/// <param name="base_t"></param>
/// <returns>Triangle number from base</returns>
public static BigInteger Triangle(BigInteger base_t)
{
BigInteger square = BigInteger.Multiply(base_t, base_t);
BigInteger square_side = BigInteger.Add(square, base_t);
return BigInteger.Divide(square_side, two);
}
Here is code for calculating n from the base (x+n), c and d
n will be correct for a (x+n) that works, otherwise it is a result that is used subsequently to calculate whether an (x+n) exists before the (x+n) value for the product of 1 and c.
public static BigInteger Get_n_from_odd_triangle_base(BigInteger bs, BigInteger c, BigInteger d)
{
BigInteger triangle = Triangle(bs);//Create triangle from base
BigInteger eight_base = BigInteger.Multiply(triangle, eight);//multiply by eight
BigInteger XPN = BigInteger.Add(eight_base, one);//add one to create (x+n)(x+n)
BigInteger DPN = BigInteger.Add(XPN, c);//(d+n)(d+n)
return BigInteger.Subtract(Lib.Sqrt(DPN),d);//sqrt((d+n)(d+n)) - d = n
}
The square root method referenced above:
I put this in a library class called Lib but it can be switched out and put into whichever class you're using.
public static BigInteger Sqrt(this BigInteger number)
{
BigInteger n = 0, p = 0;
if (number == BigInteger.Zero)
{
return BigInteger.Zero;
}
var high = number >1;
var low = BigInteger.Zero;
while (high low + 1)
{
n = (high + low) >1;
p = n * n;
if (number < p)
{
high = n;
}
else if (number p)
{
low = n;
}
else
{
break;
}
}
return number == p ? n : low;
}
I didn't write the square root method but it is tested.
Here is the square root of RSA 2048
158732191050391204174482508661063007579358463444809715795726627753579970080749948404278643259568101132671402056190021464753419480472816840646168575222628934671405739213477439533870489791038973166834068736234020361664820266987726919453356824138007381985796493621233035112849373047484148339095287142097834807844
And the remainder of RSA 2048
149730827186590819409161975355863102499674499386960841184873248110419525705142414412560340457818822465695973580080183089801154577153055685206470161899420076208154943348665238647007714095089342669905666884517354400122833485897064098153958317993833609635063079613328500485188782423277886515290863800949716792021
And RSA 2048 itself:
25195908475657893494027183240048398571429282126204032027777137836043662020707595556264018525880784406918290641249515082189298559149176184502808489120072844992687392807287776735971418347270261896375014971824691165077613379859095700097330459748808428401797429100642458691817195118746121515172654632282216869987549182422433637259085141865462043576798423387184774447920739934236584823824281198163815010674810451660377306056201619676256133844143603833904414952634432190114657544454178424020924616515723350778707749817125772467962926386356373289912154831438167899885040445364023527381951378636564391212010397122822120720357
Here are the values for RSA 100 we'll be using.
They are a bit shorter!
public static string Rsa100c =
"1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139";
public static string Rsa100a = "37975227936943673922808872755445627854565536638199";
public static string Rsa100b = "40094690950920881030683735292761468389214899724061";
public static string Rsa100d = "39020571855401265512289573339484371018905006900194";
public static string Rsa100e = "61218444075812733697456051513875809617598014768503";
public static string Rsa100f = "16822699634989797327123095165092932420211999031886";
public static string Rsa100n = "14387588531011964456730684619177102985211280936";
public static string Rsa100x = "1045343918457591589480700584038743164339470261995";
public static string Rsa100x_plus_n = "1059731506988603553937431268657920267324681542931";
The image above shows 8 triangles of equal size plus a unit square.
This image divides up the odd square (x+n)(x+n) into eight equal triangles plus one unit square.
For RSA 100, n is even, since x is odd and d+n is even. (Thank you to anon who pointed out the pattern for mod 4 was for d+n)
Since n is even and n squared makes up an even square as part of (x+n)(x+n), then the odd square (n-1)(n-1) can be shown as a set of "sub-triangles" of (x+n)(x+n) as shown in the image.
For odd (x+n), the base of each of the eight triangles is ((x+n)-1)/2
Indeed
f = 2d - 1 + e
For RSA 100:
f = (39020571855401265512289573339484371018905006900194) + (39020571855401265512289573339484371018905006900194) + 1 - 61218444075812733697456051513875809617598014768503
=
16822699634989797327123095165092932420211999031886
Correction:
f = 2d + 1 - e
Absolutely
In the diagram of 8 triangles + 1, the +1 is donated by f.
16822699634989797327123095165092932420211999031885 + 1
From the equation:
(x+n)(x+n) = nn + 2d(n-1) + f - 1
The value f donates another one unit to give:
nn + 2d(n-1) + f - 2 = 8Tu
Where for even n and odd (x+n)(x+n), u = ((x+n)-1)/2
f-2 = 16822699634989797327123095165092932420211999031884
We then use the method below (posted earlier) to find out what n would be, if this was the correct base, knowing that the base is either larger or smaller.
public static BigInteger Get_n_from_odd_triangle_base(BigInteger bs, BigInteger c, BigInteger d)
{
BigInteger triangle = Triangle(bs);//Create triangle from base
BigInteger eight_base = BigInteger.Multiply(triangle, eight);//multiply by eight
BigInteger XPN = BigInteger.Add(eight_base, one);//add one to create (x+n)(x+n)
BigInteger DPN = BigInteger.Add(XPN, c);//(d+n)(d+n)
return BigInteger.Subtract(Lib.Sqrt(DPN),d);//sqrt((d+n)(d+n)) - d = n
}
If I put the correct base in (x+n), the result is n
BigInteger xpn = BigInteger.Add(x, n);
BigInteger half_xpn = BigInteger.Divide(xpn, two);
BigInteger test_correct_base = Get_n_from_odd_triangle_base(half_xpn, c, d);
Try this yourself (note that divding x+n by two removes the odd one)
So, we have the 8 bases of our triangles made of f/40. We know that there are four left over. We then know that if the base of f/40 is too small, then the number of 2d to add must have the same left over on the last d to create the final base of each triangle. THIS is key.
I'll add some diagrams to show what I mean so far.
In this diagram, somewhere in each triangle, there is a part that is five units wide, that we hope is smaller than (x+n) and larger than n.
The middle of each blue bar is (f-2) div 40, so the base of a triangle with that bar would be ((f-2) div 40) + 2, the top of that bar would be ((f-2) div 40) - 2. The five parts together add up to (f-2) div 40.
Plus the remainder of 4 unit squares from (f-2) mod 40.
We have a method to calculate what n would be if we used our blue base of ((f-2) div 40). This n will call n0, to make it different from the value of n that will be our solution.
We will add a method to calculate what would be missing from the triangles if we could only fill them with n0 squared and multiples of 2d.
That gap will allow us to use more geometry of triangular numbers to establish what multiple of 2d could be added to make our eight triangles.
That geometry with multiples of 2d will give us the solution, if it exists (which in our example we know it does). If doubling the width of the chunks of (f-2) didn't give us a solution, the number c would be prime, the worst case (doubling the width of (f-2) chunks very quickly determines this as the number of times it doubles is logarithmic in the length of (f-2)).
So far, it should become clearer that increasing the length of c adds to the number of calculations in the logarithmic of half the length c in bits. Hence why the overall complexity is < O(log m) where m is the length of c in bits.
Bear with me as we walk through the rest in stages.
Thanks!
We will get to the sono experiments.
Coincidence? ;)
Base in that context referred to the base of a triangle
Thanks for being Board Owner. No problem with anyone using names or not here. It's as much up to you guys.
Yes. I'll be doing a recap. Adding another function and then demonstrating on an unsolved RSA number after walking through the rest of RSA 100.
Thank you, that's great.
The next function takes our triangle base made out of (f-2)/40 which is five units thick and our value of n0 and calculates how many lots of 2d would be needed to fill in the gap in our 8 triangles, taking into consideration the space taken up by the 8 triangles made with a base of (n0-1)/2.
public static BigInteger Get_Remainder_2dnm1(BigInteger bs, BigInteger d, BigInteger n, BigInteger f)
{
BigInteger triangle = Triangle(bs);//Tbs
BigInteger eight_base = BigInteger.Multiply(triangle, eight);//8Tbs
BigInteger XPN = BigInteger.Add(eight_base, one);//8Tbs+1
BigInteger two_d = BigInteger.Add(d, d);//2d
BigInteger nm1 = BigInteger.Subtract(n, one);//(n-1)
BigInteger two_d_nm1 = BigInteger.Multiply(two_d,nm1);//2d(n-1)
BigInteger XPN_mfp1 = BigInteger.Subtract(XPN, BigInteger.Subtract( f,one));//(x+n)(x+n) - (f-1)
BigInteger resultpN = BigInteger.Subtract(XPN_mfp1, two_d_nm1);//(x+n)(x+n) - (f-1) - 2d(n-1)
BigInteger result = BigInteger.Subtract(resultpN, BigInteger.Multiply(n,n));//(x+n)(x+n) - (f-1) - 2d(n-1) - nn
return result;
}
We require a couple of diagrams to explain this part.
It would be good if you test the code above with the correct values to show it works for the known correct values for RSA 100.
I will add several diagrams next.
These diagrams will show for RSA how the (x+n)(x+n) square MAPs onto the side of the dd + e square and remainder.
The colours in the MAP will be the KEY to GUIDE you through the process of how the algorithm works.
Your work is impressive. I spent seven years putting this together and the acceleration of a group on understanding is phenomenal.
*RSA 100
Thanks!
Recap:
If d is even and e is odd, the remainder can be split into two even lengths and one left over.
Regardless of the length of e, this is possible.
For RSA 100 or generally for any odd e.
In this case for an odd c, f will be even.
f is even
In the diagram, f will be long, the shorter e is and vice versa
If we add the other components, we make a square.
The components above are n squared minus one, f and 2d(n-1).
The last component is two rectangles.
Note the symmetry.
The next diagram illustrates that (f-2) is broken into pieces, 2(f-1) + 1 + 1.
We know that to create a square (d+n)(d+n)
Which is c + ((x+n)(x+n)), then we are adding a square.
The pieces of f can be anywhere in the square.
We are creating a method that USES f as a guide to find how to construct the square.
After all that, for those that are interested, we'll then use the virtual quantum computer patterns in the original grid to short cut all this.
Those who are good with their grid diagrams, can you show any examples of how all the pieces fit together for smaller examples with the triangles?
The only piece missing before is the left hand big square with the pieces added to the side.
Should make for a good diagram. Particularly with respect to the contribution of 2d(n-1) and how the symmetry of that looks.
Hint:
Build up your diagrams for small examples of the same time from the smallest incrementally upwards.
Try this group:
odd e, even d, odd (x+n)
From the smallest upwards incrementally.
Notice any patterns with f?
For those of Faith. Let those who would seek an understanding know where we are going.
The Scroll and the Lamb
5 Then I saw in the right hand of him who was seated on the throne a scroll written within and on the back, sealed with seven seals [P=NP Millenium Prize Problems]. 2 And I saw a mighty angel proclaiming with a loud voice, “Who is worthy to open the scroll and break its seals?” 3 And no one in heaven or on earth or under the earth was able to open the scroll or to look into it, 4 and I began to weep loudly because no one was found worthy to open the scroll or to look into it. 5 And one of the elders said to me, “Weep no more; behold, the Lion [British] of the tribe of Judah, the Root of David, has conquered, so that he can open the scroll and its seven seals.”
6 And between the throne and the four living creatures and among the elders I saw a Lamb [Spring birth] standing, as though it had been slain [Addiction], with seven [binary III = Third] horns [Day or Dawns] and with seven eyes [binary moons ooo = March], which are the seven [III = 3; Son,Father, Spirit] spirits of God sent out into all the earth. 7 And he went and took the scroll from the right hand of him who was seated on the throne [Gives example of P=NP to all who seek understanding, freely without profit]. 8 And when he had taken the scroll, the four living creatures and the twenty-four elders [United Nations Security Council] fell down before the Lamb, each holding a harp, and golden bowls full of incense, which are the prayers of the saints [Desire for Global Peace].