Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  newsreader  groups  login

Message-ID:  

PURGE COMPLETE.


devel / comp.theory / Re: How to solve DLP (without solving MSR):

SubjectAuthor
* How to solve DLP (without solving MSR):B.H.
`* How to solve DLP (without solving MSR):B.H.
 `* How to solve DLP (without solving MSR):B.H.
  `* How to solve DLP (without solving MSR):B.H.
   `* How to solve DLP (without solving MSR):B.H.
    `* How to solve DLP (without solving MSR):B.H.
     `* How to solve DLP (without solving MSR):B.H.
      `* How to solve DLP (without solving MSR):B.H.
       `* How to solve DLP (without solving MSR):B.H.
        `* How to solve DLP (without solving MSR):B.H.
         `* How to solve DLP (without solving MSR):B.H.
          `- How to solve DLP (without solving MSR):B.H.

1
How to solve DLP (without solving MSR):

<66d931e6-e868-454c-a62c-5e51250f4e41n@googlegroups.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=35943&group=comp.theory#35943

 copy link   Newsgroups: comp.theory
X-Received: by 2002:ad4:5761:0:b0:473:7861:69d1 with SMTP id r1-20020ad45761000000b00473786169d1mr2624590qvx.73.1658544929271;
Fri, 22 Jul 2022 19:55:29 -0700 (PDT)
X-Received: by 2002:a25:2e50:0:b0:669:9a76:beb with SMTP id
b16-20020a252e50000000b006699a760bebmr2348051ybn.597.1658544929001; Fri, 22
Jul 2022 19:55:29 -0700 (PDT)
Path: i2pn2.org!i2pn.org!usenet.blueworldhosting.com!feed1.usenet.blueworldhosting.com!peer03.iad!feed-me.highwinds-media.com!news.highwinds-media.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.theory
Date: Fri, 22 Jul 2022 19:55:28 -0700 (PDT)
Injection-Info: google-groups.googlegroups.com; posting-host=173.53.104.152; posting-account=X_pe-goAAACrVTtZeoCLt7hslVPY2-Uo
NNTP-Posting-Host: 173.53.104.152
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <66d931e6-e868-454c-a62c-5e51250f4e41n@googlegroups.com>
Subject: How to solve DLP (without solving MSR):
From: xlt....@gmail.com (B.H.)
Injection-Date: Sat, 23 Jul 2022 02:55:29 +0000
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
X-Received-Bytes: 2656
 by: B.H. - Sat, 23 Jul 2022 02:55 UTC

Hi everyone,

Here is the solution.

You can find one solution to a DL instance by using "binary construction." Let's say it's a safe prime modulus. (I first devised this part of the approach in 2007.) Then use Euler's criterion to identify the last bit of the DL. Then, use properties of logs to "subtract one" from the DL. Now you need to take the sqrt to divide by 2, then repeat this process to find a working DL.

That is what I had in 2007. Today, I realized: Since the sqrt cannot be identified to be "the large one" or "the small one," you need a test. The test is, raise both powers to numbers close to 2. You need a rational number with a denominator that works given the modulus p and phi(p). Raise your two candidate sqrts to different powers like 1.99, except with appropriate denominators that work for the modular division, and test the frequency of the results being large or small. Typically, the smaller value, when squared, will be closer to the value that is the value squared, since (-x)^1.99 vs. x^1.99 is such that the latter is more likely to be "positive" and thus close to the same value as before (for x^2) and not thrown around the modulus value, although of course we're including an unpredictable factor, (x^(1.99))^(2/1.99). (The modular division might come up in an unexpected way..)

I haven't proved that this works but it looks like it should work intuitively. Let me know if it doesn't work right and you want me to try again; I refuse to publish my DL result that solves MSR.

-Philip White (philipjwhite@yahoo.com)

Re: How to solve DLP (without solving MSR):

<a17b33da-b782-42fa-9ee6-9ec144021da4n@googlegroups.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=35944&group=comp.theory#35944

 copy link   Newsgroups: comp.theory
X-Received: by 2002:ac8:7fc1:0:b0:31e:c575:a56c with SMTP id b1-20020ac87fc1000000b0031ec575a56cmr2648250qtk.11.1658546788770;
Fri, 22 Jul 2022 20:26:28 -0700 (PDT)
X-Received: by 2002:a25:c68f:0:b0:670:7e87:28c0 with SMTP id
k137-20020a25c68f000000b006707e8728c0mr2424011ybf.99.1658546788517; Fri, 22
Jul 2022 20:26:28 -0700 (PDT)
Path: i2pn2.org!i2pn.org!usenet.blueworldhosting.com!feed1.usenet.blueworldhosting.com!peer03.iad!feed-me.highwinds-media.com!news.highwinds-media.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.theory
Date: Fri, 22 Jul 2022 20:26:28 -0700 (PDT)
In-Reply-To: <66d931e6-e868-454c-a62c-5e51250f4e41n@googlegroups.com>
Injection-Info: google-groups.googlegroups.com; posting-host=173.53.104.152; posting-account=X_pe-goAAACrVTtZeoCLt7hslVPY2-Uo
NNTP-Posting-Host: 173.53.104.152
References: <66d931e6-e868-454c-a62c-5e51250f4e41n@googlegroups.com>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <a17b33da-b782-42fa-9ee6-9ec144021da4n@googlegroups.com>
Subject: Re: How to solve DLP (without solving MSR):
From: xlt....@gmail.com (B.H.)
Injection-Date: Sat, 23 Jul 2022 03:26:28 +0000
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
X-Received-Bytes: 3663
 by: B.H. - Sat, 23 Jul 2022 03:26 UTC

On Friday, July 22, 2022 at 10:55:30 PM UTC-4, B.H. wrote:
> Hi everyone,
>
> Here is the solution.
>
> You can find one solution to a DL instance by using "binary construction." Let's say it's a safe prime modulus. (I first devised this part of the approach in 2007.) Then use Euler's criterion to identify the last bit of the DL. Then, use properties of logs to "subtract one" from the DL. Now you need to take the sqrt to divide by 2, then repeat this process to find a working DL.
>
> That is what I had in 2007. Today, I realized: Since the sqrt cannot be identified to be "the large one" or "the small one," you need a test. The test is, raise both powers to numbers close to 2. You need a rational number with a denominator that works given the modulus p and phi(p). Raise your two candidate sqrts to different powers like 1.99, except with appropriate denominators that work for the modular division, and test the frequency of the results being large or small. Typically, the smaller value, when squared, will be closer to the value that is the value squared, since (-x)^1.99 vs. x^1.99 is such that the latter is more likely to be "positive" and thus close to the same value as before (for x^2) and not thrown around the modulus value, although of course we're including an unpredictable factor, (x^(1.99))^(2/1.99). (The modular division might come up in an unexpected way.)
>
> I haven't proved that this works but it looks like it should work intuitively. Let me know if it doesn't work right and you want me to try again; I refuse to publish my DL result that solves MSR.
>
> -Philip White (philip...@yahoo.com)

The key to raising something to (2/1.99) or something is, you can use modular division to calc 2/1.99, and then if it's x to that power, you can treat it as multiplying by x to that power minus one, and you can calculate out what that is. So it is not that all that unpredictable. Basically you want to track how different -x and x raised to 1.99 are; you have to see if the .99 turned up odd or even in the modular division, to see if the negative sign will get canceled out, which it sometimes will and sometimes won't.

If you have access to a number-theory-literate programmer, you should be able to get this and code it within a few hours...I don't have a proof but don't see why it wouldn't work.

-Philip White (philipjwhite@yahoo.com)

Re: How to solve DLP (without solving MSR):

<80ed1143-b11d-4dcc-a31a-b34b94ec300bn@googlegroups.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=35945&group=comp.theory#35945

 copy link   Newsgroups: comp.theory
X-Received: by 2002:ac8:5809:0:b0:31f:2052:922f with SMTP id g9-20020ac85809000000b0031f2052922fmr2636594qtg.253.1658547009968;
Fri, 22 Jul 2022 20:30:09 -0700 (PDT)
X-Received: by 2002:a81:3d52:0:b0:31e:7b01:452 with SMTP id
k79-20020a813d52000000b0031e7b010452mr2423493ywa.494.1658547009711; Fri, 22
Jul 2022 20:30:09 -0700 (PDT)
Path: i2pn2.org!i2pn.org!usenet.blueworldhosting.com!feed1.usenet.blueworldhosting.com!peer03.iad!feed-me.highwinds-media.com!news.highwinds-media.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.theory
Date: Fri, 22 Jul 2022 20:30:09 -0700 (PDT)
In-Reply-To: <a17b33da-b782-42fa-9ee6-9ec144021da4n@googlegroups.com>
Injection-Info: google-groups.googlegroups.com; posting-host=173.53.104.152; posting-account=X_pe-goAAACrVTtZeoCLt7hslVPY2-Uo
NNTP-Posting-Host: 173.53.104.152
References: <66d931e6-e868-454c-a62c-5e51250f4e41n@googlegroups.com> <a17b33da-b782-42fa-9ee6-9ec144021da4n@googlegroups.com>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <80ed1143-b11d-4dcc-a31a-b34b94ec300bn@googlegroups.com>
Subject: Re: How to solve DLP (without solving MSR):
From: xlt....@gmail.com (B.H.)
Injection-Date: Sat, 23 Jul 2022 03:30:09 +0000
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
X-Received-Bytes: 4121
 by: B.H. - Sat, 23 Jul 2022 03:30 UTC

On Friday, July 22, 2022 at 11:26:29 PM UTC-4, B.H. wrote:
> On Friday, July 22, 2022 at 10:55:30 PM UTC-4, B.H. wrote:
> > Hi everyone,
> >
> > Here is the solution.
> >
> > You can find one solution to a DL instance by using "binary construction." Let's say it's a safe prime modulus. (I first devised this part of the approach in 2007.) Then use Euler's criterion to identify the last bit of the DL. Then, use properties of logs to "subtract one" from the DL. Now you need to take the sqrt to divide by 2, then repeat this process to find a working DL.
> >
> > That is what I had in 2007. Today, I realized: Since the sqrt cannot be identified to be "the large one" or "the small one," you need a test. The test is, raise both powers to numbers close to 2. You need a rational number with a denominator that works given the modulus p and phi(p). Raise your two candidate sqrts to different powers like 1.99, except with appropriate denominators that work for the modular division, and test the frequency of the results being large or small. Typically, the smaller value, when squared, will be closer to the value that is the value squared, since (-x)^1.99 vs. x^1.99 is such that the latter is more likely to be "positive" and thus close to the same value as before (for x^2) and not thrown around the modulus value, although of course we're including an unpredictable factor, (x^(1..99))^(2/1.99). (The modular division might come up in an unexpected way.)
> >
> > I haven't proved that this works but it looks like it should work intuitively. Let me know if it doesn't work right and you want me to try again; I refuse to publish my DL result that solves MSR.
> >
> > -Philip White (philip...@yahoo.com)
> The key to raising something to (2/1.99) or something is, you can use modular division to calc 2/1.99, and then if it's x to that power, you can treat it as multiplying by x to that power minus one, and you can calculate out what that is. So it is not that all that unpredictable. Basically you want to track how different -x and x raised to 1.99 are; you have to see if the .99 turned up odd or even in the modular division, to see if the negative sign will get canceled out, which it sometimes will and sometimes won't.
>
> If you have access to a number-theory-literate programmer, you should be able to get this and code it within a few hours...I don't have a proof but don't see why it wouldn't work.
>
> -Philip White (philip...@yahoo.com)

Basically, when x^(1.99) and (-x)^(1.99) come up different (half the time?), you have to look at (x^1.99)^(2/1.99) and see which value is the positive x value, based on the multiplication that should check out in the latter expression, because x is positive there.

-Philip White

Re: How to solve DLP (without solving MSR):

<03a05bd0-98be-41b9-b6ee-b6bb3d74a46an@googlegroups.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=35946&group=comp.theory#35946

 copy link   Newsgroups: comp.theory
X-Received: by 2002:ac8:5a48:0:b0:31e:f288:3d68 with SMTP id o8-20020ac85a48000000b0031ef2883d68mr2664259qta.111.1658547951487;
Fri, 22 Jul 2022 20:45:51 -0700 (PDT)
X-Received: by 2002:a81:2506:0:b0:31e:7c6f:ce with SMTP id l6-20020a812506000000b0031e7c6f00cemr2505526ywl.16.1658547951201;
Fri, 22 Jul 2022 20:45:51 -0700 (PDT)
Path: i2pn2.org!i2pn.org!usenet.blueworldhosting.com!feed1.usenet.blueworldhosting.com!peer03.iad!feed-me.highwinds-media.com!news.highwinds-media.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.theory
Date: Fri, 22 Jul 2022 20:45:51 -0700 (PDT)
In-Reply-To: <80ed1143-b11d-4dcc-a31a-b34b94ec300bn@googlegroups.com>
Injection-Info: google-groups.googlegroups.com; posting-host=173.53.104.152; posting-account=X_pe-goAAACrVTtZeoCLt7hslVPY2-Uo
NNTP-Posting-Host: 173.53.104.152
References: <66d931e6-e868-454c-a62c-5e51250f4e41n@googlegroups.com>
<a17b33da-b782-42fa-9ee6-9ec144021da4n@googlegroups.com> <80ed1143-b11d-4dcc-a31a-b34b94ec300bn@googlegroups.com>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <03a05bd0-98be-41b9-b6ee-b6bb3d74a46an@googlegroups.com>
Subject: Re: How to solve DLP (without solving MSR):
From: xlt....@gmail.com (B.H.)
Injection-Date: Sat, 23 Jul 2022 03:45:51 +0000
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
X-Received-Bytes: 4930
 by: B.H. - Sat, 23 Jul 2022 03:45 UTC

On Friday, July 22, 2022 at 11:30:11 PM UTC-4, B.H. wrote:
> On Friday, July 22, 2022 at 11:26:29 PM UTC-4, B.H. wrote:
> > On Friday, July 22, 2022 at 10:55:30 PM UTC-4, B.H. wrote:
> > > Hi everyone,
> > >
> > > Here is the solution.
> > >
> > > You can find one solution to a DL instance by using "binary construction." Let's say it's a safe prime modulus. (I first devised this part of the approach in 2007.) Then use Euler's criterion to identify the last bit of the DL. Then, use properties of logs to "subtract one" from the DL. Now you need to take the sqrt to divide by 2, then repeat this process to find a working DL.
> > >
> > > That is what I had in 2007. Today, I realized: Since the sqrt cannot be identified to be "the large one" or "the small one," you need a test. The test is, raise both powers to numbers close to 2. You need a rational number with a denominator that works given the modulus p and phi(p). Raise your two candidate sqrts to different powers like 1.99, except with appropriate denominators that work for the modular division, and test the frequency of the results being large or small. Typically, the smaller value, when squared, will be closer to the value that is the value squared, since (-x)^1.99 vs. x^1.99 is such that the latter is more likely to be "positive" and thus close to the same value as before (for x^2) and not thrown around the modulus value, although of course we're including an unpredictable factor, (x^(1.99))^(2/1.99). (The modular division might come up in an unexpected way.)
> > >
> > > I haven't proved that this works but it looks like it should work intuitively. Let me know if it doesn't work right and you want me to try again; I refuse to publish my DL result that solves MSR.
> > >
> > > -Philip White (philip...@yahoo.com)
> > The key to raising something to (2/1.99) or something is, you can use modular division to calc 2/1.99, and then if it's x to that power, you can treat it as multiplying by x to that power minus one, and you can calculate out what that is. So it is not that all that unpredictable. Basically you want to track how different -x and x raised to 1.99 are; you have to see if the .99 turned up odd or even in the modular division, to see if the negative sign will get canceled out, which it sometimes will and sometimes won't.
> >
> > If you have access to a number-theory-literate programmer, you should be able to get this and code it within a few hours...I don't have a proof but don't see why it wouldn't work.
> >
> > -Philip White (philip...@yahoo.com)
> Basically, when x^(1.99) and (-x)^(1.99) come up different (half the time?), you have to look at (x^1.99)^(2/1.99) and see which value is the positive x value, based on the multiplication that should check out in the latter expression, because x is positive there.
>
> -Philip White

The goal, again, is to find the x value that is linked to the DL that is closer to 0. The smaller x will be the one that, when multiplied by the "the multiplication" (where you replace the exponent with the multiplication), clearly comes out to something that is true even in non-modular terms, e.g., if you multiply something small by something big, if you don't wrap around, you should see that it is the same as a non-modular multiplication.

I am not writing extremely clearly, I am tossing out notes to help programmers. I'll look at what I've written again tomorrow morning, but the idea seems good.

-Philip

Re: How to solve DLP (without solving MSR):

<d619a9dc-d05f-42a3-9bbd-0c4e07251e80n@googlegroups.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=35949&group=comp.theory#35949

 copy link   Newsgroups: comp.theory
X-Received: by 2002:ad4:5e8e:0:b0:473:f8df:11fd with SMTP id jl14-20020ad45e8e000000b00473f8df11fdmr2479446qvb.15.1658550907656;
Fri, 22 Jul 2022 21:35:07 -0700 (PDT)
X-Received: by 2002:a05:6902:110b:b0:670:c034:4f61 with SMTP id
o11-20020a056902110b00b00670c0344f61mr2859239ybu.238.1658550907445; Fri, 22
Jul 2022 21:35:07 -0700 (PDT)
Path: i2pn2.org!i2pn.org!usenet.blueworldhosting.com!feed1.usenet.blueworldhosting.com!peer03.iad!feed-me.highwinds-media.com!news.highwinds-media.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.theory
Date: Fri, 22 Jul 2022 21:35:07 -0700 (PDT)
In-Reply-To: <03a05bd0-98be-41b9-b6ee-b6bb3d74a46an@googlegroups.com>
Injection-Info: google-groups.googlegroups.com; posting-host=173.53.104.152; posting-account=X_pe-goAAACrVTtZeoCLt7hslVPY2-Uo
NNTP-Posting-Host: 173.53.104.152
References: <66d931e6-e868-454c-a62c-5e51250f4e41n@googlegroups.com>
<a17b33da-b782-42fa-9ee6-9ec144021da4n@googlegroups.com> <80ed1143-b11d-4dcc-a31a-b34b94ec300bn@googlegroups.com>
<03a05bd0-98be-41b9-b6ee-b6bb3d74a46an@googlegroups.com>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <d619a9dc-d05f-42a3-9bbd-0c4e07251e80n@googlegroups.com>
Subject: Re: How to solve DLP (without solving MSR):
From: xlt....@gmail.com (B.H.)
Injection-Date: Sat, 23 Jul 2022 04:35:07 +0000
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
X-Received-Bytes: 6482
 by: B.H. - Sat, 23 Jul 2022 04:35 UTC

On Friday, July 22, 2022 at 11:45:52 PM UTC-4, B.H. wrote:
> On Friday, July 22, 2022 at 11:30:11 PM UTC-4, B.H. wrote:
> > On Friday, July 22, 2022 at 11:26:29 PM UTC-4, B.H. wrote:
> > > On Friday, July 22, 2022 at 10:55:30 PM UTC-4, B.H. wrote:
> > > > Hi everyone,
> > > >
> > > > Here is the solution.
> > > >
> > > > You can find one solution to a DL instance by using "binary construction." Let's say it's a safe prime modulus. (I first devised this part of the approach in 2007.) Then use Euler's criterion to identify the last bit of the DL. Then, use properties of logs to "subtract one" from the DL. Now you need to take the sqrt to divide by 2, then repeat this process to find a working DL.
> > > >
> > > > That is what I had in 2007. Today, I realized: Since the sqrt cannot be identified to be "the large one" or "the small one," you need a test. The test is, raise both powers to numbers close to 2. You need a rational number with a denominator that works given the modulus p and phi(p). Raise your two candidate sqrts to different powers like 1.99, except with appropriate denominators that work for the modular division, and test the frequency of the results being large or small. Typically, the smaller value, when squared, will be closer to the value that is the value squared, since (-x)^1.99 vs. x^1.99 is such that the latter is more likely to be "positive" and thus close to the same value as before (for x^2) and not thrown around the modulus value, although of course we're including an unpredictable factor, (x^(1.99))^(2/1.99). (The modular division might come up in an unexpected way.)
> > > >
> > > > I haven't proved that this works but it looks like it should work intuitively. Let me know if it doesn't work right and you want me to try again; I refuse to publish my DL result that solves MSR.
> > > >
> > > > -Philip White (philip...@yahoo.com)
> > > The key to raising something to (2/1.99) or something is, you can use modular division to calc 2/1.99, and then if it's x to that power, you can treat it as multiplying by x to that power minus one, and you can calculate out what that is. So it is not that all that unpredictable. Basically you want to track how different -x and x raised to 1.99 are; you have to see if the .99 turned up odd or even in the modular division, to see if the negative sign will get canceled out, which it sometimes will and sometimes won't.
> > >
> > > If you have access to a number-theory-literate programmer, you should be able to get this and code it within a few hours...I don't have a proof but don't see why it wouldn't work.
> > >
> > > -Philip White (philip...@yahoo.com)
> > Basically, when x^(1.99) and (-x)^(1.99) come up different (half the time?), you have to look at (x^1.99)^(2/1.99) and see which value is the positive x value, based on the multiplication that should check out in the latter expression, because x is positive there.
> >
> > -Philip White
> The goal, again, is to find the x value that is linked to the DL that is closer to 0. The smaller x will be the one that, when multiplied by the "the multiplication" (where you replace the exponent with the multiplication), clearly comes out to something that is true even in non-modular terms, e.g.., if you multiply something small by something big, if you don't wrap around, you should see that it is the same as a non-modular multiplication.
>
> I am not writing extremely clearly, I am tossing out notes to help programmers. I'll look at what I've written again tomorrow morning, but the idea seems good.
>
> -Philip

The way I wrote it, it doesn't quite work, but I can fix it.

The idea is, we need the "small DL" to behave in a certain predictable way. So we start with an "unmasked number y," and compute the modular exponentiation of it; now, we know what the value of y is, and can manipulate it with properties of logarithms. Using such properties, we manipulate y to be such that it is close to some value that is like x^0.99, where we let 0.99 differ from that precise value a little bit, and decide on what it is by equating it to y'. E.g., based on our knowledge of y, we could set x^0.85 = y' (where we also know the manipulated value y'), and then do x*x^0.85 = x^1.85 = x*y'.

So once we have that, we can "try different values" that are close to 2 like 1.85 and see, based on our ability to know the value of y', if x^1.85 (for whatever value) represented a "big increase." In particular, if we can get y' to be small in some cases when we try repeatedly, then we have found a situation where we can get fairly strong statistical evidence that the multiplication by y' constituted a quasi-squaring that did not "wrap around." In other words, I'm asserting, without proof right now, that y' will be "much more frequently" equal to x^j when j is close to 2 when y' is small.

-Philip White

Re: How to solve DLP (without solving MSR):

<b507f19a-ec52-471b-95b2-fdd4ecbf13d1n@googlegroups.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=35961&group=comp.theory#35961

 copy link   Newsgroups: comp.theory
X-Received: by 2002:a37:be42:0:b0:6b5:e542:233b with SMTP id o63-20020a37be42000000b006b5e542233bmr3727376qkf.498.1658588901561;
Sat, 23 Jul 2022 08:08:21 -0700 (PDT)
X-Received: by 2002:a05:6902:723:b0:670:b2a7:b267 with SMTP id
l3-20020a056902072300b00670b2a7b267mr3915420ybt.345.1658588901202; Sat, 23
Jul 2022 08:08:21 -0700 (PDT)
Path: i2pn2.org!i2pn.org!usenet.blueworldhosting.com!feed1.usenet.blueworldhosting.com!peer01.iad!feed-me.highwinds-media.com!news.highwinds-media.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.theory
Date: Sat, 23 Jul 2022 08:08:20 -0700 (PDT)
In-Reply-To: <d619a9dc-d05f-42a3-9bbd-0c4e07251e80n@googlegroups.com>
Injection-Info: google-groups.googlegroups.com; posting-host=173.53.104.152; posting-account=X_pe-goAAACrVTtZeoCLt7hslVPY2-Uo
NNTP-Posting-Host: 173.53.104.152
References: <66d931e6-e868-454c-a62c-5e51250f4e41n@googlegroups.com>
<a17b33da-b782-42fa-9ee6-9ec144021da4n@googlegroups.com> <80ed1143-b11d-4dcc-a31a-b34b94ec300bn@googlegroups.com>
<03a05bd0-98be-41b9-b6ee-b6bb3d74a46an@googlegroups.com> <d619a9dc-d05f-42a3-9bbd-0c4e07251e80n@googlegroups.com>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <b507f19a-ec52-471b-95b2-fdd4ecbf13d1n@googlegroups.com>
Subject: Re: How to solve DLP (without solving MSR):
From: xlt....@gmail.com (B.H.)
Injection-Date: Sat, 23 Jul 2022 15:08:21 +0000
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
X-Received-Bytes: 7089
 by: B.H. - Sat, 23 Jul 2022 15:08 UTC

On Saturday, July 23, 2022 at 12:35:09 AM UTC-4, B.H. wrote:
> On Friday, July 22, 2022 at 11:45:52 PM UTC-4, B.H. wrote:
> > On Friday, July 22, 2022 at 11:30:11 PM UTC-4, B.H. wrote:
> > > On Friday, July 22, 2022 at 11:26:29 PM UTC-4, B.H. wrote:
> > > > On Friday, July 22, 2022 at 10:55:30 PM UTC-4, B.H. wrote:
> > > > > Hi everyone,
> > > > >
> > > > > Here is the solution.
> > > > >
> > > > > You can find one solution to a DL instance by using "binary construction." Let's say it's a safe prime modulus. (I first devised this part of the approach in 2007.) Then use Euler's criterion to identify the last bit of the DL. Then, use properties of logs to "subtract one" from the DL. Now you need to take the sqrt to divide by 2, then repeat this process to find a working DL.
> > > > >
> > > > > That is what I had in 2007. Today, I realized: Since the sqrt cannot be identified to be "the large one" or "the small one," you need a test.. The test is, raise both powers to numbers close to 2. You need a rational number with a denominator that works given the modulus p and phi(p). Raise your two candidate sqrts to different powers like 1.99, except with appropriate denominators that work for the modular division, and test the frequency of the results being large or small. Typically, the smaller value, when squared, will be closer to the value that is the value squared, since (-x)^1.99 vs. x^1.99 is such that the latter is more likely to be "positive" and thus close to the same value as before (for x^2) and not thrown around the modulus value, although of course we're including an unpredictable factor, (x^(1.99))^(2/1.99). (The modular division might come up in an unexpected way.)
> > > > >
> > > > > I haven't proved that this works but it looks like it should work intuitively. Let me know if it doesn't work right and you want me to try again; I refuse to publish my DL result that solves MSR.
> > > > >
> > > > > -Philip White (philip...@yahoo.com)
> > > > The key to raising something to (2/1.99) or something is, you can use modular division to calc 2/1.99, and then if it's x to that power, you can treat it as multiplying by x to that power minus one, and you can calculate out what that is. So it is not that all that unpredictable. Basically you want to track how different -x and x raised to 1.99 are; you have to see if the .99 turned up odd or even in the modular division, to see if the negative sign will get canceled out, which it sometimes will and sometimes won't.
> > > >
> > > > If you have access to a number-theory-literate programmer, you should be able to get this and code it within a few hours...I don't have a proof but don't see why it wouldn't work.
> > > >
> > > > -Philip White (philip...@yahoo.com)
> > > Basically, when x^(1.99) and (-x)^(1.99) come up different (half the time?), you have to look at (x^1.99)^(2/1.99) and see which value is the positive x value, based on the multiplication that should check out in the latter expression, because x is positive there.
> > >
> > > -Philip White
> > The goal, again, is to find the x value that is linked to the DL that is closer to 0. The smaller x will be the one that, when multiplied by the "the multiplication" (where you replace the exponent with the multiplication), clearly comes out to something that is true even in non-modular terms, e..g., if you multiply something small by something big, if you don't wrap around, you should see that it is the same as a non-modular multiplication.
> >
> > I am not writing extremely clearly, I am tossing out notes to help programmers. I'll look at what I've written again tomorrow morning, but the idea seems good.
> >
> > -Philip
> The way I wrote it, it doesn't quite work, but I can fix it.
>
> The idea is, we need the "small DL" to behave in a certain predictable way. So we start with an "unmasked number y," and compute the modular exponentiation of it; now, we know what the value of y is, and can manipulate it with properties of logarithms. Using such properties, we manipulate y to be such that it is close to some value that is like x^0.99, where we let 0.99 differ from that precise value a little bit, and decide on what it is by equating it to y'. E.g., based on our knowledge of y, we could set x^0.85 = y' (where we also know the manipulated value y'), and then do x*x^0.85 = x^1.85 = x*y'.
>
> So once we have that, we can "try different values" that are close to 2 like 1.85 and see, based on our ability to know the value of y', if x^1.85 (for whatever value) represented a "big increase." In particular, if we can get y' to be small in some cases when we try repeatedly, then we have found a situation where we can get fairly strong statistical evidence that the multiplication by y' constituted a quasi-squaring that did not "wrap around." In other words, I'm asserting, without proof right now, that y' will be "much more frequently" equal to x^j when j is close to 2 when y' is small.
>
> -Philip White

Btw, when working with a number like 0.85, you might have to track the fractional power to see if it will lead to wrap-around. Sometimes it will, sometimes it won't; if you can feed known quantities into the DL black box, you can keep track of both the "unmasked value" and the "masked value," as with y', even when the number is subject to manipulations based on properties of logs.

Re: How to solve DLP (without solving MSR):

<4767ceee-04e0-4fe7-abd3-33c96034818cn@googlegroups.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=35971&group=comp.theory#35971

 copy link   Newsgroups: comp.theory
X-Received: by 2002:ac8:7d96:0:b0:31e:f953:ae40 with SMTP id c22-20020ac87d96000000b0031ef953ae40mr4533262qtd.511.1658595222826;
Sat, 23 Jul 2022 09:53:42 -0700 (PDT)
X-Received: by 2002:a81:1e94:0:b0:31e:8e3b:f05a with SMTP id
e142-20020a811e94000000b0031e8e3bf05amr4370618ywe.172.1658595222599; Sat, 23
Jul 2022 09:53:42 -0700 (PDT)
Path: i2pn2.org!i2pn.org!usenet.blueworldhosting.com!feed1.usenet.blueworldhosting.com!peer02.iad!feed-me.highwinds-media.com!news.highwinds-media.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.theory
Date: Sat, 23 Jul 2022 09:53:42 -0700 (PDT)
In-Reply-To: <b507f19a-ec52-471b-95b2-fdd4ecbf13d1n@googlegroups.com>
Injection-Info: google-groups.googlegroups.com; posting-host=173.53.104.152; posting-account=X_pe-goAAACrVTtZeoCLt7hslVPY2-Uo
NNTP-Posting-Host: 173.53.104.152
References: <66d931e6-e868-454c-a62c-5e51250f4e41n@googlegroups.com>
<a17b33da-b782-42fa-9ee6-9ec144021da4n@googlegroups.com> <80ed1143-b11d-4dcc-a31a-b34b94ec300bn@googlegroups.com>
<03a05bd0-98be-41b9-b6ee-b6bb3d74a46an@googlegroups.com> <d619a9dc-d05f-42a3-9bbd-0c4e07251e80n@googlegroups.com>
<b507f19a-ec52-471b-95b2-fdd4ecbf13d1n@googlegroups.com>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <4767ceee-04e0-4fe7-abd3-33c96034818cn@googlegroups.com>
Subject: Re: How to solve DLP (without solving MSR):
From: xlt....@gmail.com (B.H.)
Injection-Date: Sat, 23 Jul 2022 16:53:42 +0000
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
X-Received-Bytes: 8186
 by: B.H. - Sat, 23 Jul 2022 16:53 UTC

On Saturday, July 23, 2022 at 11:08:22 AM UTC-4, B.H. wrote:
> On Saturday, July 23, 2022 at 12:35:09 AM UTC-4, B.H. wrote:
> > On Friday, July 22, 2022 at 11:45:52 PM UTC-4, B.H. wrote:
> > > On Friday, July 22, 2022 at 11:30:11 PM UTC-4, B.H. wrote:
> > > > On Friday, July 22, 2022 at 11:26:29 PM UTC-4, B.H. wrote:
> > > > > On Friday, July 22, 2022 at 10:55:30 PM UTC-4, B.H. wrote:
> > > > > > Hi everyone,
> > > > > >
> > > > > > Here is the solution.
> > > > > >
> > > > > > You can find one solution to a DL instance by using "binary construction." Let's say it's a safe prime modulus. (I first devised this part of the approach in 2007.) Then use Euler's criterion to identify the last bit of the DL. Then, use properties of logs to "subtract one" from the DL. Now you need to take the sqrt to divide by 2, then repeat this process to find a working DL.
> > > > > >
> > > > > > That is what I had in 2007. Today, I realized: Since the sqrt cannot be identified to be "the large one" or "the small one," you need a test. The test is, raise both powers to numbers close to 2. You need a rational number with a denominator that works given the modulus p and phi(p). Raise your two candidate sqrts to different powers like 1.99, except with appropriate denominators that work for the modular division, and test the frequency of the results being large or small. Typically, the smaller value, when squared, will be closer to the value that is the value squared, since (-x)^1.99 vs. x^1.99 is such that the latter is more likely to be "positive" and thus close to the same value as before (for x^2) and not thrown around the modulus value, although of course we're including an unpredictable factor, (x^(1.99))^(2/1.99). (The modular division might come up in an unexpected way.)
> > > > > >
> > > > > > I haven't proved that this works but it looks like it should work intuitively. Let me know if it doesn't work right and you want me to try again; I refuse to publish my DL result that solves MSR.
> > > > > >
> > > > > > -Philip White (philip...@yahoo.com)
> > > > > The key to raising something to (2/1.99) or something is, you can use modular division to calc 2/1.99, and then if it's x to that power, you can treat it as multiplying by x to that power minus one, and you can calculate out what that is. So it is not that all that unpredictable. Basically you want to track how different -x and x raised to 1.99 are; you have to see if the .99 turned up odd or even in the modular division, to see if the negative sign will get canceled out, which it sometimes will and sometimes won't.
> > > > >
> > > > > If you have access to a number-theory-literate programmer, you should be able to get this and code it within a few hours...I don't have a proof but don't see why it wouldn't work.
> > > > >
> > > > > -Philip White (philip...@yahoo.com)
> > > > Basically, when x^(1.99) and (-x)^(1.99) come up different (half the time?), you have to look at (x^1.99)^(2/1.99) and see which value is the positive x value, based on the multiplication that should check out in the latter expression, because x is positive there.
> > > >
> > > > -Philip White
> > > The goal, again, is to find the x value that is linked to the DL that is closer to 0. The smaller x will be the one that, when multiplied by the "the multiplication" (where you replace the exponent with the multiplication), clearly comes out to something that is true even in non-modular terms, e.g., if you multiply something small by something big, if you don't wrap around, you should see that it is the same as a non-modular multiplication.
> > >
> > > I am not writing extremely clearly, I am tossing out notes to help programmers. I'll look at what I've written again tomorrow morning, but the idea seems good.
> > >
> > > -Philip
> > The way I wrote it, it doesn't quite work, but I can fix it.
> >
> > The idea is, we need the "small DL" to behave in a certain predictable way. So we start with an "unmasked number y," and compute the modular exponentiation of it; now, we know what the value of y is, and can manipulate it with properties of logarithms. Using such properties, we manipulate y to be such that it is close to some value that is like x^0.99, where we let 0.99 differ from that precise value a little bit, and decide on what it is by equating it to y'. E.g., based on our knowledge of y, we could set x^0.85 = y' (where we also know the manipulated value y'), and then do x*x^0.85 = x^1.85 = x*y'.
> >
> > So once we have that, we can "try different values" that are close to 2 like 1.85 and see, based on our ability to know the value of y', if x^1.85 (for whatever value) represented a "big increase." In particular, if we can get y' to be small in some cases when we try repeatedly, then we have found a situation where we can get fairly strong statistical evidence that the multiplication by y' constituted a quasi-squaring that did not "wrap around." In other words, I'm asserting, without proof right now, that y' will be "much more frequently" equal to x^j when j is close to 2 when y' is small.
> >
> > -Philip White
> Btw, when working with a number like 0.85, you might have to track the fractional power to see if it will lead to wrap-around. Sometimes it will, sometimes it won't; if you can feed known quantities into the DL black box, you can keep track of both the "unmasked value" and the "masked value," as with y', even when the number is subject to manipulations based on properties of logs.

To explain a little more clearly: We have some "masked values" that need to be understood better, particularly the starting x value. We can "mask" some values that we already know, leading us to be able to "unmask" values based on manipulations of this easily. The key is, if we can take the masked x value and, instead of squaring it, raise to a "well-behaved" power like 1.99, we can understand that the squaring translates, in the masked version, to multiplying by 2, so if we have the .99 value well-understood and "unmasked," we can check the masked value to see if it is close to the known x^2 value; the belief is, the value that is "positive and close to 0" modulo the modulus will be closer to x^2 most of the time, when conditions are held to be right.

I think that should be enough for people to figure out how to do the solution.

-Philip White

Re: How to solve DLP (without solving MSR):

<06b9770d-d45c-464c-a655-0c25cb0c6c2fn@googlegroups.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=36009&group=comp.theory#36009

 copy link   Newsgroups: comp.theory
X-Received: by 2002:a37:af04:0:b0:6b5:e908:b2c7 with SMTP id y4-20020a37af04000000b006b5e908b2c7mr4409146qke.214.1658612807212;
Sat, 23 Jul 2022 14:46:47 -0700 (PDT)
X-Received: by 2002:a25:4157:0:b0:670:f3aa:dd9d with SMTP id
o84-20020a254157000000b00670f3aadd9dmr4943304yba.454.1658612806925; Sat, 23
Jul 2022 14:46:46 -0700 (PDT)
Path: i2pn2.org!i2pn.org!usenet.blueworldhosting.com!feed1.usenet.blueworldhosting.com!peer02.iad!feed-me.highwinds-media.com!news.highwinds-media.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.theory
Date: Sat, 23 Jul 2022 14:46:46 -0700 (PDT)
In-Reply-To: <4767ceee-04e0-4fe7-abd3-33c96034818cn@googlegroups.com>
Injection-Info: google-groups.googlegroups.com; posting-host=173.53.104.152; posting-account=X_pe-goAAACrVTtZeoCLt7hslVPY2-Uo
NNTP-Posting-Host: 173.53.104.152
References: <66d931e6-e868-454c-a62c-5e51250f4e41n@googlegroups.com>
<a17b33da-b782-42fa-9ee6-9ec144021da4n@googlegroups.com> <80ed1143-b11d-4dcc-a31a-b34b94ec300bn@googlegroups.com>
<03a05bd0-98be-41b9-b6ee-b6bb3d74a46an@googlegroups.com> <d619a9dc-d05f-42a3-9bbd-0c4e07251e80n@googlegroups.com>
<b507f19a-ec52-471b-95b2-fdd4ecbf13d1n@googlegroups.com> <4767ceee-04e0-4fe7-abd3-33c96034818cn@googlegroups.com>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <06b9770d-d45c-464c-a655-0c25cb0c6c2fn@googlegroups.com>
Subject: Re: How to solve DLP (without solving MSR):
From: xlt....@gmail.com (B.H.)
Injection-Date: Sat, 23 Jul 2022 21:46:47 +0000
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
X-Received-Bytes: 8917
 by: B.H. - Sat, 23 Jul 2022 21:46 UTC

On Saturday, July 23, 2022 at 12:53:43 PM UTC-4, B.H. wrote:
> On Saturday, July 23, 2022 at 11:08:22 AM UTC-4, B.H. wrote:
> > On Saturday, July 23, 2022 at 12:35:09 AM UTC-4, B.H. wrote:
> > > On Friday, July 22, 2022 at 11:45:52 PM UTC-4, B.H. wrote:
> > > > On Friday, July 22, 2022 at 11:30:11 PM UTC-4, B.H. wrote:
> > > > > On Friday, July 22, 2022 at 11:26:29 PM UTC-4, B.H. wrote:
> > > > > > On Friday, July 22, 2022 at 10:55:30 PM UTC-4, B.H. wrote:
> > > > > > > Hi everyone,
> > > > > > >
> > > > > > > Here is the solution.
> > > > > > >
> > > > > > > You can find one solution to a DL instance by using "binary construction." Let's say it's a safe prime modulus. (I first devised this part of the approach in 2007.) Then use Euler's criterion to identify the last bit of the DL. Then, use properties of logs to "subtract one" from the DL.. Now you need to take the sqrt to divide by 2, then repeat this process to find a working DL.
> > > > > > >
> > > > > > > That is what I had in 2007. Today, I realized: Since the sqrt cannot be identified to be "the large one" or "the small one," you need a test. The test is, raise both powers to numbers close to 2. You need a rational number with a denominator that works given the modulus p and phi(p). Raise your two candidate sqrts to different powers like 1.99, except with appropriate denominators that work for the modular division, and test the frequency of the results being large or small. Typically, the smaller value, when squared, will be closer to the value that is the value squared, since (-x)^1.99 vs. x^1.99 is such that the latter is more likely to be "positive" and thus close to the same value as before (for x^2) and not thrown around the modulus value, although of course we're including an unpredictable factor, (x^(1.99))^(2/1.99). (The modular division might come up in an unexpected way.)
> > > > > > >
> > > > > > > I haven't proved that this works but it looks like it should work intuitively. Let me know if it doesn't work right and you want me to try again; I refuse to publish my DL result that solves MSR.
> > > > > > >
> > > > > > > -Philip White (philip...@yahoo.com)
> > > > > > The key to raising something to (2/1.99) or something is, you can use modular division to calc 2/1.99, and then if it's x to that power, you can treat it as multiplying by x to that power minus one, and you can calculate out what that is. So it is not that all that unpredictable. Basically you want to track how different -x and x raised to 1.99 are; you have to see if the .99 turned up odd or even in the modular division, to see if the negative sign will get canceled out, which it sometimes will and sometimes won't.
> > > > > >
> > > > > > If you have access to a number-theory-literate programmer, you should be able to get this and code it within a few hours...I don't have a proof but don't see why it wouldn't work.
> > > > > >
> > > > > > -Philip White (philip...@yahoo.com)
> > > > > Basically, when x^(1.99) and (-x)^(1.99) come up different (half the time?), you have to look at (x^1.99)^(2/1.99) and see which value is the positive x value, based on the multiplication that should check out in the latter expression, because x is positive there.
> > > > >
> > > > > -Philip White
> > > > The goal, again, is to find the x value that is linked to the DL that is closer to 0. The smaller x will be the one that, when multiplied by the "the multiplication" (where you replace the exponent with the multiplication), clearly comes out to something that is true even in non-modular terms, e.g., if you multiply something small by something big, if you don't wrap around, you should see that it is the same as a non-modular multiplication.
> > > >
> > > > I am not writing extremely clearly, I am tossing out notes to help programmers. I'll look at what I've written again tomorrow morning, but the idea seems good.
> > > >
> > > > -Philip
> > > The way I wrote it, it doesn't quite work, but I can fix it.
> > >
> > > The idea is, we need the "small DL" to behave in a certain predictable way. So we start with an "unmasked number y," and compute the modular exponentiation of it; now, we know what the value of y is, and can manipulate it with properties of logarithms. Using such properties, we manipulate y to be such that it is close to some value that is like x^0.99, where we let 0..99 differ from that precise value a little bit, and decide on what it is by equating it to y'. E.g., based on our knowledge of y, we could set x^0.85 = y' (where we also know the manipulated value y'), and then do x*x^0.85 = x^1.85 = x*y'.
> > >
> > > So once we have that, we can "try different values" that are close to 2 like 1.85 and see, based on our ability to know the value of y', if x^1.85 (for whatever value) represented a "big increase." In particular, if we can get y' to be small in some cases when we try repeatedly, then we have found a situation where we can get fairly strong statistical evidence that the multiplication by y' constituted a quasi-squaring that did not "wrap around." In other words, I'm asserting, without proof right now, that y' will be "much more frequently" equal to x^j when j is close to 2 when y' is small.
> > >
> > > -Philip White
> > Btw, when working with a number like 0.85, you might have to track the fractional power to see if it will lead to wrap-around. Sometimes it will, sometimes it won't; if you can feed known quantities into the DL black box, you can keep track of both the "unmasked value" and the "masked value," as with y', even when the number is subject to manipulations based on properties of logs.
> To explain a little more clearly: We have some "masked values" that need to be understood better, particularly the starting x value. We can "mask" some values that we already know, leading us to be able to "unmask" values based on manipulations of this easily. The key is, if we can take the masked x value and, instead of squaring it, raise to a "well-behaved" power like 1.99, we can understand that the squaring translates, in the masked version, to multiplying by 2, so if we have the .99 value well-understood and "unmasked," we can check the masked value to see if it is close to the known x^2 value; the belief is, the value that is "positive and close to 0" modulo the modulus will be closer to x^2 most of the time, when conditions are held to be right.
>
> I think that should be enough for people to figure out how to do the solution.
>
> -Philip White

One more thing...you can modify the value x or -x, adding or subtracting 1, with Euler's criterion, within the mask. That way, you can avoid that it's just "times -1" and therefore equidistant from x^2, since -1 to the whatever is either or -1.

I'll review it again and see if it works and post an update if I need to; I don't feel too motivated to do more math for you, none of you can do it yourselves, and I don't owe anyone a finished product for anything, obviously..

-Philip White

Re: How to solve DLP (without solving MSR):

<c87e4df0-627d-4cae-b075-19279c871d95n@googlegroups.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=36010&group=comp.theory#36010

 copy link   Newsgroups: comp.theory
X-Received: by 2002:a05:622a:5d2:b0:31f:229d:441d with SMTP id d18-20020a05622a05d200b0031f229d441dmr5240551qtb.277.1658612879329;
Sat, 23 Jul 2022 14:47:59 -0700 (PDT)
X-Received: by 2002:a25:30c4:0:b0:670:9351:324f with SMTP id
w187-20020a2530c4000000b006709351324fmr4736528ybw.537.1658612879020; Sat, 23
Jul 2022 14:47:59 -0700 (PDT)
Path: i2pn2.org!i2pn.org!usenet.blueworldhosting.com!feed1.usenet.blueworldhosting.com!peer02.iad!feed-me.highwinds-media.com!news.highwinds-media.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.theory
Date: Sat, 23 Jul 2022 14:47:58 -0700 (PDT)
In-Reply-To: <06b9770d-d45c-464c-a655-0c25cb0c6c2fn@googlegroups.com>
Injection-Info: google-groups.googlegroups.com; posting-host=173.53.104.152; posting-account=X_pe-goAAACrVTtZeoCLt7hslVPY2-Uo
NNTP-Posting-Host: 173.53.104.152
References: <66d931e6-e868-454c-a62c-5e51250f4e41n@googlegroups.com>
<a17b33da-b782-42fa-9ee6-9ec144021da4n@googlegroups.com> <80ed1143-b11d-4dcc-a31a-b34b94ec300bn@googlegroups.com>
<03a05bd0-98be-41b9-b6ee-b6bb3d74a46an@googlegroups.com> <d619a9dc-d05f-42a3-9bbd-0c4e07251e80n@googlegroups.com>
<b507f19a-ec52-471b-95b2-fdd4ecbf13d1n@googlegroups.com> <4767ceee-04e0-4fe7-abd3-33c96034818cn@googlegroups.com>
<06b9770d-d45c-464c-a655-0c25cb0c6c2fn@googlegroups.com>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <c87e4df0-627d-4cae-b075-19279c871d95n@googlegroups.com>
Subject: Re: How to solve DLP (without solving MSR):
From: xlt....@gmail.com (B.H.)
Injection-Date: Sat, 23 Jul 2022 21:47:59 +0000
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
X-Received-Bytes: 9259
 by: B.H. - Sat, 23 Jul 2022 21:47 UTC

On Saturday, July 23, 2022 at 5:46:48 PM UTC-4, B.H. wrote:
> On Saturday, July 23, 2022 at 12:53:43 PM UTC-4, B.H. wrote:
> > On Saturday, July 23, 2022 at 11:08:22 AM UTC-4, B.H. wrote:
> > > On Saturday, July 23, 2022 at 12:35:09 AM UTC-4, B.H. wrote:
> > > > On Friday, July 22, 2022 at 11:45:52 PM UTC-4, B.H. wrote:
> > > > > On Friday, July 22, 2022 at 11:30:11 PM UTC-4, B.H. wrote:
> > > > > > On Friday, July 22, 2022 at 11:26:29 PM UTC-4, B.H. wrote:
> > > > > > > On Friday, July 22, 2022 at 10:55:30 PM UTC-4, B.H. wrote:
> > > > > > > > Hi everyone,
> > > > > > > >
> > > > > > > > Here is the solution.
> > > > > > > >
> > > > > > > > You can find one solution to a DL instance by using "binary construction." Let's say it's a safe prime modulus. (I first devised this part of the approach in 2007.) Then use Euler's criterion to identify the last bit of the DL. Then, use properties of logs to "subtract one" from the DL. Now you need to take the sqrt to divide by 2, then repeat this process to find a working DL.
> > > > > > > >
> > > > > > > > That is what I had in 2007. Today, I realized: Since the sqrt cannot be identified to be "the large one" or "the small one," you need a test. The test is, raise both powers to numbers close to 2. You need a rational number with a denominator that works given the modulus p and phi(p). Raise your two candidate sqrts to different powers like 1.99, except with appropriate denominators that work for the modular division, and test the frequency of the results being large or small. Typically, the smaller value, when squared, will be closer to the value that is the value squared, since (-x)^1.99 vs. x^1.99 is such that the latter is more likely to be "positive" and thus close to the same value as before (for x^2) and not thrown around the modulus value, although of course we're including an unpredictable factor, (x^(1.99))^(2/1.99). (The modular division might come up in an unexpected way.)
> > > > > > > >
> > > > > > > > I haven't proved that this works but it looks like it should work intuitively. Let me know if it doesn't work right and you want me to try again; I refuse to publish my DL result that solves MSR.
> > > > > > > >
> > > > > > > > -Philip White (philip...@yahoo.com)
> > > > > > > The key to raising something to (2/1.99) or something is, you can use modular division to calc 2/1.99, and then if it's x to that power, you can treat it as multiplying by x to that power minus one, and you can calculate out what that is. So it is not that all that unpredictable. Basically you want to track how different -x and x raised to 1.99 are; you have to see if the .99 turned up odd or even in the modular division, to see if the negative sign will get canceled out, which it sometimes will and sometimes won't.
> > > > > > >
> > > > > > > If you have access to a number-theory-literate programmer, you should be able to get this and code it within a few hours...I don't have a proof but don't see why it wouldn't work.
> > > > > > >
> > > > > > > -Philip White (philip...@yahoo.com)
> > > > > > Basically, when x^(1.99) and (-x)^(1.99) come up different (half the time?), you have to look at (x^1.99)^(2/1.99) and see which value is the positive x value, based on the multiplication that should check out in the latter expression, because x is positive there.
> > > > > >
> > > > > > -Philip White
> > > > > The goal, again, is to find the x value that is linked to the DL that is closer to 0. The smaller x will be the one that, when multiplied by the "the multiplication" (where you replace the exponent with the multiplication), clearly comes out to something that is true even in non-modular terms, e.g., if you multiply something small by something big, if you don't wrap around, you should see that it is the same as a non-modular multiplication.
> > > > >
> > > > > I am not writing extremely clearly, I am tossing out notes to help programmers. I'll look at what I've written again tomorrow morning, but the idea seems good.
> > > > >
> > > > > -Philip
> > > > The way I wrote it, it doesn't quite work, but I can fix it.
> > > >
> > > > The idea is, we need the "small DL" to behave in a certain predictable way. So we start with an "unmasked number y," and compute the modular exponentiation of it; now, we know what the value of y is, and can manipulate it with properties of logarithms. Using such properties, we manipulate y to be such that it is close to some value that is like x^0.99, where we let 0.99 differ from that precise value a little bit, and decide on what it is by equating it to y'. E.g., based on our knowledge of y, we could set x^0.85 = y' (where we also know the manipulated value y'), and then do x*x^0.85 = x^1.85 = x*y'.
> > > >
> > > > So once we have that, we can "try different values" that are close to 2 like 1.85 and see, based on our ability to know the value of y', if x^1.85 (for whatever value) represented a "big increase." In particular, if we can get y' to be small in some cases when we try repeatedly, then we have found a situation where we can get fairly strong statistical evidence that the multiplication by y' constituted a quasi-squaring that did not "wrap around." In other words, I'm asserting, without proof right now, that y' will be "much more frequently" equal to x^j when j is close to 2 when y' is small.
> > > >
> > > > -Philip White
> > > Btw, when working with a number like 0.85, you might have to track the fractional power to see if it will lead to wrap-around. Sometimes it will, sometimes it won't; if you can feed known quantities into the DL black box, you can keep track of both the "unmasked value" and the "masked value," as with y', even when the number is subject to manipulations based on properties of logs.
> > To explain a little more clearly: We have some "masked values" that need to be understood better, particularly the starting x value. We can "mask" some values that we already know, leading us to be able to "unmask" values based on manipulations of this easily. The key is, if we can take the masked x value and, instead of squaring it, raise to a "well-behaved" power like 1.99, we can understand that the squaring translates, in the masked version, to multiplying by 2, so if we have the .99 value well-understood and "unmasked," we can check the masked value to see if it is close to the known x^2 value; the belief is, the value that is "positive and close to 0" modulo the modulus will be closer to x^2 most of the time, when conditions are held to be right.
> >
> > I think that should be enough for people to figure out how to do the solution.
> >
> > -Philip White
> One more thing...you can modify the value x or -x, adding or subtracting 1, with Euler's criterion, within the mask. That way, you can avoid that it's just "times -1" and therefore equidistant from x^2, since -1 to the whatever is either or -1.
>
> I'll review it again and see if it works and post an update if I need to; I don't feel too motivated to do more math for you, none of you can do it yourselves, and I don't owe anyone a finished product for anything, obviously.
>
> -Philip White

And of course there will be retracing of steps when dealing with the masked values...that is no big deal.

Re: How to solve DLP (without solving MSR):

<e728f101-8ff9-4079-8774-6332bfb38118n@googlegroups.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=36030&group=comp.theory#36030

 copy link   Newsgroups: comp.theory
X-Received: by 2002:a05:622a:47:b0:31f:3320:6956 with SMTP id y7-20020a05622a004700b0031f33206956mr2199273qtw.350.1658618962800;
Sat, 23 Jul 2022 16:29:22 -0700 (PDT)
X-Received: by 2002:a05:6902:723:b0:670:b2a7:b267 with SMTP id
l3-20020a056902072300b00670b2a7b267mr4929992ybt.345.1658618962489; Sat, 23
Jul 2022 16:29:22 -0700 (PDT)
Path: i2pn2.org!i2pn.org!usenet.blueworldhosting.com!feed1.usenet.blueworldhosting.com!peer01.iad!feed-me.highwinds-media.com!news.highwinds-media.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.theory
Date: Sat, 23 Jul 2022 16:29:22 -0700 (PDT)
In-Reply-To: <c87e4df0-627d-4cae-b075-19279c871d95n@googlegroups.com>
Injection-Info: google-groups.googlegroups.com; posting-host=173.53.104.152; posting-account=X_pe-goAAACrVTtZeoCLt7hslVPY2-Uo
NNTP-Posting-Host: 173.53.104.152
References: <66d931e6-e868-454c-a62c-5e51250f4e41n@googlegroups.com>
<a17b33da-b782-42fa-9ee6-9ec144021da4n@googlegroups.com> <80ed1143-b11d-4dcc-a31a-b34b94ec300bn@googlegroups.com>
<03a05bd0-98be-41b9-b6ee-b6bb3d74a46an@googlegroups.com> <d619a9dc-d05f-42a3-9bbd-0c4e07251e80n@googlegroups.com>
<b507f19a-ec52-471b-95b2-fdd4ecbf13d1n@googlegroups.com> <4767ceee-04e0-4fe7-abd3-33c96034818cn@googlegroups.com>
<06b9770d-d45c-464c-a655-0c25cb0c6c2fn@googlegroups.com> <c87e4df0-627d-4cae-b075-19279c871d95n@googlegroups.com>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <e728f101-8ff9-4079-8774-6332bfb38118n@googlegroups.com>
Subject: Re: How to solve DLP (without solving MSR):
From: xlt....@gmail.com (B.H.)
Injection-Date: Sat, 23 Jul 2022 23:29:22 +0000
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
X-Received-Bytes: 10619
 by: B.H. - Sat, 23 Jul 2022 23:29 UTC

On Saturday, July 23, 2022 at 5:48:00 PM UTC-4, B.H. wrote:
> On Saturday, July 23, 2022 at 5:46:48 PM UTC-4, B.H. wrote:
> > On Saturday, July 23, 2022 at 12:53:43 PM UTC-4, B.H. wrote:
> > > On Saturday, July 23, 2022 at 11:08:22 AM UTC-4, B.H. wrote:
> > > > On Saturday, July 23, 2022 at 12:35:09 AM UTC-4, B.H. wrote:
> > > > > On Friday, July 22, 2022 at 11:45:52 PM UTC-4, B.H. wrote:
> > > > > > On Friday, July 22, 2022 at 11:30:11 PM UTC-4, B.H. wrote:
> > > > > > > On Friday, July 22, 2022 at 11:26:29 PM UTC-4, B.H. wrote:
> > > > > > > > On Friday, July 22, 2022 at 10:55:30 PM UTC-4, B.H. wrote:
> > > > > > > > > Hi everyone,
> > > > > > > > >
> > > > > > > > > Here is the solution.
> > > > > > > > >
> > > > > > > > > You can find one solution to a DL instance by using "binary construction." Let's say it's a safe prime modulus. (I first devised this part of the approach in 2007.) Then use Euler's criterion to identify the last bit of the DL. Then, use properties of logs to "subtract one" from the DL. Now you need to take the sqrt to divide by 2, then repeat this process to find a working DL.
> > > > > > > > >
> > > > > > > > > That is what I had in 2007. Today, I realized: Since the sqrt cannot be identified to be "the large one" or "the small one," you need a test. The test is, raise both powers to numbers close to 2. You need a rational number with a denominator that works given the modulus p and phi(p). Raise your two candidate sqrts to different powers like 1.99, except with appropriate denominators that work for the modular division, and test the frequency of the results being large or small. Typically, the smaller value, when squared, will be closer to the value that is the value squared, since (-x)^1.99 vs. x^1.99 is such that the latter is more likely to be "positive" and thus close to the same value as before (for x^2) and not thrown around the modulus value, although of course we're including an unpredictable factor, (x^(1.99))^(2/1.99). (The modular division might come up in an unexpected way.)
> > > > > > > > >
> > > > > > > > > I haven't proved that this works but it looks like it should work intuitively. Let me know if it doesn't work right and you want me to try again; I refuse to publish my DL result that solves MSR.
> > > > > > > > >
> > > > > > > > > -Philip White (philip...@yahoo.com)
> > > > > > > > The key to raising something to (2/1.99) or something is, you can use modular division to calc 2/1.99, and then if it's x to that power, you can treat it as multiplying by x to that power minus one, and you can calculate out what that is. So it is not that all that unpredictable. Basically you want to track how different -x and x raised to 1.99 are; you have to see if the .99 turned up odd or even in the modular division, to see if the negative sign will get canceled out, which it sometimes will and sometimes won't.
> > > > > > > >
> > > > > > > > If you have access to a number-theory-literate programmer, you should be able to get this and code it within a few hours...I don't have a proof but don't see why it wouldn't work.
> > > > > > > >
> > > > > > > > -Philip White (philip...@yahoo.com)
> > > > > > > Basically, when x^(1.99) and (-x)^(1.99) come up different (half the time?), you have to look at (x^1.99)^(2/1.99) and see which value is the positive x value, based on the multiplication that should check out in the latter expression, because x is positive there.
> > > > > > >
> > > > > > > -Philip White
> > > > > > The goal, again, is to find the x value that is linked to the DL that is closer to 0. The smaller x will be the one that, when multiplied by the "the multiplication" (where you replace the exponent with the multiplication), clearly comes out to something that is true even in non-modular terms, e.g., if you multiply something small by something big, if you don't wrap around, you should see that it is the same as a non-modular multiplication.
> > > > > >
> > > > > > I am not writing extremely clearly, I am tossing out notes to help programmers. I'll look at what I've written again tomorrow morning, but the idea seems good.
> > > > > >
> > > > > > -Philip
> > > > > The way I wrote it, it doesn't quite work, but I can fix it.
> > > > >
> > > > > The idea is, we need the "small DL" to behave in a certain predictable way. So we start with an "unmasked number y," and compute the modular exponentiation of it; now, we know what the value of y is, and can manipulate it with properties of logarithms. Using such properties, we manipulate y to be such that it is close to some value that is like x^0.99, where we let 0.99 differ from that precise value a little bit, and decide on what it is by equating it to y'. E.g., based on our knowledge of y, we could set x^0.85 = y' (where we also know the manipulated value y'), and then do x*x^0.85 = x^1.85 = x*y'.
> > > > >
> > > > > So once we have that, we can "try different values" that are close to 2 like 1.85 and see, based on our ability to know the value of y', if x^1.85 (for whatever value) represented a "big increase." In particular, if we can get y' to be small in some cases when we try repeatedly, then we have found a situation where we can get fairly strong statistical evidence that the multiplication by y' constituted a quasi-squaring that did not "wrap around." In other words, I'm asserting, without proof right now, that y' will be "much more frequently" equal to x^j when j is close to 2 when y' is small.
> > > > >
> > > > > -Philip White
> > > > Btw, when working with a number like 0.85, you might have to track the fractional power to see if it will lead to wrap-around. Sometimes it will, sometimes it won't; if you can feed known quantities into the DL black box, you can keep track of both the "unmasked value" and the "masked value," as with y', even when the number is subject to manipulations based on properties of logs.
> > > To explain a little more clearly: We have some "masked values" that need to be understood better, particularly the starting x value. We can "mask" some values that we already know, leading us to be able to "unmask" values based on manipulations of this easily. The key is, if we can take the masked x value and, instead of squaring it, raise to a "well-behaved" power like 1.99, we can understand that the squaring translates, in the masked version, to multiplying by 2, so if we have the .99 value well-understood and "unmasked," we can check the masked value to see if it is close to the known x^2 value; the belief is, the value that is "positive and close to 0" modulo the modulus will be closer to x^2 most of the time, when conditions are held to be right.
> > >
> > > I think that should be enough for people to figure out how to do the solution.
> > >
> > > -Philip White
> > One more thing...you can modify the value x or -x, adding or subtracting 1, with Euler's criterion, within the mask. That way, you can avoid that it's just "times -1" and therefore equidistant from x^2, since -1 to the whatever is either or -1.
> >
> > I'll review it again and see if it works and post an update if I need to; I don't feel too motivated to do more math for you, none of you can do it yourselves, and I don't owe anyone a finished product for anything, obviously.
> >
> > -Philip White
> And of course there will be retracing of steps when dealing with the masked values...that is no big deal.

One more clarifying thing on this, which is the right version:

You don't have to use 1.99, you could use 3. The key is, as it turns out, the Euler's criterion shift allows you to measure if the (let's say) "increase by 1" was, in terms of squaring +/- modulo the modulus, truly an increase to the value of |x|, or whether it was really subtracting from the "magnitude" (distance from 0) of a negative number. When you raise to a power other than 2, you perform a multiplication that can be checked to see if it is close to the original x^2 value. If, e.g., we added 1 to the "positive" (small) x value, then this "unmasked multiplication" will yield a value that is further from the x^2 value, which is not true if we were to add 1 to the "negative" (large) x value. Think of: 2x vs. 3x+3, and 2*(-x) vs. 3*(-x)-3. The differences are x+3 and -x-3. Those two values should come out different.

In contrast to my previous posts, I'm having a little trouble thinking about this very clearly. It doesn't matter though; my health is on the mend, I can say whatever I want.


Click here to read the complete article
Re: How to solve DLP (without solving MSR):

<7d0caef8-13a3-4f3d-8f95-3a77cf53db2dn@googlegroups.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=36031&group=comp.theory#36031

 copy link   Newsgroups: comp.theory
X-Received: by 2002:ad4:4ea2:0:b0:473:6d91:6759 with SMTP id ed2-20020ad44ea2000000b004736d916759mr5647833qvb.102.1658619006726;
Sat, 23 Jul 2022 16:30:06 -0700 (PDT)
X-Received: by 2002:a0d:d496:0:b0:31b:cd60:d9e4 with SMTP id
w144-20020a0dd496000000b0031bcd60d9e4mr5401151ywd.454.1658619006412; Sat, 23
Jul 2022 16:30:06 -0700 (PDT)
Path: i2pn2.org!i2pn.org!usenet.blueworldhosting.com!feed1.usenet.blueworldhosting.com!peer01.iad!feed-me.highwinds-media.com!news.highwinds-media.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.theory
Date: Sat, 23 Jul 2022 16:30:06 -0700 (PDT)
In-Reply-To: <e728f101-8ff9-4079-8774-6332bfb38118n@googlegroups.com>
Injection-Info: google-groups.googlegroups.com; posting-host=173.53.104.152; posting-account=X_pe-goAAACrVTtZeoCLt7hslVPY2-Uo
NNTP-Posting-Host: 173.53.104.152
References: <66d931e6-e868-454c-a62c-5e51250f4e41n@googlegroups.com>
<a17b33da-b782-42fa-9ee6-9ec144021da4n@googlegroups.com> <80ed1143-b11d-4dcc-a31a-b34b94ec300bn@googlegroups.com>
<03a05bd0-98be-41b9-b6ee-b6bb3d74a46an@googlegroups.com> <d619a9dc-d05f-42a3-9bbd-0c4e07251e80n@googlegroups.com>
<b507f19a-ec52-471b-95b2-fdd4ecbf13d1n@googlegroups.com> <4767ceee-04e0-4fe7-abd3-33c96034818cn@googlegroups.com>
<06b9770d-d45c-464c-a655-0c25cb0c6c2fn@googlegroups.com> <c87e4df0-627d-4cae-b075-19279c871d95n@googlegroups.com>
<e728f101-8ff9-4079-8774-6332bfb38118n@googlegroups.com>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <7d0caef8-13a3-4f3d-8f95-3a77cf53db2dn@googlegroups.com>
Subject: Re: How to solve DLP (without solving MSR):
From: xlt....@gmail.com (B.H.)
Injection-Date: Sat, 23 Jul 2022 23:30:06 +0000
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
X-Received-Bytes: 10999
 by: B.H. - Sat, 23 Jul 2022 23:30 UTC

On Saturday, July 23, 2022 at 7:29:24 PM UTC-4, B.H. wrote:
> On Saturday, July 23, 2022 at 5:48:00 PM UTC-4, B.H. wrote:
> > On Saturday, July 23, 2022 at 5:46:48 PM UTC-4, B.H. wrote:
> > > On Saturday, July 23, 2022 at 12:53:43 PM UTC-4, B.H. wrote:
> > > > On Saturday, July 23, 2022 at 11:08:22 AM UTC-4, B.H. wrote:
> > > > > On Saturday, July 23, 2022 at 12:35:09 AM UTC-4, B.H. wrote:
> > > > > > On Friday, July 22, 2022 at 11:45:52 PM UTC-4, B.H. wrote:
> > > > > > > On Friday, July 22, 2022 at 11:30:11 PM UTC-4, B.H. wrote:
> > > > > > > > On Friday, July 22, 2022 at 11:26:29 PM UTC-4, B.H. wrote:
> > > > > > > > > On Friday, July 22, 2022 at 10:55:30 PM UTC-4, B.H. wrote:
> > > > > > > > > > Hi everyone,
> > > > > > > > > >
> > > > > > > > > > Here is the solution.
> > > > > > > > > >
> > > > > > > > > > You can find one solution to a DL instance by using "binary construction." Let's say it's a safe prime modulus. (I first devised this part of the approach in 2007.) Then use Euler's criterion to identify the last bit of the DL. Then, use properties of logs to "subtract one" from the DL. Now you need to take the sqrt to divide by 2, then repeat this process to find a working DL.
> > > > > > > > > >
> > > > > > > > > > That is what I had in 2007. Today, I realized: Since the sqrt cannot be identified to be "the large one" or "the small one," you need a test. The test is, raise both powers to numbers close to 2. You need a rational number with a denominator that works given the modulus p and phi(p). Raise your two candidate sqrts to different powers like 1.99, except with appropriate denominators that work for the modular division, and test the frequency of the results being large or small. Typically, the smaller value, when squared, will be closer to the value that is the value squared, since (-x)^1.99 vs. x^1.99 is such that the latter is more likely to be "positive" and thus close to the same value as before (for x^2) and not thrown around the modulus value, although of course we're including an unpredictable factor, (x^(1.99))^(2/1.99). (The modular division might come up in an unexpected way.)
> > > > > > > > > >
> > > > > > > > > > I haven't proved that this works but it looks like it should work intuitively. Let me know if it doesn't work right and you want me to try again; I refuse to publish my DL result that solves MSR.
> > > > > > > > > >
> > > > > > > > > > -Philip White (philip...@yahoo.com)
> > > > > > > > > The key to raising something to (2/1.99) or something is, you can use modular division to calc 2/1.99, and then if it's x to that power, you can treat it as multiplying by x to that power minus one, and you can calculate out what that is. So it is not that all that unpredictable. Basically you want to track how different -x and x raised to 1.99 are; you have to see if the .99 turned up odd or even in the modular division, to see if the negative sign will get canceled out, which it sometimes will and sometimes won't.
> > > > > > > > >
> > > > > > > > > If you have access to a number-theory-literate programmer, you should be able to get this and code it within a few hours...I don't have a proof but don't see why it wouldn't work.
> > > > > > > > >
> > > > > > > > > -Philip White (philip...@yahoo.com)
> > > > > > > > Basically, when x^(1.99) and (-x)^(1.99) come up different (half the time?), you have to look at (x^1.99)^(2/1.99) and see which value is the positive x value, based on the multiplication that should check out in the latter expression, because x is positive there.
> > > > > > > >
> > > > > > > > -Philip White
> > > > > > > The goal, again, is to find the x value that is linked to the DL that is closer to 0. The smaller x will be the one that, when multiplied by the "the multiplication" (where you replace the exponent with the multiplication), clearly comes out to something that is true even in non-modular terms, e.g., if you multiply something small by something big, if you don't wrap around, you should see that it is the same as a non-modular multiplication.
> > > > > > >
> > > > > > > I am not writing extremely clearly, I am tossing out notes to help programmers. I'll look at what I've written again tomorrow morning, but the idea seems good.
> > > > > > >
> > > > > > > -Philip
> > > > > > The way I wrote it, it doesn't quite work, but I can fix it.
> > > > > >
> > > > > > The idea is, we need the "small DL" to behave in a certain predictable way. So we start with an "unmasked number y," and compute the modular exponentiation of it; now, we know what the value of y is, and can manipulate it with properties of logarithms. Using such properties, we manipulate y to be such that it is close to some value that is like x^0.99, where we let 0.99 differ from that precise value a little bit, and decide on what it is by equating it to y'. E.g., based on our knowledge of y, we could set x^0.85 = y' (where we also know the manipulated value y'), and then do x*x^0.85 = x^1.85 = x*y'.
> > > > > >
> > > > > > So once we have that, we can "try different values" that are close to 2 like 1.85 and see, based on our ability to know the value of y', if x^1.85 (for whatever value) represented a "big increase." In particular, if we can get y' to be small in some cases when we try repeatedly, then we have found a situation where we can get fairly strong statistical evidence that the multiplication by y' constituted a quasi-squaring that did not "wrap around." In other words, I'm asserting, without proof right now, that y' will be "much more frequently" equal to x^j when j is close to 2 when y' is small.
> > > > > >
> > > > > > -Philip White
> > > > > Btw, when working with a number like 0.85, you might have to track the fractional power to see if it will lead to wrap-around. Sometimes it will, sometimes it won't; if you can feed known quantities into the DL black box, you can keep track of both the "unmasked value" and the "masked value," as with y', even when the number is subject to manipulations based on properties of logs.
> > > > To explain a little more clearly: We have some "masked values" that need to be understood better, particularly the starting x value. We can "mask" some values that we already know, leading us to be able to "unmask" values based on manipulations of this easily. The key is, if we can take the masked x value and, instead of squaring it, raise to a "well-behaved" power like 1.99, we can understand that the squaring translates, in the masked version, to multiplying by 2, so if we have the .99 value well-understood and "unmasked," we can check the masked value to see if it is close to the known x^2 value; the belief is, the value that is "positive and close to 0" modulo the modulus will be closer to x^2 most of the time, when conditions are held to be right.
> > > >
> > > > I think that should be enough for people to figure out how to do the solution.
> > > >
> > > > -Philip White
> > > One more thing...you can modify the value x or -x, adding or subtracting 1, with Euler's criterion, within the mask. That way, you can avoid that it's just "times -1" and therefore equidistant from x^2, since -1 to the whatever is either or -1.
> > >
> > > I'll review it again and see if it works and post an update if I need to; I don't feel too motivated to do more math for you, none of you can do it yourselves, and I don't owe anyone a finished product for anything, obviously.
> > >
> > > -Philip White
> > And of course there will be retracing of steps when dealing with the masked values...that is no big deal.
> One more clarifying thing on this, which is the right version:
>
> You don't have to use 1.99, you could use 3. The key is, as it turns out, the Euler's criterion shift allows you to measure if the (let's say) "increase by 1" was, in terms of squaring +/- modulo the modulus, truly an increase to the value of |x|, or whether it was really subtracting from the "magnitude" (distance from 0) of a negative number. When you raise to a power other than 2, you perform a multiplication that can be checked to see if it is close to the original x^2 value. If, e.g., we added 1 to the "positive" (small) x value, then this "unmasked multiplication" will yield a value that is further from the x^2 value, which is not true if we were to add 1 to the "negative" (large) x value. Think of: 2x vs. 3x+3, and 2*(-x) vs. 3*(-x)-3. The differences are x+3 and -x-3. Those two values should come out different.
>
> In contrast to my previous posts, I'm having a little trouble thinking about this very clearly. It doesn't matter though; my health is on the mend, I can say whatever I want.
>
> -Philip


Click here to read the complete article
Re: How to solve DLP (without solving MSR):

<c743eeb2-14c2-4b7a-a04d-0d3ead02be16n@googlegroups.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=36033&group=comp.theory#36033

 copy link   Newsgroups: comp.theory
X-Received: by 2002:a05:620a:d83:b0:6a7:a68c:6118 with SMTP id q3-20020a05620a0d8300b006a7a68c6118mr4811592qkl.337.1658619424966;
Sat, 23 Jul 2022 16:37:04 -0700 (PDT)
X-Received: by 2002:a25:25c4:0:b0:670:7f5c:37a0 with SMTP id
l187-20020a2525c4000000b006707f5c37a0mr4833508ybl.52.1658619424675; Sat, 23
Jul 2022 16:37:04 -0700 (PDT)
Path: i2pn2.org!i2pn.org!usenet.blueworldhosting.com!feed1.usenet.blueworldhosting.com!peer01.iad!feed-me.highwinds-media.com!news.highwinds-media.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.theory
Date: Sat, 23 Jul 2022 16:37:04 -0700 (PDT)
In-Reply-To: <7d0caef8-13a3-4f3d-8f95-3a77cf53db2dn@googlegroups.com>
Injection-Info: google-groups.googlegroups.com; posting-host=173.53.104.152; posting-account=X_pe-goAAACrVTtZeoCLt7hslVPY2-Uo
NNTP-Posting-Host: 173.53.104.152
References: <66d931e6-e868-454c-a62c-5e51250f4e41n@googlegroups.com>
<a17b33da-b782-42fa-9ee6-9ec144021da4n@googlegroups.com> <80ed1143-b11d-4dcc-a31a-b34b94ec300bn@googlegroups.com>
<03a05bd0-98be-41b9-b6ee-b6bb3d74a46an@googlegroups.com> <d619a9dc-d05f-42a3-9bbd-0c4e07251e80n@googlegroups.com>
<b507f19a-ec52-471b-95b2-fdd4ecbf13d1n@googlegroups.com> <4767ceee-04e0-4fe7-abd3-33c96034818cn@googlegroups.com>
<06b9770d-d45c-464c-a655-0c25cb0c6c2fn@googlegroups.com> <c87e4df0-627d-4cae-b075-19279c871d95n@googlegroups.com>
<e728f101-8ff9-4079-8774-6332bfb38118n@googlegroups.com> <7d0caef8-13a3-4f3d-8f95-3a77cf53db2dn@googlegroups.com>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <c743eeb2-14c2-4b7a-a04d-0d3ead02be16n@googlegroups.com>
Subject: Re: How to solve DLP (without solving MSR):
From: xlt....@gmail.com (B.H.)
Injection-Date: Sat, 23 Jul 2022 23:37:04 +0000
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
X-Received-Bytes: 11605
 by: B.H. - Sat, 23 Jul 2022 23:37 UTC

On Saturday, July 23, 2022 at 7:30:07 PM UTC-4, B.H. wrote:
> On Saturday, July 23, 2022 at 7:29:24 PM UTC-4, B.H. wrote:
> > On Saturday, July 23, 2022 at 5:48:00 PM UTC-4, B.H. wrote:
> > > On Saturday, July 23, 2022 at 5:46:48 PM UTC-4, B.H. wrote:
> > > > On Saturday, July 23, 2022 at 12:53:43 PM UTC-4, B.H. wrote:
> > > > > On Saturday, July 23, 2022 at 11:08:22 AM UTC-4, B.H. wrote:
> > > > > > On Saturday, July 23, 2022 at 12:35:09 AM UTC-4, B.H. wrote:
> > > > > > > On Friday, July 22, 2022 at 11:45:52 PM UTC-4, B.H. wrote:
> > > > > > > > On Friday, July 22, 2022 at 11:30:11 PM UTC-4, B.H. wrote:
> > > > > > > > > On Friday, July 22, 2022 at 11:26:29 PM UTC-4, B.H. wrote:
> > > > > > > > > > On Friday, July 22, 2022 at 10:55:30 PM UTC-4, B.H. wrote:
> > > > > > > > > > > Hi everyone,
> > > > > > > > > > >
> > > > > > > > > > > Here is the solution.
> > > > > > > > > > >
> > > > > > > > > > > You can find one solution to a DL instance by using "binary construction." Let's say it's a safe prime modulus. (I first devised this part of the approach in 2007.) Then use Euler's criterion to identify the last bit of the DL. Then, use properties of logs to "subtract one" from the DL. Now you need to take the sqrt to divide by 2, then repeat this process to find a working DL.
> > > > > > > > > > >
> > > > > > > > > > > That is what I had in 2007. Today, I realized: Since the sqrt cannot be identified to be "the large one" or "the small one," you need a test. The test is, raise both powers to numbers close to 2. You need a rational number with a denominator that works given the modulus p and phi(p). Raise your two candidate sqrts to different powers like 1.99, except with appropriate denominators that work for the modular division, and test the frequency of the results being large or small. Typically, the smaller value, when squared, will be closer to the value that is the value squared, since (-x)^1.99 vs. x^1.99 is such that the latter is more likely to be "positive" and thus close to the same value as before (for x^2) and not thrown around the modulus value, although of course we're including an unpredictable factor, (x^(1.99))^(2/1.99). (The modular division might come up in an unexpected way.)
> > > > > > > > > > >
> > > > > > > > > > > I haven't proved that this works but it looks like it should work intuitively. Let me know if it doesn't work right and you want me to try again; I refuse to publish my DL result that solves MSR.
> > > > > > > > > > >
> > > > > > > > > > > -Philip White (philip...@yahoo.com)
> > > > > > > > > > The key to raising something to (2/1.99) or something is, you can use modular division to calc 2/1.99, and then if it's x to that power, you can treat it as multiplying by x to that power minus one, and you can calculate out what that is. So it is not that all that unpredictable. Basically you want to track how different -x and x raised to 1.99 are; you have to see if the .99 turned up odd or even in the modular division, to see if the negative sign will get canceled out, which it sometimes will and sometimes won't.
> > > > > > > > > >
> > > > > > > > > > If you have access to a number-theory-literate programmer, you should be able to get this and code it within a few hours...I don't have a proof but don't see why it wouldn't work.
> > > > > > > > > >
> > > > > > > > > > -Philip White (philip...@yahoo.com)
> > > > > > > > > Basically, when x^(1.99) and (-x)^(1.99) come up different (half the time?), you have to look at (x^1.99)^(2/1.99) and see which value is the positive x value, based on the multiplication that should check out in the latter expression, because x is positive there.
> > > > > > > > >
> > > > > > > > > -Philip White
> > > > > > > > The goal, again, is to find the x value that is linked to the DL that is closer to 0. The smaller x will be the one that, when multiplied by the "the multiplication" (where you replace the exponent with the multiplication), clearly comes out to something that is true even in non-modular terms, e.g., if you multiply something small by something big, if you don't wrap around, you should see that it is the same as a non-modular multiplication.
> > > > > > > >
> > > > > > > > I am not writing extremely clearly, I am tossing out notes to help programmers. I'll look at what I've written again tomorrow morning, but the idea seems good.
> > > > > > > >
> > > > > > > > -Philip
> > > > > > > The way I wrote it, it doesn't quite work, but I can fix it.
> > > > > > >
> > > > > > > The idea is, we need the "small DL" to behave in a certain predictable way. So we start with an "unmasked number y," and compute the modular exponentiation of it; now, we know what the value of y is, and can manipulate it with properties of logarithms. Using such properties, we manipulate y to be such that it is close to some value that is like x^0.99, where we let 0.99 differ from that precise value a little bit, and decide on what it is by equating it to y'. E.g., based on our knowledge of y, we could set x^0.85 = y' (where we also know the manipulated value y'), and then do x*x^0.85 = x^1.85 = x*y'.
> > > > > > >
> > > > > > > So once we have that, we can "try different values" that are close to 2 like 1.85 and see, based on our ability to know the value of y', if x^1.85 (for whatever value) represented a "big increase." In particular, if we can get y' to be small in some cases when we try repeatedly, then we have found a situation where we can get fairly strong statistical evidence that the multiplication by y' constituted a quasi-squaring that did not "wrap around." In other words, I'm asserting, without proof right now, that y' will be "much more frequently" equal to x^j when j is close to 2 when y' is small.
> > > > > > >
> > > > > > > -Philip White
> > > > > > Btw, when working with a number like 0.85, you might have to track the fractional power to see if it will lead to wrap-around. Sometimes it will, sometimes it won't; if you can feed known quantities into the DL black box, you can keep track of both the "unmasked value" and the "masked value," as with y', even when the number is subject to manipulations based on properties of logs.
> > > > > To explain a little more clearly: We have some "masked values" that need to be understood better, particularly the starting x value. We can "mask" some values that we already know, leading us to be able to "unmask" values based on manipulations of this easily. The key is, if we can take the masked x value and, instead of squaring it, raise to a "well-behaved" power like 1.99, we can understand that the squaring translates, in the masked version, to multiplying by 2, so if we have the .99 value well-understood and "unmasked," we can check the masked value to see if it is close to the known x^2 value; the belief is, the value that is "positive and close to 0" modulo the modulus will be closer to x^2 most of the time, when conditions are held to be right.
> > > > >
> > > > > I think that should be enough for people to figure out how to do the solution.
> > > > >
> > > > > -Philip White
> > > > One more thing...you can modify the value x or -x, adding or subtracting 1, with Euler's criterion, within the mask. That way, you can avoid that it's just "times -1" and therefore equidistant from x^2, since -1 to the whatever is either or -1.
> > > >
> > > > I'll review it again and see if it works and post an update if I need to; I don't feel too motivated to do more math for you, none of you can do it yourselves, and I don't owe anyone a finished product for anything, obviously.
> > > >
> > > > -Philip White
> > > And of course there will be retracing of steps when dealing with the masked values...that is no big deal.
> > One more clarifying thing on this, which is the right version:
> >
> > You don't have to use 1.99, you could use 3. The key is, as it turns out, the Euler's criterion shift allows you to measure if the (let's say) "increase by 1" was, in terms of squaring +/- modulo the modulus, truly an increase to the value of |x|, or whether it was really subtracting from the "magnitude" (distance from 0) of a negative number. When you raise to a power other than 2, you perform a multiplication that can be checked to see if it is close to the original x^2 value. If, e.g., we added 1 to the "positive" (small) x value, then this "unmasked multiplication" will yield a value that is further from the x^2 value, which is not true if we were to add 1 to the "negative" (large) x value. Think of: 2x vs. 3x+3, and 2*(-x) vs. 3*(-x)-3. The differences are x+3 and -x-3. Those two values should come out different.
> >
> > In contrast to my previous posts, I'm having a little trouble thinking about this very clearly. It doesn't matter though; my health is on the mend, I can say whatever I want.
> >
> > -Philip
> "Hey, if I got this 'child proof' version perfectly right and explained it clearly, would someone notify me??"
>
> (No.)


Click here to read the complete article
1
server_pubkey.txt

rocksolid light 0.9.7
clearnet tor