Surrogate factoring and interlocking constraints

Recently I began puzzling over the research that I call surrogate factoring trying to understand all the results that I have scattered across this blog, and was surprised at how difficult it has been as I stopped active research on it over a year ago, and lately have just been kind of cleaning up with finding quadratic residues using this approach.

Having spent another exhausting period trying to figure it all out, I think I kind of have the gist of it as an approach that uses interlocking constraints to limit an infinity. That infinity I've described in various ways which I now see as not completely accurate so here it is, I think, after serious hours of pondering:

z² = y² + T

and

x² = y² mod p

I put that second relation mod p, though most of the results that follow can be considered mod N, as that I think is more accurate, and notice there are actually a limited number of integer solution for z and y, so the infinity is with x.

So what I do next I think is limit that infinity, as two key relations are:

z = x + αk mod p and k = 2αx mod p

where k and α are the crucial control variables from which all else follows, and it actually took me a while to settle on both of them, while k came in early but only after years of research did I realize I needed α as well.

Yet another key relation now follows which is:

x² = y² + T - (1 + α²)k² + kpr

And that shows up in various forms, and is crucial to some important conclusions which I still don't completely understand how I proved them before, and it's usually given not as a congruence relation but explicitly to, I guess, show that k multiplied times p, where r is some unknown integer that is rarely if ever determined.

From THAT result a fascinating conclusion is that a value I call k₀ is the minimum k using only positive k, such that you have a non-trivial factorization of T.

Where k₀ is given by the greatest k such that:

abs(T - (1 + α²)k²)

is a minimum.

But it is actually used as and better presented as:

x² = y² + T - (1 + α²)k² mod p

Oh, and one thing that bugged me as I puzzled over the equations was, how do you know that y is an integer? As usually you see y² all over the place, and in past research I even talked about non-rational values for y itself, and the LATEST on solving for quadratic residues gives the answers as using T, and factoring it to solve for k, you have z and y as integers.

Another crucial result is:

k² = (α²+1)^-1(T) mod p

And now with all of the above you intriguingly enough can solve for factors of T:

f₁ = αk mod p

and

f₂ = α^-1(1 + α²)k mod p

Where I get those using solutions for z and y:

z = (2α)^-1(1 + 2α²)k mod p

and

y = (2α)^-1k mod p

and the solution for z, I also call the z constraint, and seemed fascinated by its explicit value which I also call the z constraint:

z = (1 + 2α²)k/2α

Though I guess I grew less enthralled with it over time, but it is a critical result in explaining limitations on the size of p, as p can only be so big because if it is too large then there is a conflict between the relations for z, y and the f's, because of k with all of them.

Oh yeah, so I already mentioned the last key constraint that gave all of those results, which is: k² = (α²+1)^-1(T) mod p

But I also give it as:

T - (α²+1)k² = 0 mod p

That goes all the way back to:

x² = y² + T - (1 + α²)k² mod p

And represents shrinking down the choices yet again, which is the final limitation which brings the infinity from the start down to a finite number of possibilities, but also means that in some cases no integer solutions exist!

And there is this relation that helps there as well:

T - k² - f₁² = 0 mod p

And I do not remember how I got that result, but it shows how some factorizations can be blocked because T - f₁² is not a quadratic residue mod p.

Oh, and I love the phrase "helper prime" for a prime p that will work.

And for most of those relations the result holds mod N, which I used to come up with a general method for solving quadratic residues.

One last result I talk a lot about is that a k that will factor T non-trivially must be within floor(k₀/2p) steps in increments of 2αp from k₀ which to me now is just like some bolt from the blue as I haven't figured out how I figured that out, and I'm tired from the effort.

In any event, this post may help me the next time I try to understand how surrogate factoring works, so it's worth putting it down now, while enough of it's still fresh that I kind of think I have the gist of how it all works.


James Harris

Solving quadratic residues

Remarkably my surrogate factoring research leads to a simple way to solve quadratic residues.

Given a quadratic residue q modulo N, with N a non-unit odd natural number coprime to 3, and k, where

k² = q mod N

you can solve for k, using T = (1 + α²)q mod N, so T = (1 + α²)q + jN, where j is a non-zero integer, and α is a natural number of your choice.

You next check each factorization of T to find positive f₁ and f₂ such that f₁f₂ = T and then you get k simply enough from

k = α(1 + 2α²)^-1(f₁ + f₂) mod N

where a key relation is T - k² - f₁² = 0 mod N, so T - f₁² must be a quadratic residue modulo N.

That means, for instance, that if the first trivial factorization of T does not work, then none will, as f₁ mod N will remain the same.

There are size ranges on T such that for about 50% success with α=1, T needs to be at least N².

More precisely for a factor f₁ of T, T needs to be greater than f₁(2N - f₁), with α=1, which has to do with the underlying surrogate factoring equations and what I call the z constraint.

To use smaller size T for smaller numbers to factor more than likely α greater than 1 will be needed.

