Prev: JSH: Solving discrete logarithms
Next: Discrete logs result, sum of the factors upper bound?
From: JSH on 30 Jun 2010 19:51
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.

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.

Here's the example given in my prior post, which should make more
sense given the information above:

Solve for m, where:

2^m = 13 mod 23

so k = 2, and f_1*...*f_m = q^2 mod N = 13^2 mod 23 = 8 mod 23.

And I found a solution with f_1*...*f_m = 54, and

f_1 = 2, f_2 = 3, f_3 = 3, f_4 = 3

so c=4, and

m = (k-1)^{-1}(f_1 +...+ f_c - c) mod N = 2+3+3+3 - 4 = 7

And 2^7 = 128 = 13 mod 23.

Notice that 2 is a factor as are small primes. The method will try to
fit small primes if you are using small values which is about human
preference. The algebra tries to give you what you want based on the
size of the numbers you are factoring.

The value of c is dynamically set by the factorization of q^2 mod N.
But the results above indicate that the algebra must give you a
factorization 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.


James Harris



From: Pubkeybreaker on 1 Jul 2010 07:54
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.


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.

I think you are lying when you claim a degree in physics. In my home
state falsely claiming to have a degree is a crime.

Why do you keep ignoring these questions?
Could it be because you ARE lying about your degree?..........

From: JSH on 1 Jul 2010 09:45
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?

> I think you are lying when you claim a degree in physics.  In my home
> state falsely claiming to have a degree is a crime.
>
> Why do you keep ignoring these questions?
> Could it be because you ARE lying about your degree?..........

Hey, I say I have the degree, you say you think I'm lying. To me that
kind of creates an impasse.

After you've insulted me, why do you wish for me to jump through hoops
for your pleasure?

When you think I'm a liar ANYWAY.


James Harris
From: Pubkeybreaker on 1 Jul 2010 12:11
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.
From: JSH on 1 Jul 2010 19:35
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.


James Harris
 |  Next  |  Last
Pages: 1 2
Prev: JSH: Solving discrete logarithms
Next: Discrete logs result, sum of the factors upper bound?