baker - thank you. I put together "test cases" for all the unsolved rsa numbers. This project is mind boggling.
Working through some tree ideas. Nothing to share yet.
Posting a work in progress for any feedback.
Pics attached for c=145, 901 and 6107.
Shows the factor tree with various calculated columns. Each d node is a perfect square. We can calculate an f, x, and assuming n=1, the small square. We can also get to the the next perfect square at c+f. And the difference in squares between them.
Below each tree is a small square analysis between the c and prime records, their corresponding na records, and their na records compared to the genesis cell. Each analysis includes all prime factors for the difference in small squares.
My thinking is that perhaps the factor tree can somehow be used to arrive at the difference between the squares.
Hey MM - these are excellent drawings.
Have you read this VQC hint?
>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).
Would adding f to your diagrams add any clarity?
The factor tree for this record is:
-
259 (c)
| + 16 (d)
| | + 8 (/2)
| | | + 4 (/2)
| | | | + 2 (/2)
| | | | | + 1 (/2)
| + 3 (e)
| | + 1 (d)
| | + 2 (e)
| | | + 1 (/2)
Interesting how there is a 3x3 square around the middle. Corresponds to 3 (e) in the tree?
One side of the triangle is 16/2 = 8. Also in the factor tree (although it would be divided out by 2).
Still looking into the n0 calculation and possible subsequent calls.
I did notice in a few of my test cases that the result from (2dnm1 - ((f-2) mod 8)) equaled a triangle number.
Don't know what to make of this.
Example for c=6107:
c = 6107
d = 78
f = 134
(f-2) = 132
(f-2) % 8 = 4
(f-2) / 8 = 16 (triangle base)
n0 = Get_n_from_odd_triangle_base( (f-2)/8, c, d )
n0 = 6
remainder 2dnm1 = Get_Remainder_2dnm1( (f-2)/8, d, n0, f )
remainder 2dnm1 = 140
2dnm1 - (f-2) % 8
triangle number? = 136
(16*17)/2 = 136
>Notice any patterns with f?
the f parity matches the d parity.
>odd e, even d, odd (x+n)
Possible test cases including parity:
115=5x23 - (15,48,5) = {15:48:10:9:1:115} = 115; f=6; (x+n)=57; (d+n)=58
parity: e=odd, n=even, d=even, x=odd, x+n=odd, d+n=even, f=even
259=7x37 - (3,114,8) = {3:114:16:15:1:259} = 259; f=30; (x+n)=129; (d+n)=130
parity: e=odd, n=even, d=even, x=odd, x+n=odd, d+n=even, f=even
287=7x41 - (31,128,8) = {31:128:16:15:1:287} = 287; f=2; (x+n)=143; (d+n)=144
parity: e=odd, n=even, d=even, x=odd, x+n=odd, d+n=even, f=even
6107=31x197 - (23,2976,39) = {23:2976:78:77:1:6107} = 6107; f=134; (x+n)=3053; (d+n)=3054
parity: e=odd, n=even, d=even, x=odd, x+n=odd, d+n=even, f=even
7463=17x439 - (67,3646,43) = {67:3646:86:85:1:7463} = 7463; f=106; (x+n)=3731; (d+n)=3732
parity: e=odd, n=even, d=even, x=odd, x+n=odd, d+n=even, f=even
I believe so. This is a piece of the puzzle.
Think I've figured out the f calculations for the (x+n)(x+n) and (d+n)(d+n) squares that match the diagram posted by VQC.
pics attached for c=115, 259, and 6107 for odd e, even d, odd (x+n) combinations.
For the small square, f needs a bit of an adjustment to make everything work properly. I've introduce a new variable f0 to handle this.
f0 = (f-2)/2 + 1
Code to calculate the squares per VQC diagrams. >>4678
/// <summary>
/// (d+n)(d+n) = dd + f + e + 2d(n-1) + (nn-1)
/// </summary>
public static BigInteger Get_XPD_from_f( BigInteger e, BigInteger n, BigInteger d, BigInteger f ) {
BigInteger dsquared = d * d;
BigInteger twodnm1 = 2 * d * ( n - 1 );
BigInteger nsquaredm1 = n * n - 1;
return dsquared + f + e + twodnm1 + nsquaredm1;
}
/// <summary>
/// (x+n)(x+n) = 2d(n-1) + (nn-1) + (2(f0-1) + 1 + 1)
/// small square formula in terms of f where f0 = (f-2)/2 + 1
/// </summary>
public static BigInteger Get_XPN_from_f( BigInteger n, BigInteger d, BigInteger f ) {
// given an f, f0 is the modification required to fit it into the small square formula
BigInteger f0 = ( f - 2 ) / 2 + 1;
BigInteger twodnm1 = 2 * d * ( n - 1 );
BigInteger nsquaredm1 = n * n - 1;
BigInteger ftotal = 2 * (f0 - 1) + 1 + 1;
return ftotal + twodnm1 + nsquaredm1;
}
I've added the new XPN_from_f function into my test cases for Get_n_from_odd_triangle_base using n0.
Very interesting…
Pic attached for c=259, 6107 and 7463.
If you add the results from XPN_from_f (called with n0) to the result from Get_Remainder_2dnm1, you get a perfect square.
That's quite a coincidence.
Thanks Isee. If this turns out to be a path to the solution, then it is getting really clean and elegant.
Will look into the triangles further. Good stuff here.
Sure thing.
The growth of the small square and the elegance of the solutions >>4814, led me down a path of attempting to use the Get_Remainder_2dnm1 and other formulas to search for the red square in >>4758. Which is calculated as 2d(n-1) + f + (nn-1 from the prime solution).
To find that square, I attempted a really big jump using the original 2d(n-1) + f values, and then planned on iterating closer to the red square.
The examples in >>4820 show that we can get really close to that red square even without the (f-2) div 40 jumps. But that leads to a problem of knowing how to determine that a solution has been found.
As I haven't been able to figure that out, I am now looking at using the known result of Get_Remainder_2dnm1 == 0 to identify a correct solution.
Attached pic of larger value shows work in progress. Using the formulas and iterating via increments of x+n to arrive at a solution.
This value took 989 iterations. See the line 989 (p).
This doesn't include any (f-2) div 40 jumps (as I don't fully understand how to work with that yet) - but it does find a solution for any odd (x+n).
If someone can figure out the larger jumps…
Iterating through larger chunks on Rsa 100 is not going to be a problem.
Using multiple*( (f-2) div 40 ) as an example and increment the multiple by 1 each iteration, we will fly right by the solution on the 21st calculation.
Pic attached is the result of n0, remainder 2d(n-1) calculations. First group is +/- (x+n) by 10. Bottom group is +/- (x+n) by 1.
Perhaps we are meant to break down the formulas and work at the individual triangle level, instead of (x+n)?
Thoughts on iterating.
(f-2) / 40 makes up the triangle base of each of the 8 triangles. This is the number we are growing by multiples of 2.
(f-2) % 40 is the remainder.
(x+n)(x+n) = 1+ 8T(u) where u is the triangle base, and T(u) = (u(u+1))/2
Get_n_from_odd_triangle_base takes (x+n)/2 as a parameter.
Get_Remainder_2dnm1 takes (x+n - 1) / 2 as a parameter.
In order to test for a solution using the above formulas, we need to estimate what (x+n) would should be.
Formula for estimating (x+n):
(x+n)(x+n) = 1 + remainder + 8 * T(triangle_base)
(x+n)(x+n) = 1 + ( (f-2) % 40 ) + 8 * T( (f-2) / 40 )
(x+n) = sqrt( 1 + remainder + 8*T(triangle_base) )
Does this make sense?
Sample spreadsheets attached show how the estimated x+n calculations work.
An exact match was found for c=14904371.
Notice that the mod changes for each iteration.
Have tested this algorithm on large numbers (not RSA sized yet). The problem is handling the "proximate" records.
For subsequent iterations, the estimated small square formula may need to include the remainder from 2d(n-1).
(x+n)(x+n) = 1 + ( (f-2) % 40 ) + 8 * T( (f-2) / 40 ) + (remainder 2d(n-1))
Progress pics for c=14904371 and c=9874400051.
The "rm2dnm1" column is a running total of the "rm 2d(n-1)" result. This total is then added into the (x+n)(x+n), which is then part of the (x+n) value to test. When the "rm 2d(n-1)" becomes negative, the f-2 factor is increased and the rm2dnm1 total is reset. Checking proximate ranges for each row.
The f-2 factor is a larger jump and the "rm 2d(n-1)" is a fine tuning on each iteration.
This process is dependent on the base factor and proximate range searches. These examples use (f-2) div 256 and proximate ranges of +/- 4. Those were chosen by trial and error, but relate to f-2 being divisible by 4.
CA - I wrote a test around your "toOther" and "web" methods from >>4998.
Called them using the a and b values from our c and p records and noticed something VERY interesting.
Pic attached is for c=6107 and c=9874400051. But this holds true for all my other test cases including RSA100.
web.one = toOther(a, b*a)
web.two = toOther(b, b*a)
I then determined the d and e values for each of these results. And for giggles, added them together to get d+e.
For a and b values from the original c record, d+e is the same for the web.one and web.two.
But, for the a and b values from the prime record:
-
1/2 of the difference between d+e for web.one and web.two equals the (x+n) value we are looking for.
-
the d value for both web.one and web.two always equals the x+n value from our starting c record.
There is a link here.
Or to simplify
(web.two - web.one) / 2 == solution (x+n)
where the d for both web.two and web.one equals the original (x+n).
Some other nifty coincidences from these formulas:
( (d+n)(d+n) + (x+n)(x+n) ) / 2 - web.one == solution a
( (d+n)(d+n) + (x+n)(x+n) ) / 2 - web.two == solution b
web.one e - (x+n) = a
web.two e - (x+n) = b
(cc / 4) - web.one == a
(cc / 4) - web.two == b
I think you should come up with a better name for these methods!
VA - If I'm understanding this correctly, there seems to be a direct relationship between the x+n value for the entry c record, and the squares of these values as you go higher up the tree.
For example, for a = 31, b = 197, c=6107
web.one = 31 + (6107*6107)/4 = 9323893
web.two = 197 + (6107*6107)/4 = 9324059
The interesting parts here are that the sqrt of both numbers is x+n = 3053.
And the web.one number 9323893 is prime.
I have also checked a=5, b=29, c=145, and the web.one method also produces a prime number. 5+(145*145)/4 = 5261.