I'm still looking into this for now. One thing I noticed is that (e, 1)'s d will always be (e + 1, 1)'s a. Thus we can easily get the factor a for (e, 1). We know d, so we can get the t for d at (e, 1). Then we simply get a at t for (e + 1, 1) and we have one factor.
Since we won't have our c in (e, 1) it doesn't give any instant solution, but I think it is a useful observation.
By all means, keep at it! I don't want to discourage anyone, I'm just curious.
If we get a binary search to work (and one that beats sieve) then it's a great starting point. We might be able to optimize things further after that
> I'll show you all how to move easily from the first or second cell (odd or even e) to any value c and then any value that is the product of p and c, where p is a prime.
From VQC in thread #5. Have we solved this, has VQC showned it or is this still unsolved?
We've been told a few different things regarding finding c.
> If we multiply c by 105 ( 2 * 3 * 7 ) that number should appear in the column it belongs multiple times.
So far I don't know how to count those times (assuming VQC means the number of times that number occurs in (e, n).
> If we figure out the relationship between n * a, (n - 1) * a and a[t] and d[t] respectively we can use f.
Still not sure what this means. Is (n - 1) the previous n, or just n - 1? ProgramMathAnon has looked into into it at >>1896
I've been trying to wrap my head around this hint:
>> At the correct element in the grid at (e,1) where the value of a at that element equals the na we want, if you subtract 2d+1 from na then you are in the negative half of the grid in terms of e and the value at the same element in the first row will be (n-1)a
So let's generate an example:
>>e, n, d, x, a, b = rowForAB(5, 29)>>> e, n, d, x, a, b(1, 5, 12, 7, 5, 29)>>> 5 * 5 # = na25>>> 25 - (2 * d + 1)0
Now what? I assume this means that we expect 20 to be in (0, 1) at t = 4, but it's not there.
Again, not sure if this is useful, buuuuut
>>rowForAB(1, 1452)(0, 10368, 145, 144, 1, 21025)>>> rowForAB(-1, -1452)(0, -10658, 145, 146, -1, -21025)>>> 10368-10658-290>>> 290/2145.0
So what we see is that when changing from positive a, b to negative if affects the n by -(n +145 * 2).
>>rowForAB(52, 292)(0, 288, 145, 120, 25, 841)>>> rowForAB(-52, -292)(0, -578, 145, 170, -25, -841)>>> 578-288290>>> 290/2145.0
So this applies the record for aa, bb.
This means we have some kind of knowledge of n for -aa and -bb. I'm wondering if this can be combined to find the n (using na for (0, n)).
I'm not after negative x-records. I was playing with generating rows using negative numbers and saw that when I generate the record for a=1 b=145^2 I get n = 10368.
When I then generate the record for a=-1 and b=-145^2 I get n = -10658.
The difference between 10658 and 10368 is 2*d.
This pattern appears to hold true for all values, but I don't know if it is a useful pattern.
Generate two records, one for a, b and one for -a, -b. The n in -a, -b will be equal to
-(n - 2*d) // where n is the same as the n from the a, b record.
This isn't limited to aa, bb or c*c records.
>>rowForAB(101, 2887)(1066, 955, 539, 438, 101, 2887)>>> rowForAB(-101, -2887)(1066, -2033, 539, 640, -101, -2887)>>> (2033 - 955)/2539.0>>> rowForAB(4637, 6917)(4560, 114, 5663, 1026, 4637, 6917)>>> rowForAB(-4637, -6917)(4560, -11440, 5663, 10300, -4637, -6917)>>> (11400 - 114)/25643.0
It appears to hold true for any given a, b and their -a, -b counter part.
Yes it would appear so.
Also, we talk about f, but from what I gather what we are really doing is computing the difference of perfect squares.
So f = (2*d + 1) - e
We remove e, because it is our remainder of c from our "perfect square" d*d. So naturally c + f will be the same as (d + 1)(d + 1).
If we want to "jump" with f further we can use the general function f* = k( 2 * d + k).
So c + (2 * (2 * d + 2) - e) will give (d + 2),
c + (3 * (2 * d + 3) - e) will give (d + 3).
But I don't think we would want to use that to find n, that just seems like an overly complicated way of doing fermats factorization.
This is also trivial to find for (e, 1).
Generate the row for a=1, b=c. Get the t1 for (e, 1) where a=1 * n, then get a in (e, 1) at t2 = (t1 + n) = Nc.
I'm skeptical
>>print(generateGenesis(2145, 20), sep='\n')(290, 1, 145, 0, 145, 147)(290, 1, 149, 2, 147, 153)(290, 1, 157, 4, 153, 163)(290, 1, 169, 6, 163, 177)(290, 1, 185, 8, 177, 195)(290, 1, 205, 10, 195, 217)(290, 1, 229, 12, 217, 243)(290, 1, 257, 14, 243, 273)(290, 1, 289, 16, 273, 307)(290, 1, 325, 18, 307, 345)(290, 1, 365, 20, 345, 387)(290, 1, 409, 22, 387, 433)(290, 1, 457, 24, 433, 483)(290, 1, 509, 26, 483, 537)(290, 1, 565, 28, 537, 595)(290, 1, 625, 30, 595, 657)(290, 1, 689, 32, 657, 723)(290, 1, 757, 34, 723, 793)(290, 1, 829, 36, 793, 867)(290, 1, 905, 38, 867, 945)(290, 1, 985, 40, 945, 1027)
145 = 5 × 29147 = 3 × 7^2153 = 3^2 × 17163 is prime177 = 3 × 59195 = 3 × 5 × 13217 = 7 × 31243 = 3^5273 = 3 × 7 × 13307 is prime345 = 3 × 5 × 23387 = 3^2 × 43433 is prime483 = 3 × 7 × 23537 = 3 × 179595 = 5 × 7 × 17657 = 3^2 × 73723 = 3 × 241793 = 13 × 61867 = 3 × 17^2945 = 3^3 × 5 × 71027 = 13 × 79
5 appears as a factor 5 times while 29 only once.
>> A prime number appears once in a column. This is SIMPLE to calculate. This calculation is important. I call n for a prime number big_n or N
Are we confusing the terms for big_n or N?
I did another one now for 2 * c, with c = 61 * 101. 61 appears as a factor in (12322, 1) at t = 61.
But I don't see how we can use this to find the factors?
If we have to iterate over N cells in (e, 1) in order to find the proper factors, we don't have an algorithm that is O(log n).
For a given a, b the absolute value of negative x will point to the next cell with b, nextB.
For example, take (0, 8). Here there are multiple factors at play, so a,b = 1,25 the next b, nextB = 25, 81 won't appear until x = 20.
The negative x for a, b is -20.
It appears to hold true again for other numbers.
>>rowForAB(145, 1)(1, 61, 12, -133, 145, 1)
In (1, 61) at x = 133 you'll find a,b = 145, 533.
I'm not entirely sure what I'm doing or looking at, but let's say we want to move backwards from x.
We start with row for 1, 145
(1, 61, 12, 11, 1, 145)
We now know we want the record where x = -11.
Then a must be = 1
b = 1 + 2(-11) + 261
This gives b = 101.
rowForAB(1, 101)
(1, 41, 10, 9, 1, 101)
But here x = 9 and not 11. However, if we repeat these steps:
>>def rowNegX(n, x, a):... b = a + 2(-x) + 2n... c = ab... d = int(math.floor(math.sqrt(c)))... e = int(c - dd)... n = int(((a + b)/2) - d)... x = int(d - a)... return (e, n, d, x, a, b)...>>> rowNegX(61, 11, 1)(1, 41, 10, 9, 1, 101)>>> rowNegX(41, 9, 1)(1, 25, 8, 7, 1, 65)>>> rowNegX(25, 7, 1)(1, 13, 6, 5, 1, 37)>>> rowNegX(13, 5, 1)(1, 5, 4, 3, 1, 17)>>> rowNegX(5, 3, 1)(1, 1, 2, 1, 1, 5)>>> rowNegX(1, 1, 1)(0, 0, 1, 0, 1, 1)
I got the flu and been bedridden for a few days, so my head might still not be working correctly. I'm assuming my assumptions about rowNegX is correct, but since I'm not finding the record x = 11 something else is up.
Also, it appears this method allows us to go down in the tree.
We started with rowForAB(1, 145) and by the fourth iteration we have (1, 5) which is where a,b = 5, 29 is. So maybe this is actually the proper way to go about?
To calculate the amount of steps down from the record of a=1,b=c it's:
For even e:
k = sqrt(n - (e / 2))
For odd e:
k = sqrt((n - round(e / 2) - 1)/2 + 1)
k is the number of steps it takes to go from n to 1.
To go the other way, that is from k to n:
For even e:
(e / 2) + 2 * k^2
For odd e:
round(e / 2) + 4 * ( (k * (k + 1)/2)) + 1
I feel kind of lost right now. So much to explore, I don't know where to begin.
It appears that rowNegX can also give us the first cell in (e, n).
Examples:
{6:1:87:12:75:101}
{7:1:101:13:88:116}
{8:1:88:12:76:102}
>>rowNegX(75, -12, 1)(6, 75, 13, 12, 1, 175)>>> rowNegX(88, -13, 1)(7, 88, 14, 13, 1, 203)>>> rowNegX(76, -12, 1)(8, 76, 13, 12, 1, 177)
If we take an 'a' from (e, 1) and the x in the same cell and compute rowNegX(a, -x, 1) it will yield the first cell at (e, a).
I don't think traversing is the key, but it might provide more insight?
If you take a, b = 5, 157 you'll see it is in (1, 53). However if you take the row at a=1,b=5 * 157 and traverse down the tree with rowNegX, it will skip (1, 53) and go from (1, 61) to (1, 41).
It appears as if it only works for n's as defined by the a's in (e, 1)
Using rowNegX to move down the chain doesn't appear to be working for other numbers outside of (1, n). I tried with a = 1, b = 23 * 53 which gives me (63, 576).
But as I start moving down it jumps over to (2, n).
It could be that it works only for e=1 because there is an underlying pattern I haven't seen yet.
IF we can traverse down the list of n's, then shouldn't c % n == 0 at some point?
Since every prime factor and a's that occur in (e, n) for a given e and n exists as an n', then c should contain the n's it traverses down as factors.
I'm just thinking out loud here.
>>rowForAB(19, 131)(88, 26, 49, 30, 19, 131)>>> 26 + 30 # x + n = j56>>> rowForAB(192, 1312)(0, 6272, 2489, 2128, 361, 17161)>>> s(6272/2)56.0
I think these (0, n) records for the squared numbers is done by (x + n)^2. Which means it's j^2 since x + n = j.
And we know c = (d + n)^2 - (x + n)^2 since d + n = i.
Unless we can somehow coerce j for a,b out of c then I don't see how we can simply "get to" the (0, n) record that hold a^2, b^2.
I think I know why this rowNegX jumps to another e at some point.
I did a test:
>>rowForAB(1, 13 * 53)(13, 319, 26, 25, 1, 689)>>> rowNegX(319, 25, 1)(13, 271, 24, 23, 1, 589)>>> rowNegX(271, 23, 1)(13, 227, 22, 21, 1, 497)>>> rowNegX(227, 21, 1)(13, 187, 20, 19, 1, 413)>>> rowNegX(187, 19, 1)(13, 151, 18, 17, 1, 337)>>> rowNegX(151, 17, 1)(13, 119, 16, 15, 1, 269)>>> rowNegX(119, 15, 1)(13, 91, 14, 13, 1, 209)>>> rowNegX(91, 13, 1)(13, 67, 12, 11, 1, 157)>>> rowNegX(67, 11, 1)(13, 47, 10, 9, 1, 113)>>> rowNegX(47, 9, 1)(13, 31, 8, 7, 1, 77)>>> rowNegX(31, 7, 1)(0, 18, 7, 6, 1, 49)
There isn't any a = 1 for any n below 31 for e=13. Which rowNegX assumes.
Is there a way of creating a cell from knowing just (e, n, x)?
Are you using the same rowNegX method to iterate downwards in the (0, n) record?
I don't think that will work for large numbers like RSA.
I also don't know if traversing x is the correct method. It doesn't require f which apparently is used by VQC.
If VQC is still out here, a correction of path is most wanted
Thanks, but I noticed a pattern in x in the n records leaving x to not follow the same pattern for the rowNegX. For the rowNegX jumping down the x decreases by 2, but that isn't the case for all (e, n). Example (13, 29) x is 25, while for the rowNegX jumps it has decreased down to 8 by (13, 31). So something else is up.
It could still mean something though.
Why doesn't (13, 29) start with a = 1?
(Or any other n below 31 for that matter)
I'm still confused on the purpose behind generating the f. c + f = c + (d + 1)^2.
This leaves us with two squares, d^2 and (d + 1)^2 where c is somewhere in between these two.
Unfortunately that's way too many iterations. I wish it was faster, but I think we're missing something.
The speed of the algorithm VQC is talking about should solve all of those in waaaay less steps.
He said it was O(log n) where n is the number of bits in c.
For all those it should be done in only a few steps. If I understand it correctly, 2611447 should only take 3 operations.
For example, gcd (Greatest Common Divider) has a complexity of O(log a + log b) = O(log n). So we should have something equally fast, but for factorization.
> Why doesn't (13, 29) start with a = 1?
Ughhh, it's obvious now. We have two types of n-records for any given (e, n). Ones that are "prime" n's, that is they are n's which also exists as an 'a' in (e, 1) and we have "secondary" n's which are n's that exists as 'a' in (e, n) (n 1).
So the n's that don't exists as an a in (e, 1) will always be a multiple of an a in (e ,1).
Ah I follow you.
Unfortunately I haven't found a way. I did look for it when I was looking at the rowNegX for the zero column, but based on what I found the (0, n) for a^2, b^2 is equal to (x + n)^2, same for a=1,b=c^2.
So to know the difference between them you need to know a, b's (x + n) which we don't know from c (as far as I am aware).
I think I figured how to iterate over other records using rowNegX after "jumping".
We can find (e, n, 1) where a = 1 using rowNegX. So based on that:
>>rowForAB(1, 145)(1, 61, 12, 11, 1, 145)>>> rowNegX(61, 11, 1)(1, 41, 10, 9, 1, 101)>>> rowNegX(41, 9, 1)(1, 25, 8, 7, 1, 65)>>> rowNegX(25, 7, 1)(1, 13, 6, 5, 1, 37)>>> rowNegX(13, 5, 1)(1, 5, 4, 3, 1, 17)>>> rowNegX(5, -(25 + 3), 17)(1, 5, 30, 13, 17, 53)>>> rowNegX(5, -(45 + 3), 53)(1, 5, 76, 23, 53, 109)>>> rowNegX(5, -(65 + 3), 109)(1, 5, 142, 33, 109, 185)>>> rowNegX(5, -(85 + 3), 185)(1, 5, 228, 43, 185, 281)
It's a bit silly now, I'm negating the x-parameter on purpose now because it get's negated inside rowNegX. But the idea is as follows
Given the n = 5 we have (1, 5, 1) which we know is {1:5:4:3:1:17} we then compute a new b:
b = 17 + 2 * (2 *5 + 3) + 2 * 5
The original equation for is:
b = a + 2 * x + 2 * n
So in our new case, x = (2 * 5 + 3).
The 5 is because our n = 5 and 3 is because the first x is 3.
This will give us b = 53 and the next record is as follows:
{1:5:30:13:17:53}
We repeat it:
b = 53 + 2 * (4 * 5 + 3) + 2 * 5
Which gives us a b = 109. The next record is:
{1:5:76:23:53:109}
Now I know that there is another record between here which is:
{1:5:12:7:5:29}
But that exists because we have an interleaved n. The record above exists from the a = 25 from (5, 1) and is not a part of the a=1, b=17 pattern. It's a separate pattern existing in the same n-record.
If I'm rediscovering things and we already have names for these thing then apologies for my lack of terminology.
This rowNegX was supposed to only be used to move about with a negative x, but I'm over using it for other things. I'll try to think of a better name for it. We should also have two functions maybe. One for moving with positive x values and one for negative.
As you continue to jump using rowNegX you'll eventually wind up at (0, 0, 1) which loops over itself.
Well I don't know if I follow you, but this is an example showing the "jumping down" from a=1, b=c for 5*29
>>rowForAB(1, 145)(1, 61, 12, 11, 1, 145)>>> rowNegX(61, 11, 1)(1, 41, 10, 9, 1, 101)>>> rowNegX(41, 9, 1)(1, 25, 8, 7, 1, 65)>>> rowNegX(25, 7, 1)(1, 13, 6, 5, 1, 37)>>> rowNegX(13, 5, 1)(1, 5, 4, 3, 1, 17)>>> rowNegX(5, 1, 1)(0, 2, 3, 2, 1, 9)>>> rowNegX(2, 2, 1)(0, 0, 1, 0, 1, 1)>>> ((61 - (e / 2) - 1)/2 + 1)-49.0>>> abs((61 - (e / 2) - 1)/2 + 1)49.0>>> s(abs((61 - (e / 2) - 1)/2 + 1))7.0
But keep in mind, that equation was something I made when I thought jumping down would only go to (1, 1, 1) and not between e's.
So it could be wrong.
I wouldn't trust this calculation anymore since I don't know if it's trustworthy. It was based on an assumption I now suspect is wrong.
I looked at the pattern of the changing n's from jump to jump.
I saw it was a change of sums of 4, and the "golden" pattern in all of this is the sum of (1…n) * 4…
To generate the d at t for any (e, 1) record you either do:
Even e:
(e / 2) + 4 * ( (t * (t + 1) ) / 2)
Odd e:
(2 + int(e/2)) + 6t + 4( ( t * (t - 1) ) /2 )
So I saw the change and made some quick calculations.
It's a very recurring pattern in generating of a's d's etc.
Well to get D from T for (e, 1) I have this:
def getDFromT(e, t): if e 0 or e % 2 0: return (e / 2) + 4 * ( (t * (t - 1) ) / 2) else: return int( (e + 1) / 2) + 2t*2 - 1
And to get A from T I have this:
def getAFromT(e, t): if e % 2 == 0: return (e / 2) + 2(t - 1)*2 else: return int(e / 2) + 4 * ( (t * (t - 1) ) /2 ) + 1
The reverse way:
To get T from D in (e, 1):
def getTFromD(e, d): if e % 2 == 0: t = d - (e / 2) t = t / 2 t = t * 4 + 1 t = t / 4 t = math.sqrt(t) + 1 return -1/2 + t else: t = d - (2 + int(e / 2)) t = t / 2 t = t + 1 t = math.sqrt(t) t = t return t
To get T from A in (e, 1):
def getTFromA(e, a): if e % 2 == 0: return math.sqrt((a - (e / 2))/2) else: return math.sqrt((a - (e / 2))/2) + 0.5
I knew my original equations were a bit off, when I started. My original getDFromT would be off-by-one t. So I took some time now to refurbish them.
They should work correctly, assuming the first cell in (e, 1) is considered t=1.
{1:61:12:11:1:145}
{1:61:212:111:101:445}
{1:61:278:133:145:533}
(1, 61, 678, 233, 445, 1033)
(1, 61, 788, 255, 533, 1165)
I don't know how to predict / calculate these d's. Though. However, they do have an interesting pattern.
212 % 61 = 29
278 % 61 = 34
(212 - 29)/61 = 3
(278 - 34)/61 = 4
678 % 61 = 7
788 % 61 = 56
(678 - 7) / 61 = 11
(788 - 56) / 61 = 12
Again notice the interleaving patterns. This is because 61 appears as an a in (1, 1), but also as a 61 * 101 in (e, 1) (which is at t = 56)
I honestly don't know right now. We do know that negative x is now more interesting.
It allows us to move between these n-records and generate their "initial" cell (where a = 1)
Right now I feel like I am a bit all over the map. We have a lot of neat patterns, but I don't see a "deeper" connection between them.
What use is f?
Why did VQC's original C# code refer to x + n?
Why is negative x important?
VQC also talked about moving from the first (or second cell) to any value c. Then about controlling c by multiplying it with primes in order to coerce the factors.
I'm still not sure if this is all a LARP, or if we are close or if we are still far away.