Before going into more about α, I'll show some examples with α=1.

So let's try it. Let N = 35, as that's simple enough, and q=29 (I'll explain how I picked it later). Then, T = 2(29) mod 35, which is T = 23 mod 35.

You can use even T, but here I'll use the first odd, which is T = 93, and it does work with f₁ = 93, and f₂ = 1, as I get:

k = 3^-1(93 + 1) mod 35 = 12(94) mod 35 = 1128 mod 35 = 8 mod 35.

And k = 8 mod 35 is a correct answer.

And now you can see how I picked that example as knowing that 35 has 5 and 7 as factors I picked the first k coprime to 35 that would not give a perfect square:

8² = 29 mod 35

But also it shows that you may get answers with T less than N², but the likelihood is smaller and in fact decreases rapidly as you increase the size of N.

Ok, so I picked k=8 as it was the first case where you get a non-square for the quadratic residue coprime to 35. Why not do the next?

So let's move up one and do, k=9.

So q = 11 mod 35, and T = 22 mod 35, so I can try T = 57.

The trivial factorization didn't work--which means no trivial factorization will--so I'll do the non-trivial one:

f₁ = 19, and f₂ = 3 so,

k = 3^-1(19 + 3) mod 35 = 12(22) mod 35 = 264 mod 35 = 19 mod 35.

19² = 11 mod 35

so it worked!

And you can see that f₁ also is the answer, and in general one of the factors will often be the answer with α=1, and one always will be if N is a prime number.

And that is a factoring example, as I know k=9 is a solution, so I have

19² = 9² mod 35

so (19-9)(19+9) = 0 mod 35, so (10)(28) = 0 mod 35,

and you pull 5 and 7 as factors with a gcd.

So the probability is roughly about 50% success if T is at least N² but you can use smaller T by shifting α, where the probability with α greater than 1, is approximately ((α-1)/α)*(50%).

I haven't checked to see if there is a size limit on α as to how high it can or should go.


James Harris

Connecting prime distribution to a continuous function

Going back into my archives to copy from prior posts I have a result from 2002 where a simple progression of formulas shows how the prime distribution is connected to a continuous function:

1. Prime counting function sieve form:

With natural numbers where p_j is the j_th prime:

P(x,n) = x - 1 - sum for j=1 to n of {P([x/p_j],j-1) - (j-1)}

where if n is greater than the count of primes up to and including sqrt(x) then n is reset to that count.

To see an example of it used click here.

The [] is the floor function and is actually redundant as you're to use natural numbers.

The sqrt() is the integer square root, for instance sqrt(10) = 3, as that's floor(sqrt(10)), and it's automatically positive because natural numbers are only the positive integers greater than 0.

2. Prime counting function difference equation form:

With natural numbers

P(x,y) = x - 1 - sum for j=2 to y of {(P([x/j],j-1) - P(j-1, sqrt(j-1)))(P(j, sqrt(j)) - P(j-1, sqrt(j-1)))}

where if y>sqrt(x), then P(x,y) = P(x,sqrt(x)).

And that is an interesting advance as notice it cannot be done with any other known prime counting function! And also notice there is no longer need to tell the equation of any numbers that are prime! If you program it, you'll notice it plucks out primes on its own as it counts, as only when j is prime does:

P(j, sqrt(j)) - P(j-1, sqrt(j-1)) = 0

And it was a difference equation form (slightly different from the above) which I found first! And later I introduced the sieve form.

3. Continuous function:

In the complex plane

P'_y(x,y) = -(P(x/y,y) - P(y, sqrt(y))) P'(y, sqrt(y))

and a continuous function is found easily enough from the difference equation from above. To see the full derivation click here.

The partial differential equation form is rather succinct like the sieve form, and I just gave the PDE versus talking about summation as here there is no actual prime count involved. Integrating the PDE is of interest.

And that is the story of why the prime distribution is connected to a continuous function: a sieve form as P(x,n) equation can go to a difference equation form, which leads to a partial differential equation.

The reason mathematicians didn't figure this out before probably has to do with the historical use of a single dimensional pi(x) function versus the multi-dimensional one which tells the full story.

So a minor quirk in how some people did one thing may have managed to block for a time the direct explanation for the 'why' of the prime distribution's connection to continuous functions.

Remarkably though I found the difference equation form back in 2002, so there is the issue that this research is not new! And I sent the research to mathematicians and have talked it up on something called Usenet.

Of all my amateur research my findings on the prime distribution may be the most easily checked to be correct (hey the count of primes is the count of primes), and the most easily connected to a BIG area in number theory, but maybe it upsets so many apple-carts and so upsets the status quo that I have a social inertia theory where to preserve the current system without having to acknowledge some upstart not a Ph.D who has a major find, mathematicians pretend, it does not exist.

But that's just a theory, but the mystery is ongoing for 7 years now. 7 years.


James Harris