Prev: JSH: Solving discrete logarithms
Next: Discrete logs result, sum of the factors upper bound?
From: Pubkeybreaker on 1 Jul 2010 21:14
On Jul 1, 7:35 pm, JSH <jst...(a)gmail.com> wrote:
> On Jul 1, 9:11 am, Pubkeybreaker <pubkeybrea...(a)aol.com> wrote:
>
>
>
>
>
> > On Jul 1, 9:45 am, JSH <jst...(a)gmail.com> wrote:
>
> > > On Jul 1, 4:54 am, Pubkeybreaker <pubkeybrea...(a)aol.com> wrote:
>
> > > > On Jun 30, 7:51 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
>
> > > > within that range which will work.
>
> > > > > And that is what's found with a first blush basic analysis.  It's not
> > > > > clear at this time what further information might result from more
> > > > > basic research.  My aim at this point is to answer criticism against
> > > > > this approach.
>
> > > > > Routinely posters reply requesting I demonstrate by breaking current
> > > > > encryption.  Well, if I could do that I wouldn't need to bother
> > > > > posting on newsgroups now would I?
>
> > > > > It's basic research.  Early stages.
>
> > > > When are you going to tell us the year when you got your claimed
> > > > degree at Vanderbilt???
>
> > > > You can also tell us why Vanderbilt will  not confirm that you ever
> > > > got a  degree there.
>
> > > Do schools actually just give out that information to random
> > > inquirers?
>
> > > > Doing so would put to rest the suspicions of many people who suspect
> > > > that you are lying when you claim to have a degree in physics.
>
> > > Why would anyone be suspicious?
>
> > Because you show almost a total lack of knowledge about the
> > mathematics
> > required to study physics.  You math skills are so poor that I doubt
> > that you
> > could even get through 1st year mechanics.
>
> > Prove me wrong.  I will graciously apologize.  Tell us the year that
> > you got your degree.
>
> Are you bugging my alma mater?  Did they tell you that you needed a
> degree year for a reply?
>
> Quit harassing Vanderbilt University.
>
A polite query is not harassment.

And I note that you still will not answer the question of
when you got your degree.
From: JSH on 1 Jul 2010 21:35
On Jun 30, 4:51 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 incorrect. I failed to notice that leaves an a_3 still in the
equation, so the quadratic cannot be removed by use of the free
variables.

> 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.

I was actually maybe on to something there more than I realized.

With c=4, two of the a's are free, leaving two constrained. Assuming
human beings will want smaller numbers to factor two of the f's will
be set by the equations, while two should be small primes.

But if the math shows no particular preference for residues, given
that the average residue is about N/2, one would expect solutions
around N^2 with c=4: (N/2)*(N/2)*2*2

For c=5, you'd have: (N/2)*(N/2)*2*2*2, or approximately 2N^2

So given human nature, one would look for solutions to q^2 mod N, near
N^2.

It would actually be probabilistically rare to find solutions near q^2
itself, as that would correspond to cases where the set a's were small
residues, which is against the average residue of about N/2.

Interesting.


James Harris
From: JSH on 1 Jul 2010 21:47
On Jul 1, 6:35 pm, JSH <jst...(a)gmail.com> wrote:
> On Jun 30, 4:51 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 incorrect.  I failed to notice that leaves an a_3 still in the
> equation, so the quadratic cannot be removed by use of the free
> variables.
>
>
>
>
>
> > 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.
>
> I was actually maybe on to something there more than I realized.
>
> With c=4, two of the a's are free, leaving two constrained.  Assuming
> human beings will want smaller numbers to factor two of the f's will
> be set by the equations, while two should be small primes.
>
> But if the math shows no particular preference for residues, given
> that the average residue is about N/2, one would expect solutions
> around N^2 with c=4: (N/2)*(N/2)*2*2
>
> For c=5, you'd have: (N/2)*(N/2)*2*2*2, or approximately 2N^2
>
> So given human nature, one would look for solutions to q^2 mod N, near
> N^2.

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.

That is just way too cool.
>
> It would actually be probabilistically rare to find solutions near q^2
> itself, as that would correspond to cases where the set a's were small
> residues, which is against the average residue of about N/2.

So naively looking at q^2 mod N near the low end wouldn't work well.

> Interesting.

Way cool. Really more like, fascinating.


James Harris


From: Mark Murray on 3 Jul 2010 16:32
On 03/07/2010 20:45, JSH wrote:
> It is algebra. Not as if it's human. It doesn't have human concerns
> nor does it care if it upsets human plans.

I don't understand. Earlier, you were saying it had intelligence.

M
--
Mark "No Nickname" Murray
Notable nebbish, extreme generalist.
First  |  Prev  | 
Pages: 1 2
Prev: JSH: Solving discrete logarithms
Next: Discrete logs result, sum of the factors upper bound?