Prev: New Differential Equation website
Next: How Can ZFC/PA do much of Math - it Can't Even Prove PA isConsistent (EASY PROOF)
From: JSH on 1 Jul 2010 21:58
On Jun 30, 4:54 pm, JSH <jst...(a)gmail.com> wrote:
> I've noted a way to solve for m, when k^m = q mod N, through integer
> factorization, which is then an approach to solving discrete
> logarithms in a prior post.  In this post I'll explain when the
> equations MUST work, where a simple analysis can be done trivially
> using methods familiar to those who've solved simultaneous equations
> in regular algebra.
>
> Here are relevant equations without the complete detail explaining
> them all of the prior post which should be read for reference:
>
> Everything follows from use of a simple system of equations:
>
> f_1 = a_1*k mod N thru f_m = a_m*k mod N
>
> Two important constraining equations:
>
> a_1*...*a_m = q mod N
>
> and
>
> a_1+...+a_m = m mod N
>
> Resultant equations:
>
> f_1*...*f_m = q^2 mod N
>
> and
>
> f_1+...+f_m = mk mod N
>
> (These are arbitrary constraints that I used.  There may be others
> that are of practical use.)
>
> Now assume that for some unknown number m-c of the f's that the a's
> are simply the modular inverse of k, then for that number the f's
> simply equal 1, which allows me to solve for m with:
>
> (k-1)*m = (f_1+...+f_c - c) mod N
>
> If k-1 is coprime to N, you can simply use the modular inverse to get
> m.  Otherwise you'd to divide off common factors from both sides and
> then use the modular inverse with what remained.
>
> All of which was given in my prior post, but notice I can now go back
> to the constraining equations for the a's with the information that
> some of the a's have been set to the modular inverse of k:
>
> a_1*...*a_c*k^{-(m-c)} = q mod N, so a_1*...*a_c= q*k^{-(m-c)}
>
> and
>
> a_1+...+a_c + (m-c)k^{-1} = m mod N, so a_1+...+a_c = -(m-c)k^{-1} + m
> mod N
>
> which means there are two simultaneous congruence equations with c
> unknowns:
>
> a_1*...*a_c= q*k^{-(m-c)}
>
> and
>
> a_1+...+a_c = -(m-c)k^{-1} + m mod N
>
> Using the first to substitute out a_1 into the second and simplifying
> slightly gives:
>
> q*k^{-(m-c)}  + a_2^2*a_3*...*a_c + a_2*a_3^2*...*a_c...+
> a_2*...*a_c^2 = a_2*...*a_c[-(m-c)k^{-1} + m] mod N
>
> Notice then that with any c-2 variables set arbitrarily, the existence
> of the remaining one is set if a quadratic residue exists.
>
> So for instance if c=4, then you can have a_3 and a_4 completely free
> variables, as long as quadratic residues exist to allow for a_2, which
> would indicate a 50% probability in that case if N is prime.
>
> However, you can also further constrain one more of the a's to remove
> squares, for instance let a_3 = a_2^{-1} mod N, and you have:
>
> q*k^{-(m-c)}  + a_2*a_4*...*a_c + a_3*a_4*...*a_c...+ a_4*...*a_c^2 =
> a_4*...*a_c[-(m-c)k^{-1} + m] mod N
>
> which allows a solution for a_2 to always exist.  Which would leave
> with c=4, a_4 completely free.

That's wrong!!! Found that out working an example in this thread.

The quadratic residue *cannot* be so removed, as an a_3 is still left
in the equation.

So a_3 and a_4 would be completely free with c=4.

>
> Assuming human nature will be to look for smaller values to factor to
> actually use the algorithm, one can assume that
>
> f_1*...*f_m = q^2 mod N
>
> will be with smaller values of q^2 mod N, based on human preference,
> so if a_4 is completely free, and is non-unit, it would likely in many
> cases mean that f_4 will be 2.
>
> If a_3 and a_4 are free then one would expect f_3 and f_4 to be 2.
>
> With c = 4 or greater then the area to consider variability that
> cannot just be arbitrarily set to a convenience value is with a_1 and
> a_2 which could make f_1 and f_2 just about any residue mod N.  Worst
> case they are both near N, so you'd have a size of approximately 4N^2.
>
> So algorithms based on this method should exit within q^2 mod N less
> than 4N^2.

However the *average* case would be about N/2 as the residue, so
solutions should be expected, for c=4, near: (N/2)*(N/2)*2*2 = N^2

Assuming the smallest primes. But with small primes for c=5, it'd
still be approximately N^2, and in general you'd expect to find
solutions with q^2 mod N least N^2 or higher.

Here's an easy example I quickly noticed.

Oh cool. Consider 2^11 = 1 mod 23, which I like because it's easy.

So I want 1 mod 23, around 23^2 = 529

So 530 to try, 2*5*53, so 2+5+53 = 60, and 60 - 3 = 57.

57 mod 23 = 11.

One check to find m=11, so the supposed discrete log advantage was
erased by the algebra.

It simply didn't care about all those values for m.

Notice that naively looking at q^2 mod N, at low values would give the
appearance of failure or a bad algorithm though there is a
mathematical reason for a low probability of success.

(The probability of success at low values is roughly 1/N.)

Which is why basic research is not easy.

Knee-jerk assaults against basic researchers are just sad, but I think
reflect a bad education system. People think it's supposed to be
obvious and easy.

