>>5141

VA - Still going around in circles with the iterative approach.

>>5125

MM - we are iterating towards (1,c).

Revised c=259 pictures attached at n0=2, n0=3, n0=4 and n=6. The previous pictures didn't display the fact that both the (x+n)(x+n) and (d+n)(d+n) squares were changing sizes on each iteration. These pictures are more accurate. x+n square is outlined in red. d+n square is dark grey. I've also highlighted the "r" blocks, which is the question I'm looking to pose with this post.

We start with a triangle base u. Calculate an estimated small square est_XPN from 1 + 8*T(u) and maybe some remainders.

Next calculate the n0 = sqrt( c + est_XPN ) - d. This may or may not be the n we are looking for.

To determine this, we use the Get_Remainder_2dnm1 formula to calculate the difference between the estimated XPN, and the n,d,f formula. Simplified, this is essentially:

remainder = est_XPN - ((n0 * n0 - 1) + 2d(n0 - 1) + f)

If the remainder = 0, we have a match.

Otherwise, according to VQC:

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

Unless I am missing something, that gap is the remainder from Get_Remainder_2dnm1.

And in order to be useful, it would have to tell us more than simply how to fill the square we already know.

So what could it be?

During his explanation for RSA 100, VQC shifted from using (f/40) to (f-2)/40 as the triangle base.

>>4334

>>4337

>Since f can be divided by 5, we can make a base for each triangle which is made of (f/40), still with 4 left over.

And then f-2 took over.

>>4342

>>4343

Tried both with and without mod handling, and the results with larger numbers were similar.

I am posting 2 examples for my latest iterative process for a matching record at c=259, and a failed result at c=14596111.

The current process uses (f-2) / 40 as the incremental u, does not included either the (f-2 mod 40) or (d mod 40) in the totals, although they are displayed in the grid.

The previous u is carried forward from the last calculation and is the starting position for the next f-2 chunk to test for est u. Also showing estimated values for T(u), 1+8T(u), n0, the remainder from 2d(n-1), and x+n values.

Finally, checking those results again to determine if a match and the difference to the solution x+n.

Reason for the double checking of the 2d(n-1) remainder, is that I am unsure where the mods need to be included in the calculations, and this gave a way to tinker with different combinations to see what was happening.

Each iteration is also checking +/- 2 u values for possible matches.

Not sure if the -20 x+n diff for c=14596111 is coincidental or related to the same value from (d mod 40).

Just looking to see if anyone has any other ideas to try out here.

>>5168

Teach - in looking at that >>4678 post, and VQC's previous question "Why is (n-1) important?".

Doesn't it seem that n-1 gives the width of one side of the nn-1 square?

With regards to the 2d(n-1) contribution to the triangle, I posted a few pictures in the previous thread that connected the (x+n)(x+n) square for the prime solution to the starting c small square.

>>4758

This idea, and subsequent posts, was the closest I've come to understanding how the triangles work. The red blocks represent the 2d(n-1) contribution. When coupled with the f and (nn-1) pieces in the center prime small square, always form an outlining square or "capstone".

Those formulas work everywhere, but I wasn't able to figure out a way to arrive at that "capstone" square.

Same iteration problem that we're running into now with f-2.

>>5172

I went about the problem a bit differently than VQC explained, so I may have gone down a wrong path. Who knows?

The image VQC posted shows the relationships between small and big squares of a single record.

I combined the nn-1 + 2d(n-1) + f formulas from both the c and prime records into a single image. Think of them as one square layered on top of the other, sharing the f value and portions of the nn-1 and 2d(n-1) values.

To me this represented a nice growth perspective. Fractal even.

The positioning of the f value didn’t really matter.

What was really interesting was the appearance of the 2d(n-1) as a square every time. And then the ability to represent the inner nn-1 algebraically.

The relationship definitely exists. But don’t know how to connect the dots so to speak.

>>5174

>>5183

Pic attached for c=87 is an attempt to explain the "capstone area", and how it could be used as a basis for the iterative search.

It seems to me that there are 2 ways to iteratively find a solution. Both have been problematic.

