I made a pdf specifically so you didn't have to do something like this wall of links. I posted it in the other thread.
All I did was go through each of the threads, copy and paste the relevant posts and separate them with a line of dashes. I didn't do any formatting (which is why some posts look different to others).
You know what, I'll set up my own public and private keys, I'll see if I can encrypt a message, I'll post it here along with the public key used to encrypt it, and then you can take c from the public key and unencrypt my message. Give me like 5 minutes, I can't quite remember how to do that.
Hang on, didn't that just factor it as 1 and itself?
I mean what time zone will it be midnight then? EST?
In case for some reason CA isn't completely right, I think I just found a way to calculate i from c using binary search (meaning you can then calculate n). I need to try a few more test cases of c but it works for 35. I might be wrong of course.
People study it but they don't accomplish it. If someone breaks RSA (which is obviously going to happen), they're going to mess a lot of people's shit up for a while. You obviously would have found this board because of /cbts/. Don't you think there are powerful people who would want to either protect their shit or get revenge on whoever managed to get into their shit?
Hey, if one of us cracks RSA should we post it? You said you were holding because of something Trump said. Two of us think we've either got it or we're really close (I'm the really close one, I just have some bugs in my binary search algorithm).
>is there anyone more practical with access to 3D printing
My friend's dad has a 3D printer. If that's happening it'll need to be before the end of February and even then I don't know what a cold fusion generator is so I don't know if I'll be able to convince him.
Why so angry? For a start, nobody has listened to anything I've suggested might lead to the answer this entire time, so if anything I should be angry at you (I'm not). Secondly, I'm asking the person who allegedly knows top-level information and who also said they weren't revealing the answers yet because reasons. I'm not the only one asking that, either. Don't you think that would be a rational thing to do? Thirdly, like I said, I haven't figured some bugs out yet.
I'm going to release it. I never said I was going to keep it to myself. I just wonder if Chris wants us to wait, since he's waiting himself. Is that so wrong? Shit.
I'm pretty sure I just sorted my bug out. I've tested it on 20 or so cases of c = prime a * prime b, but I need to test it some more and make it easier to understand (and maybe tinfoil myself up before I post it). Long story short, I was onto something when I found this image. I'm 99% sure I've just written some Java that finds i for a given c.
Actually I guess I probably shouldn't be using recursion.
Clearly my code is shockingly bad because it couldn't do that. I'm currently rewriting it to be a while loop instead of a recursive binary search function, and when I've done that I'll put 75644981 into it. Until then, it definitely works for 3-digit numbers.
What is your c value?501For c = 501, a = 3 and b = 167What is your c value?485For c = 485, a = 5 and b = 97What is your c value?415For c = 415, a = 5 and b = 83
It's currently running, and it has been for 4 minutes. It will definitely finish eventually. My math isn't perfect yet. I'll type up a better explanation than this, but the gist of it is that I'm using two mathematical relationships to make binary search run (one for when it's too low, one for when it's "too high") and I only really understand one of them (when it's too low) so I have some patchy code that does what it's meant to but isn't optimised by any means. Regardless, it uses math to find a and b from c. That's what we've been trying to do this whole time, so now all we have to do is optimize it. When I've typed up an explanation and I post my code here, hopefully you'll all actually start paying attention to what I'm saying, because some of you are bound to have better ideas than I currently do in my tired and stressed-out state.
I'm about to post my code and explanation. Before I do I want to emphasize part of it: when factorizing 223916479610897, it figures out the first 8 digits of the 14-digit-long i value almost instantly, but it doesn't quite narrow it down. Some of you might think it's wrong because it doesn't use the grid like you've all been trying to, but trust me, it'll work as soon as the upper bounds are figured out.
We're given c, and we're meant to find prime factors a and b. i and j are used to generate a, b, c and some other variables we can use. If we can use c to calculate i, we can calculate a and b by doing the following:
>d = floor(sqrt(c))
>n = i - d
>o = (d+n)(d+n)
<I'll explain why there's this extra variable eventually
>x = floor(sqrt(o - c)) - n
>j = x + n
>a = i - j
>b = i + j
All we need for each of these operations is to find i from c. There isn't an obvious mathematical relationship, so one way to find ideas it to make visual plots.
When we change the co-ordinates of the {e, n, d, x, a, b} grid from (e, n) to (c, i) and turn it into a picture, we get pic related. As you can see in this picture, there are several linear lines created by spaced out pixels. Each of these dots indicates a product of primes c and its corresponding i value. Each c only has one possible i value.
Now, you'll probably notice that there aren't infinite lines in all directions. What you'll see if you change the code around again to make a grid with c and i as the axes is that each of these lines has a constant a value. For example, the lowest line you'll see has a constant a value of 3. This is the lowest prime we can use for prime products, since 2 would create even numbers. The next line up has a constant a value of 5, then the one above that 7, then 11, then 13, then 17, etc. What you'll also probably be wondering is how the gradients of each of these lines works, and where each line begins. Again, using a grid version and highlighting cells, you can find the following:
Gradient Prime
1/6 3
1/10 5
1/14 7
1/22 11
1/26 13
1/34 17
1/38 19
1/46 23
The gradient of a given prime number's line is 1/(prime * 2). Each of these lines begins where a and b are the same (in other words, at the square of said prime - e.g. 5's line starts where a and b are 5, 17's line starts where a and b are 17, etc).
Now how do we use these lines to calculate i from c? Well, VQC said we were meant to be able to factorize prime products in O(log n) time. An example of an O(log n) time program is binary search. Binary search uses a known value and looks for it in a big list of other known values. If the current value is less than the value we're looking for, it looks only above the current value, and if the current value is higher than the value we're looking for it looks only below the current value. That means that it halves the number of steps necessary each time.
Thinking of this in the context of c and i, we know what c is and we want to find the particular i value in a big list of possible i values. As I mentioned earlier, there is one line below which no other line can be generated. This is the 3 line. That means any i value along this line is the largest possible i value for any given c. If we know what c is, we can use the gradient of this 3 line to find the maximum possible i value for it, and then we'll know the upper and lower bounds (the lower bounds I've been using are 0). Now we have most of what we need for binary search.
What we also need is a mathematical relationship that allows us to decide when i is too low and when i is too high. Knowing when i is too low is reasonably easy. In order to check if the current i corresponds to the c we want to calculate a and b for, we need to use some math. We can plug i and c into the following formulae:
>d = floor(root(c))
>n = i - d
>x = (floor_sqrt(( (d+n)*(d+n) - c))) - n
>j = x + n
>a = i - j
>b = i + j
>c = a * b
If c does indeed = a * b, we'll know our i is correct. For our lower bound, we can use the following
>x = (floor_sqrt(( (d+n)*(d+n) - c))) - n
What we're looking for is a square root. If we take the square root of a negative number, we're going to get an imaginary number, and we can't really use that. That's why I had that extra variable
>o = (d+n)(d+n)
If o is less than c, we're going to get an imaginary number. d is going to be the same regardless of the i we're guessing (since d depends on c), but n depends on i. n = i - d. Whether or not o is less than c depends on how high i is. If i is too low, o will be less than c. That means we have a reason to increase the lower bounds.
The higher bounds are a little trickier for me personally to figure out. In the case I was testing as I figured this out, which was 35, it just so happened that i was the first possible value above all of the possible i values that were too low. I didn't completely go through many other examples, so I don't know if this is always the case. That said, I wrote some code that I knew would work for 35 just to test. It worked for most cases. I still had the grid I generated for finding gradients open, so all I had to do was click a cell with values in it, input that cells c value and double check that it output the correct i value. It did this for most cases, but occasionally I'd get a stack overflow error (at the time I was using recursion instead of an infinite loop) because it would loop. I used some patchy guess code (the if(mid_index == upper_bound) part) and it magically worked. What I'm saying is, the code does factorize prime numbers in O(log n) time, but I don't know how the upper bounds work. What needs to be done to this in order for it to work is for someone to understand how the upper bounds work and implement it into the code. It can obviously be done, because this code works flawlessly on every prime product from 501 down. It has trouble on bigger numbers, but it finds the general range of i almost instantly (for example, when factorizing 223916479610897, it figures out the first 8 digits of the 14-digit-long i value almost instantly, but it doesn't quite narrow it down. I think as soon as one of you looks this over you'll see the issue and we'll crack it.
>the lowest line you'll see has a constant a value of 3. This is the lowest prime we can use for prime products, since 2 would create even numbers.
That's probably wrong. I've been having way too little sleep working on this and all my other shit.
import java.util.;public class Gradient{ private static long c; private static long i_poss; private static long upper_bound_real = 0; private static long bound_change = 0; private static long i; private static long d; private static long n; private static long o; private static long x; private static long j; private static long test = 0; private static boolean changed = false; public static void main(String[] args){ Scanner input = new Scanner(System.in); System.out.println("What is your c value?"); c = input.nextLong(); i_poss_create(); long mid_index = (long) (Math.ceil(((upper_bound_real)/2))); upper_bound_real = (long) (Math.ceil((double)((c-8)/6))) + 5;; long correct_i = binary_search(mid_index, upper_bound_real, 0); long a = i - j; long b = i + j; System.out.println("For c = " + c + ", i = " + i); System.out.println("For c = " + c + ", a = " + a + " and b = " + b); } public static void i_poss_create(){ long iMax = (long) (Math.ceil((double)((c-8)/6))) + 5; i_poss = iMax; } public static long binary_search(long mid_index, long upper_bound, long lower_bound){ while(test != c){ if(upper_bound < lower_bound){ lower_bound = upper_bound-4; upper_bound+=3; /long temp = upper_bound; upper_bound = lower_bound; lower_bound = temp;*/ } System.out.println("Upper = " + upper_bound + ", middle = " + mid_index + ", lower = " + lower_bound); changed = false; i = mid_index; d = (long) Math.floor(Math.sqrt((double) c)); n = i - d; o = (d + n) * (d + n); if(o < c){ //then it needs to check everywhere above this point lower_bound = mid_index+1; mid_index = lower_bound + ((upper_bound - lower_bound)/2); changed = true; } x = (long) (Math.floor(Math.sqrt((double)(o-c)))) - n; j = x + n; test = (i-j) * (i+j); if(test != c){ //then it needs to check everywhere below this point if(!(changed)){ upper_bound = mid_index; mid_index = upper_bound - ((upper_bound - lower_bound)/2); if(mid_index == upper_bound){ bound_change++; mid_index = upper_bound_real - bound_change; upper_bound = upper_bound_real; } } } else { return i; } } return i; }}
Nice to see you aren't so angry now. I definitely hope some of you can work with it. The upper bounds I coded in work perfectly for most cases. I just don't know when they don't completely work. I'm thinking of putting something together that outputs c every time i isn't directly above the highest value that produces an imaginary number just to see if it ever even is the case (I'm pretty sure it is) and if so what the pattern is. When that isn't the case, it works fine. I just tested with a few 6 digit prime factors (762709 and 809009) and they were factored instantly (as soon as I took my finger off the enter button), so there's definitely just going to be one tiny thing wrong with it. I should probably sleep eventually though. It's almost 2018 where I live.
Oh man, thank you. That'll give me time to work on the ideas I have regarding the upper bounds issues.
I think you rewrote it wrong, at least for the first example.
>15
Works perfectly for me.
What is your c value?15Upper = 6, middle = 0, lower = 0Upper = 6, middle = 3, lower = 1Upper = 6, middle = 5, lower = 4Upper = 6, middle = 5, lower = 4Upper = 6, middle = 4, lower = 4For c = 15, a = 3 and b = 5
I haven't looked at your code yet so I don't know why.
>7474
It doesn't work for prime products where one of the factors is 2, since I'm using the line where a = 3 as the gradient. It's the equivalent of using the gradient from the 5 line. That would stop you from being able to factorize any prime products where one of the factors was 3.
>940666
As above.
>940679
Yeah, like I said, it isn't perfect. I'm not sure why some numbers work and some don't yet, but I know it has something to do with the upper bounds.
If you didn't figure out how the upper bounds work, I sincerely doubt it's going to be that easy. I have it running just in case but it's all over the place in terms of digits.
If some of what I say seems patronizingly simple, don't take it personally. I just like to explain things as simply as I can.
When you're doing binary search on a big list of sequential numbers to see if the one you have is in there, you figure out the lower bounds of each given iteration of the loop when you find that the current value you're looking at is lower than the value you're looking for. For example, if you had every number from 1 to 18, you wanted to know if 7 was in there, and the current value you were looking at was 4, the lower bounds on the next iteration and subsequent iterations would be at least 4. You would never check below 4 again because you'd know it isn't in there. Same thing with upper bounds. If you were currently looking at 11, you know it's higher than 7 so in the next iteration of the loop and subsequent iterations, your upper bound would be at least 11.
In terms of this RSA stuff (or at least my code), we aren't calculating the bounds based on a big list of all possible i values and the current i value being too low or too high. We don't know the correct i. That means we have to check if i is valid for the c we're using and we have to find mathematical properties of the calculations we do in order to find those bounds. The lower bounds are found in this case because when i is too small, the calculation of x creates an imaginary number. When we plug c in and the current i value we're looking at creates an imaginary number in the x calculation, the lower bound becomes at least that i value. What we need to find is a mathematical property of these calculations that can be used as an upper bound. In at least most of the cases I tried by doing the math by hand, it seems (I can't confirm off the top of my head) that the correct i value is 1 greater than the highest i value that creates an imaginary number. That might not actually be it. If we can find that upper bound (and if the lower bound does indeed work on 100% of cases, which I think it does considering it obviously does factorize primes), it'll be complete and we'll be able to factorize RSA numbers.
I guess I forgot to mention that at the beginning of the code the upper bound is meant to be the highest possible i value, since we don't know yet whether it's right. If a = 3, it'll be the highest possible i value and all others will create imaginary numbers (I think… don't quote me on that).
That's the idea, yeah. This whole time I was trying to figure out how this could work in O(log n) time, so I was trying to find a way to apply binary search. Here it is. VQC's real.
Oh, that was you? I remember that. I also remember agreeing with you, but I haven't heard of any other O(log n) algorithms that could be applied to anything like this.
I found an example of my theory being wrong (the one about the correct i being directly above the final lower bound).
a = 3, b = 19, c = 57, i = 11, d = 7
Let's say i = 10
n = 10-7 = 3
(d+n)(d+n) = 10*10 = 100
100 57, so it'll think to check lower down. The fix case I had for this was to set the upper bound and the middle index back up near the maximum i value and start the loop again since I couldn't figure it out. I'll just work out the rest of the calculations for i.
Also I don't think this is the solution VQC intended. I still have no idea how this relates to quantum computing and qubits at all, and a lot of what VQC has been saying seems a bit irrelevant. I guess that means either there are multiple solutions or it's impossible to find the upper bounds. I sure hope it's the former.
I've spent all day on this and I'm way too tired to function anymore so if anyone does anything with my code and they want me to explain something, it'll have to wait at least 6 hours, possibly 12 (what am I doing to myself?).
For whenever this anon >>1976 comes back, I've got my own code (without BigIntegers) factorizing 940679 correctly now, but after implementing my changes yours doesn't seem to work. It thinks the prime factors of 15 are -1 and -15, for example, and 940679 continues to work as a loop.
>I should really read the IDs
I could always use my trip or the BO capcode if you want. People (or VA anyway) were calling me Archive Anon a while ago. I can't stand using a name so I just tend not to unless someone like you doesn't know who they're talking to. I may as well at least do it once for this thread's ID.
>Did you implement these changes when you tried it on my BigInteger rewrite?
I compared that pastebin to the file I'm using with my latest changes and there doesn't seem to be anything different other than my changes. I'll post both my current non-BigInteger code and my edits of your code in a bit.
This took about 2.5 seconds.
c=101643226297mid_index = 8470268859For c = 101643226297, i = 352309For c = 101643226297, a = 202381 and b = 502237
This one took 4 seconds. c=15778598254603mid_index = 1314883187885For c = 15778598254603, i = 4010522For c = 15778598254603, a = 3457631 and b = 4563413
I can't tell if it's taking so long on these bigger ones because it scales badly or if there's a bug.
I'll explain why I did that. Some of this may be completely inaccurate (I might name a variable the wrong thing, since this is based on memory, but hopefully not). I haven't had nearly enough sleep lately. I spent most of last night trying to figure out how the upper bounds work. What I found is that, for most prime products, the correct i value is directly above the last value at which i^2 creates an imaginary number. The thing that stops it from working is the ones that don't, obviously. In the latest code I put on pastebin, there was a variable called "multiplier" and inputs for known a and b values. I was testing it on values I knew got stuck in loops (particularly 940679). What I found was that for some reason, after j gets to a certain point, i^2-c begins to loop instead of steadily increasing (the i I'm referring to is the current guess case, and the j is the j calculated based on the real c and the current guess case of i). It would go up about 10,000 from wherever the loop starts, then it would go back to the start of that 10,000, around and around forever. I figured out that it was happening because i and j were scaling together linearly (every time i increased by 1, j increased by 1) and then at the point of the beginning of each loop i was increasing by 1 but j was increasing by 2. I still have no fucking clue why that happens, and I actually have no idea how I solved it, either.
I guess I didn't really explain multiplier. When I figured out the math for 940679 by hand, I figured out that if you multiplied the highest possible i by something like 0.04207something, you got the right i value. I was planning to do this for a bunch of c values that got caught in loops and maybe plotting it to see the mathematical relationship or something. That way, if i isn't directly above the highest i value that makes an imaginary number, you can just apply some other equation to it and get the right answer.
Because it worked. When it went to run the block of code in the if statement, it seemed that when the c value was too low, the bound swap would cause it to start looking in negative numbers, but if it was high enough it wouldn't cause any problems. e.g. it factored 15 as -1 and -15 (unrelated to the BigInteger sqrt problem) and it factored 940679 perfectly. Once we understand the upper bounds, we can get rid of all these dumb solutions.
In the first if statement in the while(test != c) loop, I added lower_bound = upper_bound+3 and upper_bound = upper_bound-4 arbitrarily. I added some stuff to the code to test which of my meaningless fixes it gets caught in (whether the bounds are being switched around endlessly in this if statement or if it's the last if statement where bound_change is used) and for this example it's getting caught in the first one.
Actually the code we're messing with doesn't really take much of VQC's latest crumbs into account. We're using the gradient of a line generated when a = 3 to find the largest and smallest possible values of i for a given c and applying binary search to it. We know how to move the lower bounds (if i is too small, it creates an imaginary number in the calculation for x) and we're now trying to figure out how to change the upper bounds.
Before that, here's something I've been working on.
c = 1133284519, a = 31481 and b = 35999
Multiply 188880756 (max i) by 1.7863122064166242E-4 to get the correct i of 33740
(This gets caught in the first if statement)
c = 940679, a = 71 and b = 13249
Multiply 156783 (max i) by 0.04247909531007826 to get the correct i of 6660
(This gets caught in the second if statement)
If we get a bunch of c values that don't work properly (and assuming we already know a and b), we can make a graph and see if it looks either like noise or like a mathematical function. Then, if we're lucky enough to find it's a mathematical function (which could be dependent on the respective if statement it gets caught in possibly), we can have another if statement when the correct i value isn't found instantly that applies the mathematical function to the maximum i value and see if it finds the correct i. If it all happens to be noise then I'm not really sure what to do.
import java.util.*;public class Right{ public static void main(String[] args){ //take a bunch of cs with the a and b values int c = 1; int a = 0; int b = 0; Scanner scanner = new Scanner(System.in); while(c != 0){ System.out.println("What is c?"); c = scanner.nextInt(); System.out.println("What is a?"); a = scanner.nextInt(); System.out.println("What is b?"); b = scanner.nextInt(); //send them to be messed with print(c, a, b); } } public static void print(int c, int a, int b){ //calculate i from a and b int j = (b - a) / 2; int i = a + j; //calculate the highest possible i based on the gradient int i_poss = ((int)Math.ceil((double)((c-8)/6))) + 5; // you'll be inputting numbers you know aren't directly above the // low thing, so you probably won't have to calculate much else //print double multiplier = (double) i / (double) i_poss; System.out.println("Multiply " + i_poss + " (max i) by " + multiplier + " to get the correct i of " + i); System.out.println("(" + i_poss + ", " + multiplier + ")"); } }
What we need is a bunch of semiprimes that don't work with known a and b variables. That way we can graph the multiplier. It has to be semiprimes that don't work or it might turn out that semiprimes that do work follow a different pattern and it'll add noise to the graph.
I don't know why I'm finding it so hard to find a way to graph these points somewhere. LibreOffice Calc won't do it properly and every website I've tried hasn't worked properly. Anyone have any suggestions?
These are the points I've got so far, if anyone's curious. We need the gradient. It looks like it might be linear but it's probably not a good idea to guess.
(1653304, 0.00196213158620556)
(1704619, 0.00192946341675178)
(1714251, 0.00192212225630902)
(1787371, 0.00187593957829684)
(1903996, 0.0018009491616579)
(2486975, 0.00171975994933604)
If it is linear like it seems to be, rise / run. If it isn't, we'll be able to tell by looking at it if it's exponential or whatever. If it's all over the place then we'll know that it's super complicated and that this has all been for nothing (I don't think that's the case, it doesn't look noisy at all).
It doesn't seem to be linear, but it also doesn't seem to follow any other distinct equation.
Gradient 1 = -6.3662E-10
Gradient 2 = -7.62164E-10
Gradient 3 = -6.31601E-10
Gradient 4 = -6.43005E-10
The gradient of point 1 to point 4 is -6.42950012555885E-10
What I've been thinking is that when it comes to these semiprimes that don't work straight away, maybe the function of the multiplier used to turn the maximum possible i into the real i is made up of a bunch of lines just like the (c, i) plot I found the original gradient from, and we'd need to do binary search on the range of possible multiplier values to find the correct multiplier. Then there might be another set of gradients created when we find all the times that the multiplier isn't found with binary search. I don't know for sure, but this might be some kind of fractal.
For a start, we'd all have to completely understand each other's work. You're the only one who's been working on what I've been posting about (I doubt anyone else completely gets what we're talking about), and I haven't really helped with the cell jumping stuff (mostly because I don't entirely understand it or see where it's going). Maybe you're right though.
I'm at the point where I don't even understand my own code, so I think I should give it a rest for a day. I'll still be here to do any BO stuff I might have to do. Good luck all.
You're not the only one who's done something like that, if it makes you feel any better.
Yup
For the at least one anon who has been following along with the gradient thing I've been doing, I thought it might be a good idea to make binary search look for the lowest possible i value that doesn't create an imaginary number in the x = (floor_sqrt((i^2 - c))) - n equation. I know I said I was taking the day off but I had an idea to at least clean up the binary search code (significantly) and to fix the gradient that finds the highest possible i.
What I didn't realize is that the lowest i where i^2 c is just the smallest square larger than c. Maybe that can somehow be useful. The following code is just used for finding that i value. It isn't used to factorize, but it does say whether or not the i it finds is the correct one for the given c. https://pastebin.com/ixDFePBX
I forgot to add that I think what that means is that the real minimum i value is floor(sqrt(c))+1. That either means that binary search doesn't work or that I just don't understand what I'm doing (I think it's the latter, since the binary search algorithm that does the factorization is right most of the time depending on how big the numbers are and it does it instantly).
This program takes the c we want to factor and outputs the range of possible i values.import java.math.BigInteger;import java.util.Scanner; public class i_range{ //constants private static BigInteger zero = BigInteger.ZERO; private static BigInteger one = BigInteger.ONE; private static BigInteger two = BigInteger.valueOf(2); private static BigInteger three = BigInteger.valueOf(3); private static BigInteger four = BigInteger.valueOf(4); private static BigInteger five = BigInteger.valueOf(5); private static BigInteger six = BigInteger.valueOf(6); private static BigInteger eight = BigInteger.valueOf(8); private static BigInteger c; private static BigInteger upper_bound_real; private static BigInteger lower_bound_real; public static void main(String[] args) { Scanner input = new Scanner(System.in); String str; System.out.print("c="); str = input.nextLine(); c = new BigInteger(str); upper_bound_real = c.subtract(eight).divide(six).add(three); lower_bound_real = (sqrt(c)).add(one); System.out.println("For c = " + c + ", the true i is somewhere between (inclusive) " + lower_bound_real + " and " + upper_bound_real); } public static BigInteger sqrt(BigInteger i) { BigInteger zero = BigInteger.ZERO; BigInteger one = BigInteger.ONE; BigInteger n = zero; BigInteger p = zero; if (i.equals(zero)) { return zero; } else if (i.equals(one)) { return one; } BigInteger high = i.shiftRight(1); BigInteger low = zero; //high low + 1 while (greaterThan(high, low.add(one))) { //n = (high + low) >> 1; n = (high.add(low)).shiftRight(1); p = n.multiply(n); int result = i.compareTo(p); if (result -1) { high = n; } else if (result 1) { low = n; } else { break; } } if (i.equals(p)) { return n; } else { return low; } } public static boolean greaterThan(BigInteger i, BigInteger i2) { int result = i.compareTo(i2); return result > 0; } public static boolean lessThan(BigInteger i, BigInteger i2) { int result = i.compareTo(i2); return result < 0; } }
For example:c=403For c = 403, the true i is somewhere between (inclusive) 21 and 68c=940679For c = 940679, the true i is somewhere between (inclusive) 970 and 156781c=123824For c = 123824, the true i is somewhere between (inclusive) 352 and 20639c=35For c = 35, the true i is somewhere between (inclusive) 6 and 7
What we were doing with binary search is now kinda useless. This does, however, obviously narrow it down. As has been the case the whole time in terms of this code, if we understand the upper bounds, we can factor c.
There's nothing wrong with that. Once we get there (I'm convinced we will at this point), some crazy, crazy shit is going to happen.
I didn't want to be mean, but this seems to me like that stereotype of Tool fans taking them way, way too seriously. Using the Fibonacci sequence to decide on the length of several lines of lyrics doesn't mean he's telling you the secrets of the universe. It means he's using the Fibonacci sequence to decide on the length of several lines of lyrics. Plus, there are many bands who use occult ideas in their lyrics like as above, so below or use Enochian to name songs or albums. Unless there's a direct reference to the math in this grid, I think you're taking them far too seriously.
It isn't a method for finding i from c. What I figured out is that the lower bounds we were using in that binary search algorithm (if i^2 < c) translated to simple math: instead of using binary search, we can find the end of the lower bounds by simply taking the square root of c and adding 1 to it, because the first instance of i^2 being c is when i = floor(sqrt(c))+1.
>where do we go from now? Binary search useless?
I definitely don't think binary search is useless, considering we used it to very easily factor a bunch of different semi-primes. Some time around 3am this morning I somehow managed to make the original binary search I was working with factor 940679 even quicker than before, but it didn't work properly for most of the other numbers. The version in that pastebin I posted an hour or two ago is far cleaner and easier to understand, but it just looks for floor(sqrt(c))+1 at the moment, so we could adapt it so that the lower bound is floor(sqrt(c))+1 now that we know, and then once we know how to change the bounds again we can factor c.
From my perspective, all we still need to do is understand how these bounds work. If we find a linear relationship among the variables based on how high i is, we'll know when the current guess i is too large or too small.
Woah, weird. Instinct tells me that's a fluke based on the real i being somewhere along the logarithmic (that's what it is, right?) plot generated when you keep halving the range of possible i's. How exactly did you merge them, and how long did it take to calculate that?
That makes me think it's a fluke. Just to explain the +5 being changed to +3, the gradient starts at (3, 9), but it was giving me problems originally so instead of making it +3 I just added a couple extra (all it did was add 2 to i_poss, so it was arbitrary, but for all I know it was involved in factoring that previously unfactorable number maybe). Have you tried any of the other ones that weren't working?
Did changing it from +5 to +3 change anything about it? Did it take any extra steps? I guess in the grand scheme of things integer rounding will diminish the difference with big numbers when you're halving them, but if i just happened to be maybe 2 away from the starting point, changing it would change things (although not only do I not think that would ever happen but it also wouldn't be based on an actual understanding of how this works).
>how to programmatically check if a certain starting value doesn't work
If you mean you want to check if d+1 = i, you could just plug that into the equations for generating a and b within main before you call binary_search and see if test == c there.
Quads confirm we're making headway. Do you have any idea why it isn't factoring the 45-digit one? Also do you have any idea how long it takes the sieve method to factor a 44-digit semi-prime? Because even if we haven't gotten there yet this seems pretty crazy.
>>2230For c = 523022617466601111760007224100074291200000001, the true i is somewhere between (inclusive) 22869687743093501007952 and 87170436244433518626667870683345715200000001
It didn't really narrow much down.
Here's something interesting, based on those two changes (d+1 for 0 and +3 instead of +5) and a factorization of that bigger number:Upper = 150671169417991225046059544758357156789444171603745255851676744300137107192940602659695771463416894743331134777436564854445241931765583656307311832859469292745085419037055008587098920882459584299695035925409370319142460098639819301505752289155099234767934684476314251383056405936484795788156351765009446474080, middle = 150671169417991225046059544758357156789444171603745255851676744300137107192940602659695771463416894743331134777436564854445241931765583656307311832859469292745085419037055008587098920882459584299695035925409370319142460098639819301505752289155099234767934684476314251383056405936484795788156351765009446474080, lower = 150671169417991225046059544758357156789444171603745255851676744300137107192940602659695771463416894743331134777436564854445241931765583656307311832859469292745085419037055008587098920882459584299695035925409370319142460098639819301505752289155099234767934684476314251383056405936484795788156351765009446474080
It loops. It converges to this number, then it starts again (meaning that isn't the correct i). It took 28 seconds to reach that possible i value, so if we actually knew what we were doing, we could factorize this huge number in 28 seconds.
Derived from the equations, I would think. What I'm saying is, we have a big ordered smallest-to-largest list of potential i values for our given c, and we need to find some way of applying binary search to it in a more logical way than we currently are. We need to be able to say "i = 38 through to i = 22 are too big, i = 20 through to i = 0 are too small, and i = 21 is just right". It can't be based on imaginary numbers in the x calculation, because that's how we found d+1 as the lowest possible guess i.
>I choose to believe
So in other words you don't even know what it is we're doing? You can't just say "it doesn't work because I don't believe it works", especially considering this whole thing revolves around math. If you're saying you don't believe because Chris hasn't said anything about it, for one, I don't see why there couldn't be multiple solutions considering this isn't territory many people have studied and considering we might be interpreting the method Chris used in a different way, and secondly because Chris said himself that we can crack RSA in O(log n) time, and binary search is an O(log n) algorithm. The way you're working on probably works great, if you can figure it out.
The gradient of the lowest line in (c, j) is 1/6, just like the (c, i) grid. That means we could use either i or j almost interchangeably in the way we've been using i, but I'm not sure if that means we could use it for binary search.
I'm not entirely sure, but I put together a program that shows the way guess i and j scale up together based on a given c. You give it a c and a maximum i up to which you want it to check, and it calculates what j would be if that combination of i and c was correct. This was written before I knew the minimum i was d+1.import java.util.;public class Wrong{ public static void main(String[] args){ print(1000, 497143); } public static void print(int i, int c){ System.out.println(); System.out.println("c = " + c + ", i = " + i); int count = 0; while(count < i+1){ int i_sq = countcount; int fl_sq_c = (int)Math.floor((int)Math.sqrt(c)); int fl_sq_isqMc = (int)Math.floor((int)Math.sqrt(i_sq-c)); int j = (count - fl_sq_c) + (fl_sq_isqMc - (count - fl_sq_c)); System.out.println("i = " + count + "\tj = " + j + "\t (i-j)(i+j) = " + ((count-j)*(count+j)) + "\t real c = " + c); count++; } }}
If you run it with the c I used and change the maximum i value in the method call, you can see how j doesn't scale entirely linearly with i, but it is constantly increasing with it and never goes higher than i obviously since that would create a negative a.
I was printing the wrong c value in mine, too, and I've just found something very strange. This is for 940679, for which the real correct i value is 6600, but in this case i is a guess based on putting i through the equations.i=6600 j=6528 'c'=945216 a=72 b=13128 e=6255
The c is wrong.
I just had a binary-search-related thought. So we've got all of these lines >>1946, each starting based on the square of primes in order, and each with a gradient of 1/(prime*2). These lines all diverge, so they'll always be in smallest-to-largest order. For a given c, we can calculate how many lines there'll be based on the squares. What if, for binary search, we took the middle line and calculated what i would be based on our given c by taking its starting point and applying the gradient to it? Since all of these lines diverge, the i along any of these lines for a given c will always be in order. I really hope I explained that right because it might be part of the solution.
I'm talking about the co-ordinates of the start of each of those lines in the (c, i) plot. The first one starts where a and b = 3, and has a gradient of 1/6. The second one starts where a and b = 5, and has a gradient of 1/10. The third starts where a and b = 7, and has a gradient of 1/14. Etc. Now that I think about it I'm not 100% sure we can calculate the start of each line, but I'll check. If we can, aside from having to generate a big list of prime numbers, we should be able to do it. Don't hold your breath.
To figure out the latest line to have started, we take the highest square of primes below c. That means finding the highest prime below d (which I guess I'll call m). The latest line to have started on this (i, c) plot will start at (m, m^2) and have a gradient of 1/(m*2). If we had an array of primes (which might be quite time consuming to generate, but I'm figuring this out as I type), we could take the length of that array as the bounds, and start binary search with the middle as the center line. We'd then use the starting position of the m/2 line and its gradient to calculate where i would be for our given c. m will either be correct, too low or too high. Since these lines are diverging, if m is too low, we definitely go higher, and if m is too high, we definitely go lower. I think this it is.
Each of the lines in that picture of (c, i) is based on a prime number, but if we just pretended there were lines for every number, they would follow the same rules (same starting point and gradient rules) but they would never create an i that worked with any c. Only the primes would. That means we don't necessarily need to know that a particular line is based on prime numbers in order to use it for binary search (and therefore don't have to figure out if a number is prime before doing anything). What that means is, we plug c in, we take d as the range of possible lines, we make the starting point floor(d/2), we figure out what i would equal on that line at this c given the middle line's respective line has a starting point of (middle, middle^2) and a gradient of 1/(middle*2), and if that i is lower that becomes the new lower bound, if it's higher it becomes the new upper bound, and if it's correct it's correct.
You don't. We're performing binary search on a bunch of lines. Each line begins at (num, num^2), and the second axis is c, so the latest line to start for a given c will be the highest square below it. The number itself will be the number of lines there are at that point. The bounds are the first line to the last line.
That's the gradient of the lowest line when you turn the {e, n, d, x, a, b} grid generator from plotting (e, n) to plotting (c, i). It puts each endxab record in based on its c and i values. The lowest prime (other than 2, which we aren't really using) is 3. To get from one record with a = 3 to another, you go 6 c's to the right and 1 i down (or it might be the other way around).
Are you understanding what I'm talking about? I'm figuring out how to implement this code-wise at the moment so if I'm not explaining it well enough you could wait for that I guess.
I may have fucked up. That or I'm just confused again. Seems like a running theme for this board.
What would we use it on?
We did that when we were finding the minimum possible i. The only time i^2 seems to be in a situation that can be used for binary search is when i^2 < c, and that's how we figured out that the minimum possible i is ceiling(sqrt(c)). I don't think we can use i^2 for binary search when it's c. Do you have any idea how this grid could be used in O(log n) time without it being binary search? I'm not saying to give up (I'm about to test a thing) but the reason I started with binary search is because it's the only O(log n) algorithm I'm aware of.
You know how I said that when i and j get to a certain point, they'll scale up together most of the time and then for some reason j increases by 2 instead of by 1 and it causes the guess c to loop around a certain range of values? I wrote some code that tells us what the guess c is at the start of each of these loops.import java.util.;public class Wrong{ public static void main(String[] args){ print(9000, 940679); } public static void print(int i, int c){ System.out.println(); System.out.println("c = " + c + ", i = " + i); int count = 0; int previous_c = 0; while(count < i+1){ int i_sq = countcount; int d = (int)Math.floor((int)Math.sqrt(c)); double fl_sq_isqMc = (int)Math.floor(Math.sqrt((double)i_sq-(double)c)); int j = (count - d) + ((int)fl_sq_isqMc - (count - d)); int c_guess = (count-j)(count+j); int e = ( (count-j)(count+j) - (d*d) ); if(c_guess < previous_c){ System.out.println("i=" + count + "\tj=" + j + "\t'c'=" + c_guess + "\ta=" + (count-j) + "\tb=" + (count+j) + "\te=" + e); } previous_c = c_guess; count++; } }}
And here are some of the results.i=6069 j=5991 'c'=940680 a=78 b=12060 e=1719i=6147 j=6070 'c'=940709 a=77 b=12217 e=1748i=6227 j=6151 'c'=940728 a=76 b=12378 e=1767i=6309 j=6234 'c'=940725 a=75 b=12543 e=1764i=6393 j=6319 'c'=940688 a=74 b=12712 e=1727i=6480 j=6407 'c'=940751 a=73 b=12887 e=1790i=6569 j=6497 'c'=940752 a=72 b=13066 e=1791i=6660 j=6589 'c'=940679 a=71 b=13249 e=1718i=6755 j=6685 'c'=940800 a=70 b=13440 e=1839i=6852 j=6783 'c'=940815 a=69 b=13635 e=1854i=6951 j=6883 'c'=940712 a=68 b=13834 e=1751i=7054 j=6987 'c'=940747 a=67 b=14041 e=1786i=7160 j=7094 'c'=940764 a=66 b=14254 e=1803i=7269 j=7204 'c'=940745 a=65 b=14473 e=1784i=7382 j=7318 'c'=940800 a=64 b=14700 e=1839
So what I found, at least for this specific c, is that when i and j get to the point of looping, c will be the lowest value at the start of all of these loops. Every other guess c at the start of a loop is greater than the actual c value. I haven't tested it on any other real c yet, and I don't know how we'd find it if it was always the case.
The first graph was for 940679, and this one is for 497143. It shows the relationship between a and the i at the start of each of these loops. I haven't checked for 497143, but for 940679, the correct i is 6600 and the correct a is 71, which shows up in the graph at (71, 6600). I don't know if we can calculate that in any way, so I don't know if this is useful.
I did this for 497143 as well.i=707 j=52 'c'=497145 a=655 b=759 e=120i=712 j=99 'c'=497143 a=613 b=811 e=118i=714 j=112 'c'=497252 a=602 b=826 e=227i=716 j=124 'c'=497280 a=592 b=840 e=255i=717 j=130 'c'=497189 a=587 b=847 e=164i=721 j=150 'c'=497341 a=571 b=871 e=316i=722 j=155 'c'=497259 a=567 b=877 e=234i=724 j=164 'c'=497280 a=560 b=888 e=255i=726 j=173 'c'=497147 a=553 b=899 e=122i=729 j=185 'c'=497216 a=544 b=914 e=191i=730 j=189 'c'=497179 a=541 b=919 e=154i=732 j=196 'c'=497408 a=536 b=928 e=383i=733 j=200 'c'=497289 a=533 b=933 e=264i=735 j=207 'c'=497376 a=528 b=942 e=351i=736 j=211 'c'=497175 a=525 b=947 e=150i=739 j=221 'c'=497280 a=518 b=960 e=255i=742 j=231 'c'=497203 a=511 b=973 e=178
The correct i for 497143 is 712. This one also shows that the correct i produces the lowest guess c out of each of them at the start of a loop, which was what 940679 did too. So it would seem that, whenever we can't find i with binary search normally, if we find the range of possible i value (which is d to (c-8)/6) and then find the start of each loop for i values between these bounds, the correct i will produce the lowest guess c. That's still O(n), so the solution is obviously different, but it does most likely shave a couple thousand years off the calculation. There might be a relationship between guess i and guess c that allows us to predict where the lowest guess c will be, but I have no idea yet.
At the moment you'd implement that by going through every possible i value individually (hence the O(n) thing, and hence me saying it isn't the solution), storing the guess c value, comparing the guess c to the previous guess c, and if guess c went down, it's the start of a loop, so you'd save that value too. You'd do that for every loop, and each time guess c < previous guess c, you'd compare the previous c at the beginning of a loop (when guess c < previous guess c), and save it if it's lower. So like this: public static void print(int i, int c){ int count = 0; int previous_c = 0; int previous_previous_c = c2; int correct_i = 0; while(count < i+1){ int i_sq = countcount; int d = (int)Math.floor((int)Math.sqrt(c)); double fl_sq_isqMc = (int)Math.floor(Math.sqrt((double)i_sq-(double)c)); int j = (count - d) + ((int)fl_sq_isqMc - (count - d)); int c_guess = (count-j)(count+j); int e = ( (count-j)(count+j) - (d*d) ); if(c_guess < previous_c){ if(previous_previous_c c_guess){ previous_previous_c = c_guess; correct_i = count; } } previous_c = c_guess; count++; } System.out.println(correct_i); }
It's only when there's a loop, by the way. It doesn't work if i and j aren't large enough (so it doesn't work for 15; it thinks 15's i is 8).
That would be funnier if it didn't mean having bounds around possible i values, which would make the thing O(n logn). That would take even longer than the current method of O(n) that we're trying to beat. It is good to have ideas like that from any lurkers who are watching, because it gives us all a different perspective, so if you or anyone else has any ideas, even if you think they're dumb, post away.
They may have been here all along. The implications of this are pretty big. Even if none of us who are working on it are going to do anything shitty with it when we've figured it out, there's almost definitely at least a few people following this because they want to steal Bitcoins or something. There are also probably, like, feds or whatever. Whoever hasn't already been arrested or fired by Trump. In terms of the new thread, I have no idea. You did a good job of this one. Since you and I are the only ones who have been messing with the binary search idea, I don't know if it would be ll that useful to add to everything.
You should include definitions of all of those things, including what the genesis element is.
You've got the most recent code. I spent today graphing the relationships between different variables looking for a linear relationship. The only useful thing I found was that whenever i and j are high enough that they cause a loop (which you can probably predict with math but I have no idea), the lowest c produced from then on is the correct c. That would take O(n) time to figure out, because pic related is the lowest cs. As much as the range increases, the lowest of all the low ones doesn't seem predictable/linear/whatever, so even if we could figure out how far apart they all are we might have to check all of them if there isn't an easily predictable relationship. This picture only shows a small chunk of the cs in this section, too. I generated all of them for the entire possible range of i but it's gigantic and I think the relationship changes higher up (this chunk contains the real c so that's why I picked it). I did also figure out that (c, b) produces similar lines to (c, i), but they have pretty much the same relationship, so it doesn't give us anything new.
Oh wait, that's the cycles themselves. This is the lowest cs.
It would be even better if he stuck to the release dates he said. Several times now, the dates he stated have come and gone with nothing (e.g. Christmas), and there's no indication of whether that happens because we aren't doing well enough, or if he really is LARPing, or if there's something happening in the background that he can't tell us. I've spent every waking moment of the last week thinking about this, and, I mean, I guess we managed to fluke-factorize a 44-digit semiprime pretty quickly, but I'm out of ideas. I guess it gave me an opportunity to touch up on my coding before the uni year starts, and you all seem like interesting people.
I'm talking about that one you said you got to work.