Real world problems rarely are either.

Replies from posters wishing to junk this approach are a cautionary
tale for wouldbe math people. They surely did not wish to go into
history in this way, but a part of history they will be.

Um, I personally would NOT TRUST encryption based on the use of
discrete logarithms for encryption.

I have no confidence in encryption based on discrete logarithms given
these fresh mathematical results.


James Harris
From: Joshua Cranmer on 1 Jul 2010 22:51
On 07/01/2010 09:58 PM, JSH wrote:
> Assuming the smallest primes. But with small primes for c=5, it'd
> still be approximately N^2, and in general you'd expect to find
> solutions with q^2 mod N least N^2 or higher.

Put on your thinking cap here. If N is on the order of 1024 bits, how
many bits does N^2 / 2 have?

You are proposing solving a discrete log problem by factoring a number
twice the magnitude. Also recall that all known factoring algorithms are
exponentional in the number of bits of the number.

> Oh cool. Consider 2^11 = 1 mod 23, which I like because it's easy.

Easy problems may suffice for examples, but they suck for proof of
concepts, especially if you are asserting that your algorithm is notably
fast.

Let's go for a more interesting problem:
2^m = 1 mod 5123819881

> (The probability of success at low values is roughly 1/N.)

Which would suggest O(N) numbers to try to factor, about what I was
figuring.

> Um, I personally would NOT TRUST encryption based on the use of
> discrete logarithms for encryption.

I would continue trusting them. Factoring is still slow, and your
algorithm already has to factor at least one number; the record for RSA
is RSA-768, solved last December. The announcement reports:

We spent half a year on 80 processors on polynomial selection. This was
about 3% of the main task, the sieving, which was done on many hundreds
of machines and took almost two years. On a single core 2.2 GHz AMD
Opteron processor with 2 GB RAM, sieving would have taken about fifteen
hundred years.

They furthermore estimated that a 1024-bit number would be around 1000
times harder. My certificates seem to be using 2048-bit keys, and I
don't do anything critically important online, so I doubt that someone
would take the computer-millennia of effort needed just to figure out
the password to my bank account. Especially when they can craft a
phishing scam and ask the user directly for their password for a few
dollars.

If I were a bank looking at encrypting all bank records or the military,
sure, I wouldn't used discrete logs, but I wouldn't have used them for
several years already. ECC is already implemented and more secure for
similar key widths. In either case, this result doesn't change my opinion.

--
Beware of bugs in the above code; I have only proved it correct, not
tried it. -- Donald E. Knuth
From: Jesse F. Hughes on 1 Jul 2010 23:13
Joshua Cranmer <Pidgeot18(a)verizon.invalid> writes:

> Put on your thinking cap here. If N is on the order of 1024 bits, how
> many bits does N^2 / 2 have?
>
> You are proposing solving a discrete log problem by factoring a number
> twice the magnitude.

It's just like James says. You people will say anything to distract
from his research. In short, you lie.

It is not twice the magnitude. It's one bit short of twice the
magnitude.

Did you think you could get away with that?

--
"Being in the ring of algebraic integers is just kind of being in a
weird place, but it's no different than if you are in an Elk's Lodge
with weird made up rules versus just being out in regular society."
-- James S. Harris, teacher
From: Jesse F. Hughes on 1 Jul 2010 23:37
JSH <jstevh(a)gmail.com> writes:

> And there you go again, putting up an example that requires a computer
> program, where said program might be close to something that is
> military grade.
>
> You really don't understand the situation yet, do you?
>
> Conceivably we're closing in on territory where very serious people
> who carry guns would be VERY INTERESTED.
>
> It is not a game. Just because something is on Usenet it does not
> make it trivial.
>
> They carry guns. The guns have real bullets. Bullets can kill you,
> when shot at you out of a gun. Understand? It's not play time any
> longer.

I *love* it when you talk like that.

--
"Being in the ring of algebraic integers is just kind of being in a
weird place, but it's no different than if you are in an Elk's Lodge
with weird made up rules versus just being out in regular society."
-- James S. Harris, teacher
From: Tim Little on 2 Jul 2010 02:25
On 2010-07-01, JSH <jstevh(a)gmail.com> wrote:
> On Jun 30, 10:06 pm, MichaelW <ms...(a)tpg.com.au> wrote:
>> On Jul 1, 1:20 pm, JSH <jst...(a)gmail.com> wrote:
>> > So what would you do next if you were me?
>> Spend 5 years getting a decent education in mathematics.
>
> But what about THIS result? What would YOU do with it if it were
> yours?

If it were mine, I wouldn't call it a result at all. At best it would
be a fairly trivial intermediate step toward a result, but much more
likely it's a fairly trivial intermediate step toward other trivial
steps leading nowhere.

So: either follow up to see where it might lead (if I was very
optimistic), or work on something more likely to lead somewhere (if I
was more realistic).


> Why should I give a damn what you think?

No reason at all except that you asked the opinion of readers of this
group. You're perfectly free to ask people's opinions in the same
post you angrily disclaim any interest in the answers, and I'm
perfectly free to call you a jerkwad for doing so. Jerkwad.


- Tim
First  |  Prev  |  Next  |  Last
Pages: 1 2 3 4 5
Prev: New Differential Equation website
Next: How Can ZFC/PA do much of Math - it Can't Even Prove PA isConsistent (EASY PROOF)