The first is to start at a sufficiently small triangle base and iterate in chunks of (f-2)/40 towards the c (x+n)(x+n) square. Using the remainder 2d(n-1) = 0 along the way to determine if an n match has been found.

The second, that I pursued in the previous thread, is to iterate towards the "capstone square" which always lies somewhere between the prime and c small squares. The problem here was determining if a solution was found.

Both of these approaches share a problem of handling mods.

In >>5177, for odd (x+n) test cases, the "capstone square" can be defined as 1+8T(u) plus a remainder (if any) that is divisible by 8.

In the picture, the "capstone square" is the middle red square plus the additional remainder of 48. (6 allocated to each triangle). Note the symmetry. This "capstone square" + remainder includes the f, nn-1 and 2d(n-1) portions of the prime square we are looking for, plus the additional 2d(n-1) portion from our starting position.

The legend and math breakdown on the right hand side shows how the different squares are calculated from shared pieces.

With this approach, we are searching for the total area of the capstone. See the "Capstone Info" box.

A reasonable starting position for the search can be calculated as 2d(n-1) + f from our initial c record. The only piece we are missing from the "capstone square" is the nn-1 prime portion we are looking for.

The point of determining this "capstone square" is to calculate the "8 Triangle bases" from the c (x+n)(x+n) square - the dark purple area. Recall that VQC split his triangle into a base and capstone. >>4322

From there, the prime solution is trivial.

In order to take this further, we may need some way to incorporate the Get_n_from_odd_triangle_base and Get_Remainder_2dnm1 to relate the "capstone square" and remainder to our original c value.

What's also interesting about this approach is that outside the prime (x+n)(x+n) square, we're only trying to determine "how many lots of 2d would be needed to fill in the gap" that VQC mentioned.

>>5204

There is more geometry we can bring to bear to find our solution.

Attached is a partial picture for the same c=87 with labels indicating different u and remainder values.

On the right hand side is an explanation of how the differences between each triangle of the (x+n)(x+n) squares can be calculated as a trapezoid, following the basic formula Area=h(b1+b2)/2.

The first shows an example calculating the triangle base from the prime (x+n)(x+n) without any remainder.

The second shows an example calculating the triangle base using the capstone with a remainder.

Obviously both calculations rely on our ability to iterate to a correct u value (either for the prime or capstone squares). But perhaps this can assist along the way.

>>5212

VA - think we're getting close.

The key to the problem with iterating, I believe, lies in understanding how the remainder works.

>>5204

In the "capstone square", there is a remainder of 48 (6 per triangle). This value is different from Get_Remainder_2dnm1. Each iteration (unless by chance we happen upon a perfect match), is going to be off by a remainder evenly divisibly by 8.

In >>5206 it is labeled as "capstone remainder".

We need a formula to calculate this.

>>5214

The tons of different tests I've already tried. Which is why I've switched to spreadsheets and diagrams.

The "capstone square" that I keep mentioning is a known point between the c and p records. We can calculate it directly. Which means it can tell us something about how the squares behave when they're not "perfect" - so to speak.

When there is a remainder, that remainder will fall in the u+1 portion just outside of the u square. So for the c=87 example, the 48 remainder falls in the 4*(2(u+1)+1) range. This is the perimeter of the square surrounding u. So if u=12, the surrounding perimeter is 108. 48 units of that is our remainder, and the rest goes towards balancing out the difference of squares formula.

The remainder is always divisible by 8, so there are a number of potential remainders within this range. What makes the 48 so special?

Attached are 2 spreadsheets to explore this idea for c=87 and c=259. The green highlighted row represents the "capstone square" that provides the nn-1 solution.

I'm trying to figure out what determines the "capstone square" remainder from these list of choices. Perhaps understanding this will lead to a more accurate iteration algorithm.

I think I understand how to fill in the missing pieces in the iteration process that were giving inconsistent results in previous tests.

This is a work in progress related to >>5215 for c=87, and a continuation of trying to understand the "capstone square" remainder in >>5204 and >>5206.

Pic attached for c=87 shows a simple iteration of u. For each u, I am then iterating a remainder factor from 0 to u. (see the remainder offset column (r off)).

