Officially faster bruteforcing:

https://pastebin.com/uBFwkwTj

Provided toy values for others to try. Haven't tested if it works with cryptographic secure prime pairs (gcf(p, q) == 1)

It's a 50% reduction in time to bruteforce a semiprime. But I also have some inroads to a/30.

It's not "broke prime factorization for good!" levels of fast, but its still pretty nifty.

Could use decimal support with higher precision so I don't cause massive overflows on larger numbers, but this is just a demonstration after all.

edit, I meant q/30, not a/30, but the improvements remain the same.

Bruteforcing semiprime factorization is x2 faster.

How it works is actually pretty simple.

We're searching for a value of i related to q, in the simplest and slowest case, i is floor(q/2).

When we use this value of i as a power of 9, we get the value m = qr.

Whats qr?

q is one the original factors of n.

r is all the remaining factors of m.

think of it like a list, where q is the largest factor, and r is the product of all the factors of m smaller than q.

Now theres something interesting. m has 2 or more factors, meaning we still would have to do a lot of factorization when we get m, but factoring m in the naive case should still be quicker than n (typically).

However we can do better than that.

Could you make an official statement about NOT being suicidal? No reason...

In algebra, when you have two products that share at most one common factor, you can do a slight transformation of them.

lets say we have n=q*p, and m=q*r.

You can get z*(q+r) by doing n+m, or z*(q-r) by doing n-m.

And from this you can get at the common factor between n and m.

To eliminate this while generating cryptographic key pairs (p, and q), knowledge of which gives you someones private key, you would have to not only check gcd(p, q) == 1, but also that i=int(q/2) as input *also* only gives gdc(m, n) == 1

@Demolishun Lol, for the record I'm not suicidal and never have been. But frankly I don't think that would matter much if this were more than just a x2 speedup in bruteforcing public keys (the size of which are so large only nation-states would bother, and even then the gain so trivial they'd be better off finding some other exploits).

If I can push the method down to (q||p)/30, or a 30,000% reduction in bruteforcing time, as I suspect is possible, I will probably (definitely) release a letter stating I'm not suicidal.

I'm just hoping the NSA is thoughtful enough when they kidnap me to put me on a beautiful island and pay me for my work, in the form of steak dinners, fat cash, fast cars, and beautiful women.

Instead it'll probably be some heavily russian accented babushka with a unibrow, trained in the fine art of torture, down in ye old east european black site.

Depending upon what happens I just want to be able to tell people; "Wisecrack didn't kill himself."

FYI, wouldn't have happened if @Fast-Nop hadn't taught me about the distributive property over at

https://devrant.com/rants/4532894/...

Thanks FN!

Seems to me the whole thing inside "val" just cancels out to give val = 2*i + 1, so you're basically just trying every odd number?

@hitko in the worst case, yes and no.

I'm actually just searching straight, instead of for odd numbers only.

Calculating m=qr is contingent on i=floor(p/var),

where var=2.

Theres some modifications that I've found that let us calculate m = qr, where i=floor(q/var) for var=30, with a pretty reliable and predictable remainder.

I think it'll probably take another six months to get these variations functioning, based on prior estimates for getting the current algorithm to work (3-6 months).

I wouldn't have even found them if I hadn't been working on alife/generative approaches prior to this. Decided to apply that to finding variations to the current approach posted here because the search space was too big to do by hand, and was surprised to find a few that showed promise (stable and predictable remainders).

Still gotta confirm this works for very large numbers (2048 bits+).

what it demonstrates is the idea is sound. This approach absolute does work, 100% of the time from what I've seen, and is universally twice as fast as naive brute forcing.

By searching for a particular value of i < var, that we can use i as an input to a function that returns a value of m > n, where m and n only share one factor in common.

This is just a starting point, naturally.

If I wanted to search just even numbers (because every odd number divided by two and rounded down, is even), this would still be twice as fast as bruteforcing.

@Wisecrack

val = ((n/((((n+m)/(n-m))**0.5)-1))**0.5) + (((i-(((n/((((n+m)/(n-m))**0.5)-1))**0.5)/2))*2)+1)

If i do a search & replace for "((n/((((n+m)/(n-m))**0.5)-1))**0.5)" -> "mnq", I get

val = mnq + (((i-(mnq/2))*2)+1) = mnq + (i-(mnq/2))*2+1 = mnq + 2*i- (mnq/2)*2+1 = mnq + 2*i -mnq +1 = 2*i + 1

@Demolishun nah, he's not

@hitko unless I've misunderstood something, the problem with this is that you don't know q off the bat, so you can't just take the product mnq.

my solution gives you p and q though.

edit: I see what you did. Under normal circumstances I'd say "it's that simple", and in the general case it is, but its also missing the forest for the trees, because the simplification you're highlighting only applies to the simplest case of i=floor((p)/2)

It's still the case that for some i, there exists a product m that shares p with n, but not b.

Which means there are an infinite number of other products m, derivable through variations on the formula, with i values that have smaller quotients than p/2

The simplification of the case of p/2 is a distraction, don't focus too much on it.