Re: JSH: Now we're golden!

On Jan 19, 8:21 pm, JSH <jst...@xxxxxxxxx> wrote:
On Jan 19, 8:08 pm, Enrico <ungerne...@xxxxxxx> wrote:



On Jan 19, 8:40 pm, JSH <jst...@xxxxxxxxx> wrote:

On Jan 19, 6:58 pm, JSH <jst...@xxxxxxxxx> wrote:

On Jan 19, 6:07 pm, Enrico <ungerne...@xxxxxxx> wrote:

On Jan 19, 5:04�pm, JSH <jst...@xxxxxxxxx> wrote:

Wow! �The poster Enrico noticed cases where my factoring congruences
weren't working, and I was able to work out yet another fascinating
feature, as well as explain something that might have been missed up
until now which is that you get one 'a' and k pair for each unique
factorization.

So, yes, now it's mathematically proven that I found a solution to the
factoring problem, and I want to definitely thank Enrico and would
like to give him mention in the paper.

I will say now that an early draft of the paper is at the Annals of
Mathematics, but I ended up sending two revisions after I rushed them
my early research and have thankfully sat for a while as I worked out
the issues.

There is no doubt I'd think that a paper solving the factoring problem
deserves publication in the Annals.

Some of you may have tested out the congruences and found they did not
always work, which gave you doubts, but now the answer is that there
is a quirk of prime numbers, as there are two basic types: those for
which the negative of the quadratic residue is a quadratic residue and
those for which it is not.

So, for instance, with p=17, Enrico noticed that the congruence
relations would not work to non-trivially factor 15. �I dove into the
underlying equations and found that they would not work, and figured
out the answer as to why.

It helped that I had the existence equation for 'a' handy.

Rather wild though. �All integer factorizations are controlled by the
factoring congruences, but some primes exclude themselves but only if
they are the primes for which the negative of their quadratic residue
is a quadratic residue.

My celebration should be somewhat muted though as it is now definite
that the factoring problem is SOLVED.

Governments around the world and institutions affected should behave
accordingly.

I am directing EMC2 to give a press release as soon as possible on the
situation through its RSA division.

James Harris

---------------------------------------
"but some primes exclude themselves but only if
they are the primes for which the negative of
their quadratic residue is a quadratic residue."

They MAY exclude themselves but they may not.

The existence equation is

a^2 = 2^{-1}(y^{-1} z - 1) mod p.

So if for a solution 'a' exists, it will work.

p=53
5^2 mod p = 25
-25 mod 53 = 28
9^2 mod p = 28
p should exclude itself, but ...

T=3149 = 47*67
n=1
a=10
k^2=38 mod p
k= 41 or 12 mod p
f1 mod p = 39
-f1 mod p = 14
14 + 53 = 67 ***
f2 mod p = 6
-f2 mod p = 47 ***
(-f1)*(-f2)=T

Enrico

Plug and chug: a^2 = 2^{-1}(y^{-1} z - 1) mod p

p=53, T=47*67, so z=57, x = 43, and y=10 or -10, so a^2 = 27(-10^{-1}
(57) - 1) mod 53 = 27(-16(4) - 1) mod 53 = 47 mod 53.

So a=10 as you noted.

So yes, it can work as long as 'a' exists for a particular
factorization, but then again it might not.

The difference with the type of prime where the negative of a
quadratic residue is not a quadratic residue is that there will exist
an 'a' for every unique factorization, or wait...

There are two solutions for each y and z because you can take positive
and negative so you have

2^{-1}(y^{-1} z - 1) mod p or 2^{-1}(-y^{-1} z - 1) mod p

and it's a crapshoot. So the correct answer is 50% without regard to
the type of prime.

No, the correct answer is 87.5% without regard to the type of prime.

That's because you have positive and negative values for y and z.

Well that's actually not bad, and I had something like that before but
really, really wanted it to always work I guess, so I convinced myself
of others things.

Interestingly, an ak can always be found but it's the k = 2ax mod p
that gets you into trouble, so I thought about tossing in another
variable but don't feel like it is mathematically significant to do
so.

That high success rate though makes me wonder, as if it were lower and
I'd found cases early on that didn't work, what would I have done?
Would I have tossed this idea or puzzled through to the full answer?

Oh yeah, that's 87.5% for each unique factorization by which, for
instance, with 119=7(17) there are two: the trivial one of 119(1) and
the non-trivial one 7(17).

For EACH of those there is an 87.5% probability that the relations
will work, so they may block either, as the math doesn't care about
trivial versus non-trivial factorizations.

James Harris- Hide quoted text -

- Show quoted text -

----------------------------------------
One more. Hope I got it right this time.

"but some primes exclude themselves but only if
they are the primes for which the negative of their
quadratic residue is a quadratic residue."

So, if the negative of their quadratic residue
is NOT a quadratic residue, then those primes
include themselves?

No I was just wrong.

It's probabilistic. There is an 87.5% any prime will work for each
factorization, which your spread*** should verify as the correct
percentage.


Correction: 75%

p=11, T=7*23
There are a's such that k exists
using k^2 = [1/(a^2+1)]*T mod p
but f1 = a*k mod P and
f2 = (1/a)*(1+a^2)*k mod p
do not yield the factors mod p of T

If I change p to 13, I get the factors.

Enrico

Fun! And that's why it's not a major issue. 87.5% of the time
whatever prime you pick will work to pull out the non-trivial
factorization you want. If it doesn't then just use another prime,
and the odds that one of the next two will work is 98.4%.

So again I want to remind that these relations solve the factoring
problem though I know that's hard to accept as it feels so wrong
considering how much training in school you get that factoring is a
hard problem.

One approach is to use a bunch of relatively small primes and get the
residues modulo p for the non-trivial factors for each prime. Even if
you start with 2, and go 2, 3, 5, 7, etc. if you find j! such that T/
j! < 1, then you will need less than j primes. Then you can use the
Chinese remainder theorem to get the smaller prime factor.

All the algebra for deriving the factoring congruences is trivial.

It's way past time for mathematicians to acknowledge this result
appropriately, as they have a duty to inform the world.

It's not a choice. It's a duty.

It is a duty.

I've argued out various areas as I've come to fully understand the
result myself, having to correct various mistakes.

But at the end of the day, it's easy algebra.

Mathematicians with years of experience can hardly fail to understand
an argument that relies mostly on easy algebra.

Willful disregard of the duty to inform is a deliberate action.

You cannot leave the world unprotected and uninformed that the
factoring problem has been solved.

You have a duty to inform.


James Harris
.