The formula for each estimated (x+n)(x+n) is: 1+8T(u) + 8*(r off).

For each u, there are 0 to u remainders possible.

This formula produces a difference of 8 between each iteration. And hits both the primary, capstone, and starting c squares properly. Something I was previously unable to do just by manipulating the u.

Next step is to add back in the (f-2)/40 for bigger jumps.

>>5230

>>5230

>>5236

Alright guys, I've taken the iteration a bit further and am now including the (f-2)/40 for bigger jumps.

Please bear with me as I try to explain and forgive the small pics attached.

There are 2 variables that control the iteration process. The first, fm2_factor, is the number of (f-2)/40 chunks to include in the triangle base (u) (see the "#" column), and the second, rm_factor, is the number of chunks of (f-2)/40 to include in the remainder calculation (see the "r off" column).

The estimated (x+n)(x+n) square (est_XPN), is calculated as follows:

est_XPN = 1 + 8 * est_tu + ((f-2)%40) + (rm total)

where est_tu = T(fm2_factor * (f-2)/40)

and rm_total = 8 * (rm_factor * (f-2)/40) + ((f-2)%40)

The rm_total is only included if the rm_factor != 0.

Conceptually, we are creating a square from triangles and then adding chunks of (f-2)/40 around the square, checking for a match at each step.

In my previous example for c=87, the area around the square to check was simply u+1 and fit within the 4*(2(u+1)+1) perimeter. "For each u, there are 0 to u remainders possible."

For larger gaps in u, however, we need to expand the possible area for the remainder search to include up to the next possible u: (fm2_factor + 1) * (f-2)/40). See column "rm u" in the examples. Not accounting for this gap is what lead to inconsistent results in previous attempts.

The area that could possibly contain the remainder can be defined as follows:

remainder_max = 8 * (T(rm_u) - T(est_u))

This maximum remainder is essentially the "triangle base", and is necessary to know when to switch from iterating through a remainder to the next potential u. The "rm next" column is a calculation for the next total remainder.

rm_next = 8 * ( rm_factor + 1 ) * _fm2_chunk

When the next remainder is greater than the max possible remainder, the rm_factor is reset, and the fm2_factor is increased.

The pictures attached are various test cases from small to medium sized numbers, and are an attempt to illustrate that the process works, and that there are a couple of pitfalls that still need to be addressed. Number of iterations and elapsed time for each test are included.

Tests for 363, 6107, 7463 just show the process working for small numbers.

For 208975787, 208997671, and 209194627 note the additional iterations and processing time required for small values of f.

For 9872452111 and 9872801899, the starting fm2_factor of 0 enables searching of smaller values of n.

For 9874400051, the rm 2d(n-1) didn't equal zero, but the n0 value does equal the prime result. The concern here is that a minor adjustment to this algorithm needs to be made to tackle larger numbers and/or an additional validation method needs to be written.

This may or may not work for RSA sized numbers. The number of iterations required is still too large to effectively test. Most likely, we need another breakthrough with regards to the geometry of numbers to make this more efficient.

>>5256

VA - I'll try to summarize my recent posts and the current iterative approach using f-2 chunks of (f-2)/40.

1) Starting from a 0 factor, create an initial square as 1+8T(u) + remainder. Where u is a multiple of chunks and the remainder is the mod.

2) Calculate the next u (I'm calling this rm u) as u + (f-2 chunk).

3) Within the area between u and rm u, a solution may be found. Iterate through this section by adding 8 times incremental f-2 chunks to the initial square, plus another remainder.

4) At each iteration, calculate the n0, and remainder for 2d(n-1). Subtract this remainder from the estimated XPN to get a final XPN.

5) This final XPN is a perfect square with no remainder. This is the x+n rm column and is only a sanity check. Test the final XPN against the rm 2d(n-1) to see if we have a match.

The recent work on the "capstone square", lead to an understanding of how the remainders are always evenly divisible by 8. Which in turn lead to a more accurate iterative approach.

The slow part of this process is checking within the u and rm u area.

In trying to understand a bit more about the remainders, I stumbled upon something that seems too coincidental not to share.

This has not yet been verified against other test cases.

The pics attached are for the last iteration that solves the prime for c=6107. A full output of the execution can be found at pastebin.com/EnNfXudK if anyone is interested. These pictures show only 1 of the 8 triangles that will eventually make up the final (x+n)(x+n) square.

The first picture (c6107_triangle_base_triangles) shows how the triangle base can be represented as the sum of two triangles.

The triangle base is T(42) - T(39) = 123, which is equal to T(12) + T(9).

And T(12) = 78 just happens to be the remainder portion that solves our prime problem. (!!!!!) The math breakdown is on the right hand side.

The second picture (c6107_triangle_iteration_mapping) shows how the T(39) and T(12) triangles are mapped into the T(41) solution triangle.

Pay particular attention to the 3 dark green squares on the bottom right side of the triangle. These 3 remainder squares represent a portion of the original (f-2) mod 40.

VQC hinted at this in the previous thread:

>>4337

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

In this example, (f-2) mod 40 = 12. We add 12 to the initial 1+8T(u) triangle, and then again in the remainder iterations. So the total mod to be added is 24.

In my picture, 3 dark green squares, 8 triangles. 24.

If this breakdown of the triangle base into smaller triangles holds for other test cases, then we have a way to speed up the iteration process.

>>5264

>Does x+n diff become negative

The x+n diff column is a sanity test against the known prime solution x+n value. We won't know this value when searching through unsolved RSA numbers. I just use it as an indicator.

u is a triangle base. For odd x+n values, it is defined as u = (x+n-1)/2. And the area for any triangle base is T(u) = u*(u+1)/2.

>>5260

>>5268

I tried converting the linear search into something that will handle T(u) values.

See pastebin.com/qEgSaq4r for the the full iterative output for c=6107.

The main difference here is that instead of computing the remainder as a multiple of (f-2)/40, I am using the multiple of (f-2)/40 as the triangle base to the T(u) formula. This has the effect of both dramatically improving performance, and at the same time creating inconsistent results for different test cases. For the c=6107 example, it has reduced iterations from 287 to 53. For other test cases, the results are hit and miss.

Recall that the iterative solution presented previously leads a prime solution for ANY odd x+n (given enough processing time). And so we need a faster way to iterate.

VQC mentioned previously in a DM that the factor tree was one way to understand the recursive nature of solutions.

To that end, I think we need a different approach to solving this problem. And I think the factor tree we worked on previously now needs to come into play.

See the attach pic for a "triangle" analysis of c=6107 and c=7463.

The c=6107 example is just another breakdown of the previously presented final iteration.

For c=7463, however, the last iteration doesn't fit as cleanly into 2 triangles. I am attempting to show in this spreadsheet how we could conceptually recurse into the correct x+n value using the factor tree. Notice that there are 5 separate triangles, plus the 2 mod values that when added together equal the prime solution.

The solution for c=7463 was produced by trial and error just to illustrate an idea.

Also recall that in the previous thread CA found an interesting connection between the x+n and d values as numbers scaled higher.

>>4998

>>5024

I'm not quite sure yet how to incorporate these different ideas into a unified solution. But certainly something to consider further.

>>5467

Started to integrate the factor tree into the iterative search process.

Currently using the c and f values from the original starting position, and substituting in d from the node being evaluated.

Unfortunately, doesn't look like rm 2d(n-1)=0 is usable with this combination of values. So previous theory won't work.

However, the c=6107 pic attached does show something interesting in the very first calculation. Notice the (x+n) and u values relative to our prime solution. I'm seeing similar sized jumps on a number of other test cases, but not all.

For subsequent nodes, I'm calculating estimated factors based on the final XPN in the previous node.

>>5473

Continuing with the factor tree integration.

Pic attached is for test cases c=6107 and c=7463 showing iterative search results now satisfying rm 2d(n-1)=0 constraints for each node in the factor tree. Full output available at pastebin.com/bDv31qjY.

Main change here is that I am using node specific c, d, e and f values instead of my previous example that attempted to use the starting c and f values. For the c=6107 example, the c values for each node are 3, 39, and 6107.

So perhaps we do have valid small squares at each level of the factor tree after all.